Link List

I am reading the Link List section at C++ programming tutorial in Cprogramming.com. I need help to understand the following code better.

1. It would be great if someone could display this specific code in a diagram type display.
2. Are there only two nodes in here, root and conductor? with root data 12 and conductor data 42
3. If item #2 correct, how do I read the content of data in the 1st node (root) at the end of
main() code?

I have recently started to learn C++ and I apologize in advance if my request is too elementary.

Thanks,
Andrew

Code:

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

int main()
{
  node *root;       
  node *conductor;  

  root = new node;  
  root->next = 0;   
  root->x = 12;
  conductor = root; 

  if ( conductor != 0 ) 
   {
       while ( conductor->next != 0)
       conductor = conductor->next;
   }
  conductor->next = new node;  
  conductor = conductor->next; 
  conductor->next = 0;         
  conductor->x = 42;
}

2. Are there only two nodes in here, root and conductor? with root data 12 and conductor data 42

That is correct, there are just 2 nodes. The first node (root) holds 12, and the second node holds 42. conductor is just a pointer used to move through the list.

3. If item #2 correct, how do I read the content of data in the 1st node (root) at the end of
main() code?

Like this:

Code:

printf("root node holds: %d\n", root->x);

3. If item #2 correct, how do I read the content of data in the 1st node (root) at the end of
main() code?

Yes, 2 is correct. Think of the conductor as a way to walk through the list and do whatever you want to it.
So, for example if you wanted to print the list -
you could do something like this

Code:

 
   conductor = root; 
   while ( conductor) 
    {
          cout << conductor->x << endl;
          conductor = conductor->next;
    }

Thanks bithub and spidey for your descriptions,

Andrew

Couple of questions about the following simple link list code.

1. Do I have 3 nodes in the following link list?
Or the 3rd one is just over writing the 2nd one.

2. If I have 3 nodes then, how do I access the 2nd node's data?
Let's say, how can I print the value of the 2nd node at the end of the code?

Thanks,
Andrew

Code:

#include "stdafx.h"
#include <iostream>
using namespace std;

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

int main()
{
	node *root;
	node *conductor;

	root = new node;
	root->next = 0;
    root->x = 12;
	cout<< "The Root Node Value is = " << root->x <<endl;
	conductor = root;

	if (conductor != 0) {
		while (conductor->next != 0)
	//while (conductor != NULL) {
	//	cout<< "The Node Value is = " << conductor->x <<endl;
			conductor = conductor->next;
	}
	
	//=======================================================
	// 2nd Node Geneartion
	//=======================================================
	conductor->next = new node;
	conductor = conductor->next;
	//conductor->next = 0;
	conductor->x = 42;
	cout<< "The 2nd Node Value of X is = " << conductor->x <<endl;

    //=======================================================
	// 3rd Node Geneartion
	//=======================================================
	conductor->next = new node;
	conductor = conductor->next;
	conductor->next = 0;
	conductor->x = 152;
	cout<< "The 3rd Node Value of X is = " << conductor->x <<endl;

    cout<< "The 1st Node Value of X is = " << root->x <<endl;
	cin.get();
	return 0;
}

1. Do I have 3 nodes in the following link list?
Or the 3rd one is just over writing the 2nd one.

Yes, that is correct, you now have three nodes.

2. If I have 3 nodes then, how do I access the 2nd node's data?
Let's say, how can I print the value of the 2nd node at the end of the code?

Well, link list's dont have an index so theres no direct way of accessing element '2' without traversing the list.
Here is the same example I gave you, this will set the conductor to point at the root and then walk the list as it prints out each members x value.

Code:

   conductor = root; 
   while ( conductor) 
    {
          cout << conductor->x << endl;
          conductor = conductor->next;
    }

If you wanted to print the second element you could walk the list and stop after 2 increments like this -

Code:

conductor = root;
for(int i = 1; i < 2; ++i)
	conductor = conductor->next;
cout << conductor->x << endl;

1. Do I have 3 nodes in the following link list?
Or the 3rd one is just over writing the 2nd one.

Also, if your getting confused about how the link list works. Try drawing it out on paper and trace through the flow as you add and remove nodes. The basic principle to remember is that each node has a pointer to the next node in the list, so as long as you keep updating the next pointer, you will never overwrite a value.

A good exercise would be to create the functions

Code:

 void AddNode(int data);

which adds a node to the end of the list.

I think I see what you mean. The pointer has advanced to node 3 at the
end of the program and if I want to access the node 2, I have to do reverse
direction to the pointer to get the data in 2nd node.

Here how they:
1st node: root->next
root->x

2nd node: conductor->next
conductor->x

3rd node: conductor->next
conductor->x

As you noticed at the end of the program, I was able to read the data of the 1st node. I guess this because the pointer was unique. If we have to name every pointer a unique name then, that would not be practical. I would to be able to
read the 2nd node when I have traversed to the end of the above link list.
I guess the question is: How do I travel in reverse on pointers?

Thanks again,
Andrew

Originally Posted by andrewh

I think I see what you mean. The pointer has advanced to node 3 at the
end of the program and if I want to access the node 2, I have to do reverse
direction to the pointer to get the data in 2nd node.

Here how they:
1st node: root->next
root->x

2nd node: conductor->next
conductor->x

3rd node: conductor->next
conductor->x

As you noticed at the end of the program, I was able to read the data of the 1st node. I guess this because the pointer was unique. If we have to name every pointer a unique name then, that would not be practical. I would to be able to
read the 2nd node when I have traversed to the end of the above link list.
I guess the question is: How do I travel in reverse on pointers?

Thanks again,
Andrew

Well, first I'm not sure what your saying but here is the basic concept of your list.

root is the head or the first node of your list.
You then set conductor to point to root( the head of the list).
The only purpose of the conductor is to traverse the list so you can access elements other than the head.

Now for your question,

How do I travel in reverse on pointers?

There is no way to reverse the direction of a pointer in c++. But you can get you desired effect by adding a previous pointer to the list.

Code:

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

this is known as a doubly linked list.

Now you can rebuild your list like this

Code:

        node *root;
	node *conductor;

	root = new node;
	root->next = 0;
         root->prev = 0;
         root->x = 12;
	cout<< "The Root Node Value is = " << root->x <<endl;
	conductor = root;

Now when you add a new node, you just have to link the previous pointer as well -

Code:

//=======================================================
	// 2nd Node Geneartion
	//=======================================================
	conductor->next = new node;
	conductor = conductor->next;
	conductor->next = 0;
        conductor->prev = root;
	conductor->x = 42;
	cout<< "The 2nd Node Value of X is = " << conductor->x <<endl;

Now you, have access to both the previous and next node in the list and the ability to walk the list in both directions.

Thanks spidey for your suggestion. I guess I have used arrays so much and now need to get used to pointers.
I am also trying to look ahead in terms of usage. For instance, managing a link list with thousands of nodes. I guess you can't easily cherry pick on accessing a desired node.

I guess you can't easily cherry pick on accessing a desired node.

That is true, all linked lists have O(n) access which means that the time taken to access a specific element in the list, is directly proportional to the number of item's in the list(n).

However, linked list's are only one of the hundreds of data structures available to you as a programmer. If random access is important, then an array would definitely be the fastest. But if you wanted to look up specific items in you structure you could use something like a map or a hash table which are both dictionary like data structures.

Like a said, there are a number of data structures available. Which one you should use is dependent on many things like the usage pattern of your program, memory/speed etc.