1. Member
Join Date
Aug 2011
Posts
16
Rep Power
0

The question goes like this
Swaps two elements in the list,
* list: A B C -> swap(A,B) will result in the list B A C
* list: A C C -> swap(A, D) will throw a NoSuchElementException
* list: A B C B -> swap (A, B) will result in the list B A C B
* list: A B C A B B -> swap (A,B) will result in the list B A C A B B
* a list with one or zero elements cannot do a swap

I'm really out of wits and ran out of patience with this question, I've made a working version but just changing the values is not allowed and I have to relink them manually. I spend already 10 hours on figuring out how to relink them. I'm sick of my lecturer he just threw everything to us without explaining and my classmates would not help.
I've checked out the internet all over but failed to understand why. This is my last resort.

Java Code:
```import java.util.NoSuchElementException;

public class SwapListImpl<T> implements SwapList<T>
{

int size=0;
Node<T> first;
Node<T> last;
Node<T> list;
Node<T> swapNode = new Node(0);

{
if(size==0)
{
first = new Node<T>(val); //
last = first; //
size++;  //
}
else
{
if(size==1)
{
list = new Node<T>(val);
last.prev = first;
last.next = list;
list.prev = first;
last = list;
size++;
}else{
Node<T> nNode=new Node<T>(val);
nNode.prev=last;
last.next=nNode;
last=nNode;
size++;
}
}
}

public T get(int i)
{
Node<T> temp = first;

for(int x=0; x<i;x++)
{
temp=temp.next;
}
return temp.val;
}

public void swap(T val1, T val2)
{
swap2(val1, val2);
}

public void swap2(T val1, T val2) throws NoSuchElementException
{
Node<T> elementA=first;
Node<T> elementB=first;
boolean found = false;
int i =0;
int x =0;

if(size>1)
{
while(!elementA.val.equals(val1) && elementA.next!=null)
{
elementA=elementA.next;
i++;
}

while(!elementB.val.equals(val2) && elementB.next!=null)
{
elementB=elementB.next;
x++;
}

if(!elementA.val.equals(val1) && !elementA.equals(val2) || !elementB.val.equals(val1) && !elementB.val.equals(val2))
{
throw new NoSuchElementException();
}

// I found the two nodes to swap but I cant ever get past the relink process
//    swapNode.prev = elementA.prev;
//    swapNode.next = elementB.prev;
//   System.out.println(swapNode.prev.val+" "+swapNode.next.val);

}
}
}```
Last edited by FiasseKrystella; 02-19-2012 at 11:35 AM.

2. ## Re: Linked List swapping question

Think of the elements before nodes A and B, say prevA and prevB. Also think of the elements following A and B, say nextA and nextB. So prevA and nextA embrace element A an similar with prevB, nextB and B. Swapping elements A and B is just updating all the pointers in the nodes:

Java Code:
```prevA.next= B;
nextA.prev= B;
B.prev= prevA;
B.next= nextA;

prevB.next= A;
nextB.prev= A;
A.prev= prevB;
A.next= nextB;```
kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•