Like Tree1Likes
  • 1 Post By Salem

Help with my doubly linked list

This is a discussion on Help with my doubly linked list within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> using namespace std; struct dNode { int info; dNode *next; //link to next node dNode *back; //link ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    135

    Help with my doubly linked list

    Code:
    #include <iostream>
    
    using namespace std;
    
    struct dNode
    {
    	int info;
    	dNode *next; //link to next node
    	dNode *back; //link to previous node
    };
    
    void main(void)
    {
    	dNode *head, *tail, *newNode *current;
    	head = tail = newNode = NULL;
    
    	newNode = new dNode;
    	newNode->info = 55;
    	newNode->next = NULL;
    	newNode->back = NULL;
    	cout << "My first node is " << newNode -> info << endl;
    
    	head = tail = newNode;
    
    	newNode = new dNode;
    	newNode->info = 514;
    	newNode->next = NULL;
    	newNode->back = NULL;
    	cout << "My second node is " << newNode -> info << endl;
    	tail->next = newNode;
    
    	newNode = new dNode;
    	newNode->info = 27;
    	newNode->next = NULL;
    	newNode->back = NULL;
    	cout << "My third node is " << newNode -> info << endl;
    	tail->next = newNode;
    
    	newNode = new dNode;
    	newNode->info = 35;
    	newNode->next = NULL;
    	newNode->back = NULL;
    	cout << "My fourth node is " << newNode -> info << endl;
    	tail->next = newNode;
    	cout << "End of building a linked list: " << endl;     //end of building a linked list
    
    	cout << "Transvering " << endl;                         //start to transverse
    	current = head;                                        //set current pointer to the first
    	
    
    	system ("pause");
    }
    I am now doing the doubly linked list. I not sure what should I do to transverse and print the values using cout. Because, doubly linked list got 2 linking to the next nodes and I am totally stucked on what to do.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    When you're adding to the end of a DL list, you do

    node->next = NULL;
    node->back = tail;
    tail->next = node;
    tail = node;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    135
    Code:
    #include <iostream>
     
    using namespace std;
     
    struct nodeType
    {
        int info;
        nodeType * link;
    };
     
    int main()
    {
        nodeType * first, * last, *newNode, * current ,*previous;
        first = last = newNode = NULL;
     
         
     
         
        cout << "Building a linked list: " << endl;
     
        newNode = new nodeType;                                  //create a first node
        newNode -> info = 5;                                     //first node = 5;
        newNode -> link = NULL;                                  //make the first link to NULL first
        cout << "My first node is " <<newNode -> info << endl;   //print the first node = 5
         
     
        first = last = newNode;                                  //ensure pointer first and last is in first node
                                             
        newNode = new nodeType;                                  //create a second node                                 
        newNode -> info = 15;                                    //second node = 15;
        newNode -> link = NULL;                                  //make the second link to NULL first
        cout << "My second node is " <<newNode -> info << endl;  //print the second node = 15
        last->link = newNode;                                    //link to the second node from the first node
        last = newNode;                                          //set last point to the second node
     
        newNode = new nodeType;                                  //create the third node
        newNode -> info = 10;                                    //third node = 10;
        newNode -> link = NULL;                                  //make the third link to NULL first
        cout << "My third node is " <<newNode -> info << endl;   //print the third node =1 0
        last->link = newNode;                                     //link to the third node from the second node
        last = newNode;
     
        newNode = new nodeType;                                 //create a fourth node
        newNode -> info = 22;                                   //fourth node = 22;
        newNode -> link = NULL;                                 //make the fourth node link to NULL first
        cout << "My fourth node is " <<newNode -> info << endl; //print the fourth node
        last->link = newNode;
        last = newNode;
         
        cout << "End of building a linked list: " << endl;     //end of building a linked list
         
        //Start of Transvering
        cout << "Transvering " << endl;                         //start to transverse
        current = first;                                        //set current pointer to the first node
         
        cout << "Transvering through the first node" << endl;   
        cout << current-> info << endl;                        //5
     
        cout << "Transvering thorugh the second node" << endl;
        current = first;                                       //set current back to first node
        current = current->link ;                              //set current pointer to the second node
        cout << current -> info << endl;                       //15
     
        cout << "Transvering through the third node" << endl;
        current = first;                                        //set current back to first node
        current = current-> link->link;                        //set current pointer to third node
        cout << current -> info << endl;                       //10
     
        cout << "Transvering through the fourth node" << endl;
        current = first;                                       //set current back to first node
        current = current-> link->link->link;                  //set current pointer to fourth node
        cout << current -> info << endl;                       //22
         
        cout << "Transvering through the last node" << endl;   //trying to transverse after the fourth node, accessing after from the fourth node
        if (current == last)
        {
            cout << endl;
            cout << "No transvering allowed in fourth node: " << endl;        //error would be given since there are only 4 nodes
             
        }
        else
        {
            cout << current -> info << endl;                    //would not print and go through this else statement since it is not possible
        }
        cout << endl;
         
        cout << "Transvering back to the first node: " << endl; //back to the first node
        cout << endl;
        current = first;                                        //set current back to the first node
        cout << current -> info << endl;                        //print , 5
     
     
        //Deleting third node
         
        previous = first->link;         // Previous points to second node
        current = previous->link;       // Current points to third node
        previous->link = current->link; // 2nd node link pointer to link to the 4th node
        delete current;                 // Delete the third node pointing 
     
        //Print after deleting using transverse
        current = first;                //set the current back to the first node
        cout <<"New first node is " <<  current -> info << endl;    //print the first node, 5
      
        current = first;                                            //set current back to the first node                                  
        current = current ->link;                                   //set current pointing to the second node
        cout << "new Second node is " << current -> info << endl;   //print the second node, , 15
     
        current = first;                                               //set current pointing back to the first node  
        current = current ->link->link;                                //set current pointing to the fourth node since third node has been deleted
        cout << "New Third node is " << current -> info << endl;       //print 22 instead 0f 10
        cout << "Deletion of the third node is successfully." << endl;
     
        //Insertion new node between first node and third node
        //newNode = new nodeType;                                  //create a new node
        //newNode -> info = 33;                                     //first node = 33;
        //newNode -> link = NULL;                                  //make the first link to NULL first
        //cout << "My new node is " <<newNode -> info << endl;   //print the first node = 33
        //previous = first;        
        //current = current->link; 
        //previous -> link = newNode;
        //newNode = current;
        //cout << current -> info << endl;
        //cout << current -> info << endl;
        //cout << current -> info << endl;
         
         
        system ("pause");
        return 0;
    }
    I managed to build a single linked list but completely unsure how to implement in double linked list. Is the pointer that I wrote enough for transverse. Maybe i add another current pointer to transverse but do I need other point just to transverse.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    It might help if you had some utility functions which say
    - appendNodeToList
    - prependNodeToList
    - insertNodeIntoList
    type functions, rather than merely copy/pasting everything and hoping you get all the link pointer edits correct.

    There are plenty of prior examples on the board to look at.
    iMalc likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked list
    By msky in forum C Programming
    Replies: 0
    Last Post: 11-11-2011, 04:25 PM
  2. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 02:31 PM
  3. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 02:39 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Doubly Linked List.. please Help!!
    By ProgrammingDlux in forum C++ Programming
    Replies: 8
    Last Post: 10-24-2004, 09:27 PM

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