Linked Lists

Ok so im pretty new to C++ and am using the tutorials to get started. So far ive been pretty good but when i got to linked lists i got lost. I understand the concept but the acutally code makes absolutly no sense. While i realize there are comments if someone has a easy way to explain it or could help me with adding more detailed comments it would be greatly appreciated. You can reply to the post of reach me at <<snipped>>. Thankz

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;
  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;
}

---

So, do you have a real question, or do you just want someone to write arbitrary comments that you MAY find useful?

--
Mats

Well adding more detailed comments or getting on a IM would be great but here

What exactly is "->" mean through the code

-> requires a pointer to a struct on the left, and a member of that struct on the right. The result is the value of the member in the struct pointed to. So: root->x is the "x" variable in the structure that root points to.

something->other is short for (*something).other. So what it means is:
something is a pointer, and I want to get to the element other that the pointer points to.

This is part of "pointer to structure" learning, and is an essential part of linked lists, since linked lists are structures with a pointer to the next structure.

[Silly note: This is my 0x1000th post!]

--
Mats

Scroll down to "Pointers to structures": http://www.cplusplus.com/doc/tutorial/structures.html

[edit] Too slow. [/edit]

ok so its using pointers and changing the members of the structures...

and secondly why does it use a pointer as a acutally member of the structure at first.

Code:

---

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

---

and thanks for your quick answers amd help i really am not grasping this concept

Quote:

---

Originally Posted by Bleu_Cheese

ok so its using pointers and changing the members of the structures...

and secondly why does it use a pointer as a acutally member of the structure at first.

Code:

---

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

---

---

Well, the short answer is "That's how linked lists work".

The idea behind linked lists is that you can extend the list at the end, and add nodes in the middle of the list. To do that, you need some sort of "link" to the next element in the list. This is your "next" pointer.

It has to be a pointer, because the next node isn't part of the current element - it is the NEXT element. Does that make sense?

--
Mats

ok im starting to understand maybe parts of this. I added comments in here explaining what i could but there are many parts that im not exactly sure. If anyone would be willing to replace my comments with some kind of explanation i believe i will understand this. If not thanks for your help and ill try to figure it out.

Code:

---

struct node {
  int x;       
  node *next;
}; 
int main()
{
  node *root;      // these are 2 pointers to the structure
  node *conductor; 
  root = new node;  // it uses a ptr to make a starting point
  root->next = 0;  // Need more explanation
  root->x = 12;    // Need more explanation
  conductor = root; // sets the other ptr = the ptr conductor
  if ( conductor != 0 ) {      // if the conductor not = to 0 ... how does it know that? never defined?
    while ( conductor->next != 0)  // Need more explanation
      conductor = conductor->next;  // Need more explanation
  }
  conductor->next = new node;  // Need more explanation
  conductor = conductor->next; // Need more explanation
  conductor->next = 0;        // Need more explanation
  conductor->x = 42;          // Need more explanation
}

---

Code:

---

struct node {
  int x;       
  node *next;
}; 
int main()
{
  node *root;      // these are 2 pointers to the structure
  node *conductor; 
  root = new node;  // it uses a ptr to make a starting point

---

Code:

---

  root->next = 0;  // Need more explanation

---

That's the same as (*root).next = 0. What it's doing is setting the "next" member of the newly allocated structure assigned to root to 0, or NULL -- the standard value used to indicate that the pointer is in fact pointing at nothing at all.

Code:

---

  root->x = 12;    // Need more explanation

---

This is setting the x value of the first node in the list, the element that was dynamically allocated and assigned to root. It's syntactically equivalent to (*root).x = 12;.

Code:

---

  conductor = root; // sets the other ptr = the ptr conductor

---

Code:

---

  if ( conductor != 0 ) {      // if the conductor not = to 0 ... how does it know that? never defined?

---

What do you mean? conductor was "defined" -- it's a variable of type node*.

Basically that's checking to see if conductor is pointing at a valid element or not. If it's not, conductor will contain 0 or NULL. Presumably this is so the contents of conductor can be used. Accessing a node that doesn't really exist is not a very good idea.

Code:

---

    while ( conductor->next != 0)  // Need more explanation
      conductor = conductor->next;  // Need more explanation

---

This loop loops while the next element of the structure that conductor is pointing to is a valid node. Every time, it advances conductor to point to the next node.

In effect, after this loop executes, conductor will be pointing at the last element in the linked list, because conductor->next will be NULL -- there will be no node after the current one.

Code:

---

  }
  conductor->next = new node;  // Need more explanation

---

conductor->next, which was NULL, is now being assigned to a new, dynamically allocated node.

Code:

---

  conductor = conductor->next; // Need more explanation

---

Just like in the loop, conductor is advanced to point to the new node.

Code:

---

  conductor->next = 0;        // Need more explanation
  conductor->x = 42;          // Need more explanation
}

---

42! The answer to life, the universe, and everything! :p Never mind.

The data in the new node is being set up. Before this happens, the node will contain random data, so setting it is a good idea. :)

Thanks much, I think I have some what of a basic understanding of this now. Do you happend to have something that really puts this to use ?

Well, a linked list is typically used when you have elements (or nodes) that refer to each other. One idea might be a game where there are lots of rooms. Since a room would typically be a class, it would have members that points to the next room depending on the direction you would walk.
So it contains a pointer for north, south, west and east. They all point to another room object.

That's one thing I can think of.

:D you know ... that concept just turned the little light bulb in my head on lol ... i think it actually makes sense lol