Computer Science Canada

LinkedList Swap

Author:

cool dude [ Wed Jul 11, 2012 11:52 am ]

Post subject:

LinkedList Swap

I'm a little rusty at this so please bare with me. For the code below why is the head = head.next.next not actually advancing and staying the same?

Assume head was defined and there are other classes for LinkNode but for this problem the other classes are not needed to be posted as one can figure it out with them.

code:

public LinkNode swap()
{
LinkNode newList = head;
while (head != null)
{
newList = head.next;
newList.next = head;
head = head.next.next;
}

return newList;
}

Lets say the list is {A1, A2, B1, B2)

the following are the values i get in my debugger:

newList = head.next //newList = A2
newList.next = head //newList.next = A1
head = head.next.next //head =A1 PROBLEM! Since head doesn't move to next we get infinite loop.

What I am trying to do is swap adjacent values in a list. So for the example above the output should be {A2, A1, B2, B1}

Thank you

Author:	Tony [ Wed Jul 11, 2012 1:58 pm ]
Post subject:	RE:LinkedList Swap
so far it seems that A2.next is A1, not B1. Where's the code where you create this list?

Author:

cool dude [ Wed Jul 11, 2012 4:46 pm ]

Post subject:

Re: LinkedList Swap

Okay so the following in my main method creates the list and adds the elements:

code:

LinkedList myList = new LinkedList("A1");

myList.add("A2");

myList.add("B1");

myList.add("B2");

Next in my main method I call the swap method:

code:

myList.swap();

myList right now is {A1, A2, B1, B2} which I printed out to ensure its correct.

In the swap method the first 2 lines of the while loop produce correct results. head=A1 as it should and head.next = A2 as it should. However the third line of the while loop head=head.next.next remains A1 Confused

Author:

Dreadnought [ Wed Jul 11, 2012 7:06 pm ]

Post subject:

Re: LinkedList Swap

If these are pointers (I don't know Java) then

code:

newList = head.next; -- newList = A2
newList.next = head; -- newList.next = A1 or A2.next = A1
head = head.next.next; -- head = A1.next.next = A2.next = A1

If this is true, then the list is now A1 -> A2 -> A1 -> ...
B1 -> B2 (are no longer "attached" to the list)

Author:	cool dude [ Wed Jul 11, 2012 11:24 pm ]
Post subject:	Re: LinkedList Swap
Okay so I kinda see the problem here. newList and head share the same memory space. I thought that head didn't change when we modified newList so head = A1 and head.next = A2 and head.next.next = B1. How would I make it so that they don't share the same memory space so when I modifiy newList the original list head doesn't change?

Author:

Tony [ Thu Jul 12, 2012 12:08 am ]

Post subject:

RE:LinkedList Swap

but newList and head are the same thing, since

code:

LinkNode newList = head;

If you want them to be distinct objects, you'd need to allocate new memory space, e.g.

code:

LinkNode newList = new LinkNode(head);

(provided that you have the right constructors in place... it kind of seems that you are using Java's standard LinkedList; as such, I'm not sure how that relates to LinkNode)

But then you might end up creating a new copy of a list (so twice the space). You can probably do all of this with just a single pointer.

starting at head = A2 (in [A1, A2, B1, B2])

code:

head.previous.next = head.next; // A1 -> B1
head.previous.previous = head; // A2 <- A1
head.next = head.previous; // A2 -> A1
head.previous = null; // start <- A2

you end up with [A2, A1, B1, B2]

Author:

cool dude [ Thu Jul 12, 2012 11:07 pm ]

Post subject:

Re: LinkedList Swap

I followed your suggestion to allocate new memory space:

code:

LinkNode newList = new LinkNode(head);

I created a constructor like so:

code:

public LinkNode(LinkNode head)
{
data = head.data;
}

Seems like it still not allocating new memory space so i think my constructor might be wrong?

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy