Solved

Understanding piece of linked list code

Posted on 2006-11-25
13
169 Views
Last Modified: 2010-03-31
I have to write comments for a piece of code that I wrote a while ago.
The last line is the line I have lost my understanding of:

swap.setPrevious(swapWith.getPrevious()); // sets previous of that node to previous of other node

swap.setNext(swapWith.getNext()); // opposite to the above

swapWith.getPrevious().setNext(swap);

Please tell me what this last line is doing. An example might help.

Cheers
0
Comment
Question by:john8932
  • 6
  • 5
  • 2
13 Comments
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18011663
Consider three nodes (NodeFirst and NodeLast are terminal nodes, do not contain an object):

NodeFirst - Node1 - Node2 - Node3 - NodeLast

Now assume we want to swap node Node1 with Node3 we get that..

swap(Node1, Node3);

Node1.prev = Node3.prev
Node1.next = Node3.next

But now the Node2 does not know that Node1 is his next, so...

Node3.prev (which is Node2) .next = Node1

Voila. I think that if it really performes a swap that there will be more lines..

Mark

0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18011675
The 3rd swaps an item from before 'current' to after 'current'.

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
|       |       |  B   |   C  |   A |       |       |      |       |       |       |      |       |       |      
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
If C is the current item,
the 3rd takes 'B' out and inserts it between C & A

;JOOP!
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18011679
ADSLMark, did you notice that 'swap' and 'swapWith' are different collections?

;JOOP!
0
Is Your AD Toolbox Looking More Like a Toybox?

Managing Active Directory can get complicated.  Often, the native tools for managing AD are just not up to the task.  The largest Active Directory installations in the world have relied on one tool to manage their day-to-day administration tasks: Hyena. Start your trial today.

 
LVL 24

Expert Comment

by:sciuriware
ID: 18011680
... at least I didn't read it right in that 3rd statement.  Ooops!

Now we know once more how important it is to write comments while you're writing source.

And the comment you got is aparently not clear enough.

;JOOP!
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18011685
Collections?? I think they represent a node inside a linkedlist, no?

class Node
{
    Node getPrevious();
    Node getNext();
    void setPrevious(Node prev);
    void setNext(Node next);
}

class LinkedList
{
    public void swap(Node swap, Node swapWith)
    {
        ...
        swap.setPrevious(swapWith.getPrevious());
        swap.setNext(swapWith.getNext());
        swapWith.getPrevious().setNext(swap);
        ...
    }
}

Mark
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18011692
Second time we clash.. hmm I am beginning to remember your name.. how nice.

Mark
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18011694
Possible, let him confirm.

;JOOP!
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18011696
Clash? Some questions can be misunderstood.
;JOOP!
0
 

Author Comment

by:john8932
ID: 18014582
Thanks for the replies.

And confirm what exactly?
0
 
LVL 24

Expert Comment

by:sciuriware
ID: 18014778
That at least one of us understood the question and gave the appropriete answer.

;JOOP!
0
 

Author Comment

by:john8932
ID: 18019735
I am using nodes in a linked list.

At the moment I get an infinite loop of the last value that was input to be swapped.

Please do not give the answer, just hints so I am not cheating and so I can understand how the logic of the swap would work.

At the moment I am thinking that I have to (for node 2 and 3 swap):

1. Set node 2 previous to 3 previous
2. Set node 2 next to 3 next
3. Set node 3 previous (node 2 next) to equal node 1 - something like this:

swapWith.getPrevious().setNext(swap);

Any more logic needed for the kind of swap you mentioned i.e. two middle values? - obviously when I am swapping start or end nodes there will be conditions for null.

Cheers
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18019960
Swapping requires you to save some information about one of the nodes, since after you set node 2 its prev and next, you lose that information, so you can never know what todo for the other node.

It is not so difficult to get a good swapping method. Make sure you have a flexible representation of a list, with begin and end terminal, this will make it a lot easier to check for "special cases" (most of the times the code wont have to be modified if you use terminal nodes).

Another tip would be to write it down on paper (notepad if you prefer) and just perform the swap manually. Like:

TB - A - B - C - TE

Swap(A,C)

A.prev = C.prev
A.next = C.next
C.prev.next = A
...

And make sure that in the end all the prev/next are set correctly.

Good luck
Mark
0
 
LVL 10

Accepted Solution

by:
ADSLMark earned 125 total points
ID: 18020162
Let me give a more clear hint:

The use of terminal nodes has a advantage that if you want to swap the first or last node that you can still access the previous and next node of that specific node.
For example:

TB - A - B - C - TE

TB.next = A
TB.prev = null
TB.obj = null

So both pointers (next/prev) in A are set and can be used (won't be null in a correct implementation).

I just tried to manually build the swap method and it took 9 statements (assuming both parameters are valid nodes). I think it can be slightly better using a mathematic trick (using XOR) but the simple version counts 9 lines (+3 for java method).

Mark
0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
micro services vs rest web services 16 107
split string containing \r\n in Java 46 44
servlet  URL Rewriting 1 37
Which non-HTML GUI front end to use with Java? 3 22
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question