Linked Lists

[Philandrew]

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.

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?

[cfrost]

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)

[manofsteel972]

>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

pointer=pointer->next;

[sigfriedmcwild]

  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)

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).

  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).

[elad]

>>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.

[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..

[Philandrew]

Ah, OK, makes sense

Thanks everybody!

[quzah]

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.