Linked Lists

This is a discussion on Linked Lists within the C++ Programming forums, part of the General Programming Boards category; Can somebody help explain linked lists to me? I read the tutorial on this site, and I read SAMS Teach ...

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    63

    Linked Lists

    Can somebody help explain linked lists to me?

    I read the tutorial on this site, and I read SAMS Teach yourself in 21 Days...but I still don't really understand linked lists

    I understand the idea that its data and pointers, and the pointer keeps it moving down to the next set of data (the link in the list)
    But I don't really see how this could be useful or why everybody says it is so important.

    Code from Tutorial
    Parts I don't understand are underlined.
    Code:
    struct node {
      int x;
      node *next;
    };
    
    int main()
    {
      node *root;       // This won't change, or we would lose the list in memory
      node *conductor;  // This will point to each node as it traverses the list
    
      root = new node;  // Sets it to actually point to something
      root->next = 0;   //  Otherwise it would not work well
      root->x = 12;  // why are we jumping to 12?  How would this be done in a real-world prog?
      conductor = root; // The conductor points to the first node
      if ( conductor != 0 ) {
        while ( conductor->next != 0)
          conductor = conductor->next;
      }
      conductor->next = new node;  // Creates a node at the end of the list
      conductor = conductor->next; // Points to that node
      conductor->next = 0;         // Prevents it from going any further
      conductor->x = 42;
    }
    Any help would be appreciated
    Where are these puppies used? Why are they important? What are the alternatives? Why are they better than the alternatives?
    Last edited by Philandrew; 12-08-2004 at 02:19 AM.
    -Webmaster-
    http://www.koaworld.com
    Pr0gr4m|\/|1Ng n00b

  2. #2
    Registered User cfrost's Avatar
    Join Date
    Apr 2004
    Posts
    119
    Ok
    I think you didn`t understood the idea of link list , what you do is you create an object of required data type and link it to previous one so that you can reach it again for example your list is:
    8->9->7->13->.........

    Now I want to search seven from list what you do now is start search from start by comparing 7 seven with each of element until you reach end of list.

    Now if you allocate memory and do not link it you will never be able to trace back the element , And As far as NULL of 0 is concerned in pointers you must know that NULL is a sentinal Value (a check for us that list has ended)
    Software is like sex it is good when it is free

  3. #3
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    >how this could be useful or why everybody says it is so important.


    Linked lists are great for a variety of reasons but one of the major uses is when you need to dynamically create a list and either grow or shrink the list whenever it is needed. For arrays you need to know exactly how big to make it and the size is fixed. You can't just make the array bigger without a lot of copying. (ie you would have to create a bigger or smaller array then copy over all the elements) With linked lists it is a lot easier since they are all connected with pointers all you do is just reassign the pointers and delete or add individuall nodes (elements) in the list. You can insert a whole string of elements in the middle of a list something that involves a lot of copying with arrays.

    >Parts I don't understand are underlined.

    That is just a loop that you use to find the end of the list. You can't just index a linked list like you would an array because any time you add a node in the middle any index after that would no longer point to what it did before. So you have to start at the begining of the list and follow the links down until you find what your looking for or you hit the end of the list which is a null pointer. Basically instead of increment an index in an array you are just advancing to the next node when you say
    Code:
    pointer=pointer->next;
    Last edited by manofsteel972; 12-08-2004 at 03:16 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  4. #4
    Registered User
    Join Date
    Dec 2004
    Location
    UK
    Posts
    109
    Code:
      root->x = 12;  // why are we jumping to 12?  How would this be done in a real-world prog?
    You are not jumping to the 12th element, you are setting the value of the root element to 12 (see the declaration of the node struct)

    Code:
    if ( conductor != 0 ) {
        while ( conductor->next != 0)
          conductor = conductor->next;
      }
    here you are going trhough every element of the list until you hit the end. The last node is identified by the fact that its next pointer is null (next = 0).

    Code:
      conductor->next = new node;  // Creates a node at the end of the list
      conductor = conductor->next; // Points to that node
      conductor->next = 0;         // Prevents it from going any further
      conductor->x = 42;
    And finally here you add an element to the end of the list. Notice that the formerly last element next pointer now points to the new element and the new element next pointer is null.

    As they said before linked listst are very useful when you have data collections that can greatly vary in size. An array would force you to either copy all the data over and over as you keep on enlarging it to make space for new data or to waste large amounts of space by making an array as big as the maximum number of elemnts you could ever have (which micht impossible to know beforehand).
    Linked lists on the other hand can grow and shrink quickly and easily by tacking on more elements at either end or even in the middle by changing the value of at most 2 pointers (for a singly linked list).

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    >>But I don't really see how this could be useful or why everybody says it is so important.

    Lists provide great practice in general problem solving and use of pointers. In addition, most everything you learn how to do with list can be carried over to trees and other more complex data structures that many programs use.

  6. #6
    Codin huh?
    Join Date
    Dec 2004
    Posts
    6
    for speed, and better memory usage..
    allowing you to increase and decrease the list as data is input'd or as its removed, using memory only as needed, instead of a fixed size. like an array..

  7. #7
    Registered User
    Join Date
    Oct 2004
    Posts
    63
    Ah, OK, makes sense

    Thanks everybody!
    -Webmaster-
    http://www.koaworld.com
    Pr0gr4m|\/|1Ng n00b

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by JoeS
    for speed, and better memory usage..
    allowing you to increase and decrease the list as data is input'd or as its removed, using memory only as needed, instead of a fixed size. like an array..
    For speed compared to what? I think this was covered...must have been the Mud Connector. I seem to vaguely recall a lengthy discussion on iterating through a list versus iterating through an array.

    However, the main benifit of a linked list isn't speed. It's as stated, the ability to grow when needed, insertion, etc.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 09:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21