Thread: Link Lists

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    1

    Link Lists

    Hey first of all I would like to say thanks for the help or even just reading this. Now to the problem if you have a singularly linked Link list in C and you wish to reverse the values which it holds can you?

    Move the memory locations which the pointers next value points to thus saving the values ever coming out of memory and increasign efficency 10 fold. Its kinda along the same lines as bit shifting for multiplication I suppose ? I had this question posed to me in a mock interview and I went along the above described lines to my solution only to be told that this is impossible / wrong and so coming last

    Any help much appreciated.

    Thanks

    Tom

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    You probably should have explained in more detail. Computers have a very small view of things at the moment. It may seem easy to just move the pointers, but the technical work behind that is much more difficult. Imagine this:
    Code:
    swap (A,B);
    That may look easy to you, a person with two hands. But the computer must allocate some extra space, C. The end result looks like this:
    Code:
    C = A;
    A = B;
    B = C;
    Think about how to approach linking singly-linked lists backwards. Starting off at the first element, you follow its pointer to the next element. In order to change its direction, you need a seperate pointer to store the old information. Otherwise, you've effectively isolated those two elements from the rest of the linked list.

    On the other hand...
    Move the memory locations which the pointers next value points to
    Moving memory locations is impossible. Moving the data stored at those locations is inefficient. What you want to do is to change the pointer's value to the node behind it instead of the one in front of it.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    The question really just asks you to swap the next pointers so that this:

    0->1->2->3->4->5->6->7->8->9

    becomes

    9->8->7->6->5->4->3->2->1->0

    Here's one way to do it:
    Code:
    List reverseList(List list)
    {
        Element newList = 0;
        Element item = list;
        Element forward;
        
        while (item)
        {
            forward = item->next;
            item->next = newList;
            newList = item;
            item = forward;
        }
        
        return newList;
    }
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I'm confused about link lists (again)
    By JFonseka in forum C Programming
    Replies: 4
    Last Post: 06-13-2008, 08:13 PM
  2. functions using link lists
    By chood72 in forum C++ Programming
    Replies: 3
    Last Post: 10-31-2005, 03:51 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Link lists as datastructure
    By stseitli in forum C Programming
    Replies: 13
    Last Post: 07-09-2002, 07:34 AM
  5. double link lists
    By rumi_red in forum C++ Programming
    Replies: 3
    Last Post: 10-30-2001, 10:13 AM