Explain the following lines of code - Doubly Linked List

Question

3.00/5 (2 votes)

See more:

Can anyone explain what does the following lines do? Can anyone explain how it works step by step?

C

void printChainInReverse(doubleChainCell *start)
{
    /* Start of Reverse function*/
    struct doubleChainCell *p1,*p2;
    p1=start;
    p2=p1->next;
    p1->next=NULL;
    p1->previous=p2;
    while(p2!=NULL)
    {
        p2->previous=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p2->previous; /*next of p2 changed to prev */
    }
    start=p1;
    printChain(start);
}

Thanks in advance!

Posted 23-Feb-12 7:45am

jack545

Updated 23-Feb-12 7:55am

Manfred Rudolf Bihy

v3

Add a Solution

Comments

Manfred Rudolf Bihy 23-Feb-12 15:17pm

Hi Jack! I've added a small sketch to my answer. Please have a look, I hope it will shed some light onto this for you!

:)

3 solutions

Solution 3

In plain words: The function removes the first node from the doubly linked list and directs pointer p1 to it. Then it takes the second node, directs pointer p2 to it and attaches it before the first node.

Now we continue doing so for all other nodes in the chain. We take next node from the original chain and glue it in front of our new chain. That is done by pointing p1 to where p2 has been pointing (the originally second node) and p2 to the next node of the original chain. Again, we attach the node that p2 is pointing to before the node that p1 points to. Thereby, node-by-node we reverse the sequence of the original chain. And so forth, until all nodes of the original chain have been moved over.

When we are done reversing the chain, we simply let printChain print our reversed chain.

What is unpleasant about that function? The name makes you believe, that it justs prints a linked list in reverse order. But in fact the function reverses the order of the list permanetly. Therefore, I would either

- rename it to reverseAndPrintChain, or
- modify it, such that the chain is only printed in reverse order, but not modified in the course of action.

Hope that helps you.

Posted 23-Feb-12 12:27pm

nv3

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Manfred Rudolf Bihy · Accepted Answer · 2012-02-23T08:01:00

Solve this by drawing a doubly linked list on a piece of paper. Then by going through the code in your sample for every step make a new drawing of the same list taking careful notice of what was changed. Have the drawing at the left hand side of the paper and at the right hand side write the code that made the change to the drawing. For statements that do not change the linked list there is no need to make a new drawing. To make things simpler for you it would be best to start with a linked list of length 2 or 3.

This will be a bit of tedious work, but it will surely help you understand in what is going on. I've used this before and I swear by it.

[Edit]
To get you started I made this little sketch you can study and finish:
http://img651.imageshack.us/img651/7158/doublelinkedlist.jpg[^]. In this sketch I've not drawn a new diagram for each and every statement, but rather contracted all steps that could be done as one with out getting confused.
I hope this URL will work. Tell me in a comment if it doesn't.
[/Edit]

Regards,

Manfred

OriginalGriff · Accepted Answer · 2012-02-23T08:07:00

Solution 2

It's pretty simple - but it would take far too much language to explain.
Instead, get four pieces of paper. Write a digit from 1 to 4 at the top of each, so they are all different, and you can tell then apart.
Now, divide each sheep in two with a vertical line. Label the left side "Previous" and the right side "Next". Write a digit in each side so the sheets look like this:

Sheet   Next   Previous
  1       2        0
  2       3        1
  3       4        2
  4       0        3

Now, start in your program points to sheet four
Run your program through through, and watch what happens to the sheets.

Posted 23-Feb-12 8:07am

OriginalGriff

Comments

jack545 23-Feb-12 14:19pm

what's with p1 and p2??

Manfred Rudolf Bihy 23-Feb-12 14:23pm

They are just pointers to elements of the linked list. So they could be two small pieces paper that have the current number of the sheet they are pointing to written upon them. Same goes for the attempt I advocated but there it would be a small box with an arrow pointing at the current node of the linked list.

jack545 23-Feb-12 14:27pm

so is it like this-p1 is previous of sheet 1, p2 is next of sheet 1 because p2=p1->next
then, p1->next=NULL; i.e next of sheet 1=NULL i.e p2=NULL

How does this work p1->previous=p2;

OriginalGriff 23-Feb-12 14:47pm

It rewrites the content of the sheet p1 refers to. In this case, the pervious pointer gets the number of the sheet p2 refers to.

jack545 23-Feb-12 14:34pm

@Manfred R. Bihy

Manfred Rudolf Bihy 23-Feb-12 14:20pm

That also looks like a plan that should work. 5+
My idea was to make a drawing of a linked list that would be changed for each line of code, but yours is nice too.

OriginalGriff 23-Feb-12 14:49pm

Yep. There is no substitute for paper and pencil sometimes!

jack545 23-Feb-12 15:09pm

it is not getting into my mind
its too difficult to understand

Manfred Rudolf Bihy 23-Feb-12 15:19pm

I've added a small sketch to my answer that will hopefully clear things up for you. :)

OriginalGriff 23-Feb-12 15:30pm

Your handwriting is a lot neater than mine! :laugh: :jealous:

Manfred Rudolf Bihy 23-Feb-12 15:55pm

I was into my third beer when I produced the sketch, so I think there is room for improvement. :)
Thanks for the compliment anyhow.

OriginalGriff 23-Feb-12 15:28pm

It is pretty simple, you just have to work out what is going on.
A pointer is not the object - it tells you where the object is.
This really isn't easy without pictures, and without seeing the glazed look in your eyes...
Ignore the double links, and ignore your code for a moment - a single list is easier to visualise.
So the "next" pointer tells you where the next object in the list is, and it's "next" tells you further on. The last item in the list doesn't have a next object, so it's "next" pointer is zero.
So, the "start" value is 1: look at sheet 1. It's next pointer is 2, so the order is HEAD--1--2.
To advance forward through the list, you set up a pointer (p1) which you set to the value of "start" (i.e. 1)
1) Look at p1. Is it zero? Yes? You have finished.
If not, set p1 to the value in p1->next (i.e. 2)
2) Repeat from 1

Follow that with your paper, and you should see what I mean.

Your code does the same, but more complexly. (I have no idea why a print routine changes the list, but there must be a reason).

jack545 23-Feb-12 14:31pm

Thanks

Sergey Alexandrovich Kryukov 23-Feb-12 16:25pm

It becomes a popular post. My 5, too. :-)
--SA