Link List

This is a discussion on Link List within the C++ Programming forums, part of the General Programming Boards category; I am reading the Link List section at C++ programming tutorial in Cprogramming.com. I need help to understand the following ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    5

    Smile 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. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,261
    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. #3
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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;
        }
    Last edited by Spidey; 07-17-2009 at 04:57 PM.

  4. #4
    Registered User
    Join Date
    Jul 2009
    Posts
    5

    Link List

    Thanks bithub and spidey for your descriptions,

    Andrew

  5. #5
    Registered User
    Join Date
    Jul 2009
    Posts
    5

    Link List

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

  6. #6
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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;

  7. #7
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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.

  8. #8
    Registered User
    Join Date
    Jul 2009
    Posts
    5

    Link 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

  9. #9
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    Quote Originally Posted by andrewh View Post
    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.

  10. #10
    Registered User
    Join Date
    Jul 2009
    Posts
    5

    Link List

    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.

  11. #11
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 10:28 PM
  3. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 10:11 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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