Linked Lists?

Hi, this is a newbie question but here goes...

I cannot seem to understand linked lists! Its one of those things you just don't get. I've read the tutorial about 1,000 times and I still don't get it. Could someone just explain the absolute basics of how it works, or show me a good tutorial?

-Thanks a ton

Imagine a series of post-it notes on a piece of string.

Adding to either end is pretty easy, adding to the middle is harder (cut the string, add the note, tie the two strings back together again).

What else did you want to know?

No offense, but what is that supposed to mean?

I mean like code.
Such as:

Code:

Blah, blah, blah.

The first blah means....

and so on.

-Thanks Anyway

Code:

|HP|------->  |Dell|------->  |Acer|-------->  |Mac|-------->  |Sony|

so that's a linked list. one points to another, the next one.

The principle of linked lists is that they have a "link" from one element to the next. This link is usually called "next".

The link is often a pointer, but you can make linked lists with arrays, where the "next" component is an index to the next item.

The whole idea is to "chain" things together, and not have to shuffle things if you need to insert or remove items.

Aside from that, please try to explain better what part you don't understand.

--
Mats

Maybe i should have been more specific. I mean like syntax.
such as:

Code:

Some commands and stuff... // This command means...

More commands and explanations...

Like a sample program with explanations on what each part is for.

This is the code I have been looking at:

Code:

struct node {
  int x;
  node *next;
};

int main()
{
  node *root;      
  root = new node; 
  root->next = 0;  
                   
  root->x = 5;     
}

One of the things I don't understand is why are there two pointers (specifically root) when i looks like the "next" would be a pointer to for every node you use. I realize "root" is a part of the struct but then I get really confused when I try to think about why it would be a pointer then!!!

You need a pointer to the beginning of the list - this is the "root" from which the list grows.

Code:

int main()
{
  node *root;      // Pointer to the first node
  root = new node;  // Get memory for the first node.
  root->next = 0;  // Mark the "next" node as "not there".
                   
  root->x = 5;     // Fill in the list with some value. 
}

However, this is pretty meaningless - that's like saying you have a SET of tools when you have one screwdriver. This is a linked list with one element, which is valid, and one screwdriver is a set of tools too - but very limited.

A more reasonable example:

Code:

#include <iostream>

struct node {
  int x;
  node *next;
};

int main()
{
  node *root;      // Pointer to the first node
  root = new node;  // Get memory for the first node.
  root->next = 0;  // Mark the "next" node as "not there".
                   
  root->x = 5;     // Fill in the list with some value. 
// Since this is C++, we can introduce new variables later.
  node *newNode;
  newNode = new node;   // Create one more item. 
  newNode->x = 7;   // Set x to 7. 
  newNode->next = 0;  // Mark this as the end. 
  root->next = newNode; // Insert it after root. 
  for(int i = 0; i < 3; i++) {
     node *current = newNode; // This is the previously inserted node.
     newNode = new node;   // A further node.
     newNode->x = i + 10;  // Set x to a something.
     newNode->next = 0;  // Mark the end.
     current->next = newNode;   // Insert the node AFTER current. 
  }
  
  node *temp;  // A temporary node pointer.
  temp = root; // Set it to the start of the list. 
  while (temp != 0) {  // Check if we are at the end (0), if not, go print the contents of the list
	  std::cout << "x = " << temp->x << std::endl;   // Print the "x" for this node.
     temp = temp->next;   // Go to the next item in the list. 
  }
  return 0;
}

Output:

Code:

x = 5
x = 7
x = 10
x = 11
x = 12

--
Mats

That is really helpful but (and I don't want to sound ungrateful but) 2 things:



1. Could you please supply a complete code (Something I can cut and Paste and run)

2. I am pretty newbish (as you probably know) and I'm just coming back to C++ after a while, do you think you could supply a simpler example?

-Thanks a bunch, I really appreciate it.

Because I'm so kind, I've added the necessary include file and copied the structure from your example into the extended example I wrote. Instead of re-posting some twenty or so lines of identical code, I edited the original post above.

If you don't want the LONG example I showed, then use the short "screwdriver is a set of tools" example that you gave (copy the #include line in my previous post - or remove all of the extension from my example)- but it DOES absolutely nothing other than create a single element linked list.

--
Mats

root is just so that the list doesn't get lost in memory.

also, in your example, root was not part of a struct. (not to say that it shouldn't be like that)

Thanks matt and everyone else,

P.S. You are so kind

Just one further comment that I thought of after I had shut the computer down.

The analogy that Salem gives isn't bad, but I prefer to look at it as a chain of paperclips, with post-it notes on each paper-clip. The hook that connects one paper-clip to another is the "next" pointer, and the "clip" bit is the part "holding your data" (x in the above example-code).

--
Mats

For anyone else with this problem

http://richardbowles.tripod.com/cpp/...t/linklist.htm

Really cleared it up for me.