Doubly Linked List.. please Help!!

This is a discussion on Doubly Linked List.. please Help!! within the C++ Programming forums, part of the General Programming Boards category; Any help is greatly appreciated.. How do I read this information int a Doubly Linked List? I don't even know ...

  1. #1
    Registered User ProgrammingDlux's Avatar
    Join Date
    Jan 2002
    Posts
    86

    Doubly Linked List.. please Help!!

    Any help is greatly appreciated..

    How do I read this information int a Doubly Linked List? I don't
    even know where to start.

    Code:
    #include<iomanip.h>
    #include<string>
    #include<fstream>
    #include"DubDV_listP.C"
    
    ifstream IF ("csc23565_lab4.txt");
    ofstream OF ("OUTPUT_lab4.txt");
    
    typedef struct{
       string lastName;
       string phoneNumber;
       string course[15];
    } Person;
    
    
    main()
    {
      int RecCount=1;
      Person Rec;
    
             if( !IF )
                {cout<<"cannot open file"<<endl;
                 exit;}
    
       // loop for Records of Person
       while ( IF >> Rec.lastName)
             { OF<<Rec.lastName << "  ";
                cout <<" ";
                cout <<Rec.lastName<<" ";
    
                IF >>Rec.phoneNumber;
                OF<<Rec.phoneNumber << "  ";
                cout <<Rec.phoneNumber<<"    ";
    
          // loop through the courses for this Record
    
                int courseIndex=0;   // reseting the array index to zero
                IF >>Rec.course[courseIndex];
    
                while (Rec.course[courseIndex] != "XXX111")
                 {cout<<Rec.course[courseIndex]<<" ";
                   OF<<Rec.course[courseIndex];
    
                   courseIndex++;
                   IF>>Rec.course[courseIndex];
                  
          }// end of course loop
    
          OF << endl;
          cout << endl;
          RecCount++;
          c++;
       }// end of while loop for records of Person
    
    }

    The sample info in the txt file is basically a directory of students:

    Arthur 1234567890 MTH235 PHY235 SOC235 XXX111
    Grant 1234567890 PSY235 ART235 XX111
    Johns 1234567890 CSC235 XXX111



    and the file "DubDV_listP.C" I'm including is :

    Code:
      
    typedef int DlistItemType;
    class DlistNode;            // linked list node
    
    typedef DlistNode* ptrType;  // pointer to node
    
    class DlistNode          // a node on the list
    {
       friend class  DlistClass;
       DlistItemType DItem;  // a data item on the list
       ptrType       DNext;  // pointer to next node
       ptrType       DPrev; // pointer to prev node
    };  // end class listNode
    
    class DlistClass
    {
    public:
    // constructors and destructor:
       DlistClass();                    // default constructor
       DlistClass(const DlistClass& L);  // copy constructor
       ~DlistClass();                   // destructor
    
    // list operations:
       bool DListIsEmpty() const;
       int  DListLength() const;
       void DListInsert(int NewPosition, DlistItemType NewItem,
                       bool& Success);
       void DListDelete(int Position, bool& Success);
       void DListRetrieve(int Position, DlistItemType& DataItem,
                         bool& Success) const;
    
    private:
       int     Size;  // number of items in list
       ptrType Head;  // pointer to linked list of items
       ptrType Tail;
       ptrType DPtrTo(int Position) const;
       // Returns a pointer to the Position-th node
       // in the linked list.
    }; // end class
    
    
    DlistClass::DlistClass(const DlistClass& L): Size(L.Size)
    {
       if (L.Head == NULL)
          Head = NULL;  // original list is empty
    
       else
       {  // copy first node
          Head = new DlistNode;
          assert(Head != NULL);  // check allocation
          Head->DItem = L.Head->DItem;
    
          // copy rest of list
          ptrType NewPtr = Head;  // new list pointer
          // NewPtr points to last node in new list
          // OrigPtr points to nodes in original list
          for (ptrType OrigPtr = L.Head->DNext;
                       OrigPtr != NULL;
                       OrigPtr = OrigPtr->DNext)
          {  NewPtr->DNext = new DlistNode;
             assert(NewPtr->DNext != NULL);
             NewPtr = NewPtr->DNext;
             NewPtr->DItem = OrigPtr->DItem;
          }  // end for
    
          NewPtr->DNext = NULL;
       }  // end if
    }  // end copy constructor
    
    DlistClass::~DlistClass()
    {
       bool Success;
    
       while (!DListIsEmpty())
          DListDelete(1, Success);
    } // end destructor
    
    bool DlistClass::DListIsEmpty() const
    {
       return bool(Size == 0);
    }  // end ListIsEmpty
    
    int DlistClass::DListLength() const
    {
       return Size;
    }  // end ListLength
    
    ptrType DlistClass::DPtrTo(int Position) const
    // --------------------------------------------------
    // Locates a specified node in a linked list.
    // Precondition: Position is the number of the
    // desired node.
    // Postcondition: Returns a pointer to the desired
    // node. If Position < 1 or Position > the number of
    // nodes in the list, returns NULL.
    // --------------------------------------------------
    {
       if ( (Position < 1) || (Position > DListLength()) )
          return NULL;
    
       else  // count from the beginning of the list
       {  ptrType Cur = Head;
          for (int Skip = 1; Skip < Position; ++Skip)
             Cur = Cur->DNext;
          return Cur;
       }  // end if
    }  // end PtrTo
    
    void DlistClass::DListRetrieve(int Position,
                                 DlistItemType& DataItem,
                                 bool& Success) const
    {
       Success = bool( (Position >= 1) &&
                       (Position <= DListLength()) );
    
       if (Success)
       {  // get pointer to node, then data in node
          ptrType Cur = DPtrTo(Position);
          DataItem = Cur->DItem;
       }  // end if
    } // end ListRetrieve
    
    void DlistClass::DListInsert(int NewPosition,
                               DlistItemType NewItem,
                               bool& Success)
    {
       int NewLength = DListLength() + 1;
    
       Success = bool( (NewPosition >= 1) &&
                       (NewPosition <= NewLength) );
    
       if (Success)
       {  // create new node and place NewItem in it
          ptrType NewPtr = new DlistNode;
          Success = bool(NewPtr != NULL);
          if (Success)
          {  Size = NewLength;
             NewPtr->DItem = NewItem;
    
             // attach new node to list
             if (NewPosition == 1)
             {  // insert new node at beginning of list
                NewPtr->DNext = Head;
                Head = NewPtr;
             }
    
             else
             {  ptrType Prev = DPtrTo(NewPosition-1);
                // insert new node after node
                // to which Prev points
                NewPtr->DNext = Prev->DNext;
                Prev->DNext = NewPtr;
             }  // end if
          }  // end if
       }  // end if
    } // end ListInsert
    
    void DlistClass::DListDelete(int Position,
                               bool& Success)
    {
       ptrType Cur;
    
       Success = bool( (Position >= 1) &&
                       (Position <= DListLength()) );
    
       if (Success)
       {  --Size;
          if (Position == 1)
          {  // delete the first node from the list
             Cur = Head;  // save pointer to node
             Head = Head->DNext;
          }
    
          else
          {  ptrType Prev = DPtrTo(Position-1);
             // delete the node after the
             // node to which Prev points
             Cur = Prev->DNext;  // save pointer to node
             Prev->DNext = Cur->DNext;
          }  // end if
    
          // return node to system
          Cur->DNext = NULL;
          delete Cur;
          Cur = NULL;
       }  // end if
    }  // end ListDelete
    
    
    // END of listClass Implementation Code


    If you've read this far, thank you. I don't normally post this much code, but I just don't know where to start with my problem.. i've been drawing blanks since yesterday.
    "For in fact what is a man in Nature? A Nothing in comparison with the Infinite, an All in comparison with the Nothing, a mean between nothing and everything"- Blaise Pascal

  2. #2
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    I just finished a program that uses doubly linked lists..

    For my program, I used head node insertion.. so whenever I created a new node:


    pseudocode:

    1) make new node-> next point to head node

    2) make head node -> prev point to the new node

    3) make new node-> prev = NULL

    4) assign the new node.. as the head node.

    5) make sure you handle the special case of adding your first node... ( 1. assign a tail pointer to your first node 2. make sure
    tail pointer->next = NULL)

    repeat the process for inserting more nodes



    Here is what I used to create the double-link:

    excerpt:
    Code:
    new_node = new node<T>;
    
    		T entry;
    
    		cout << "\n\n\tEnter Name: ";
    		getline(cin,entry);	
    	
    		new_node->name = entry;
    	
    		if (head_ptr != NULL)			//This block will be the most frequent occurrance	
                                                            //Perform the double-link..  the old head node will
    			head_ptr->prev = new_node;	//point to the new temp node..  and the new temp 
    			new_node->next = head_ptr;	//node will point to the old head node.	
    			new_node->prev = NULL;
    		}
    
    		else //(head_ptr == NULL)	//This block is for the first node to be added to the 
                                                    //linked list.  This is a "special case" that will 
    			new_node->next = NULL;	//facilitate the "empty list". When adding the first
    			tail_ptr = new_node;	//node to the list, *next should be set to NULL..  also assign
    		}			        //this node as the tail.


    Check out the entire algorithm here



    How do I read this information int a Doubly Linked List? I don't
    even know where to start.

    Create a function, that will iterate to the proper node, and dereference the desired information


    This is what I used:

    Code:
    template<class T>
    T Linkedlist<T>::get_name(int iter)
    {
    	if (iter > node_counter || head_ptr == NULL)
    	
    		return "";
    
    	else
    	{		
    		--iter;
    		
    		node<T> *cursor = head_ptr;		
    
    		for (int counter = 0; counter < iter; counter++)     //Use a loop like this that will iterate to the desired node
    		
    			cursor = cursor->next;
    		
    		return cursor->name;     //dereference the desired information	
    	}
    }

    In your program, you use:

    Code:
    {
       if ( (Position < 1) || (Position > DListLength()) )
          return NULL;
    
       else  // count from the beginning of the list
       {  ptrType Cur = Head;
          for (int Skip = 1; Skip < Position; ++Skip)
             Cur = Cur->DNext;
          return Cur;
       }  // end if
    }  // end PtrTo
    Which returns a pointer to the desired node...



    Now, all you have to do is dereference Cur (i.e. Cur->data_item) to access the data from that node

    Try this:

    Code:
    DPtrTo(int Position)->data_item;     //dereference DPtrTo( ) which returns a pointer to desired node.
    which will allow you to do stuff like this:
    Code:
    cout << DPtrTo(node_position)->data_item;
    Hope this helps
    Last edited by The Brain; 10-23-2004 at 02:48 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  3. #3
    Registered User ProgrammingDlux's Avatar
    Join Date
    Jan 2002
    Posts
    86
    Thanks for your input Brain, but for some reason I am not comprehending the whole picture.. I seem to be experiencing a bad case of writer's block- it's been like this for two days. I'm frozen on this project and I have no idea how to tackle it.
    "For in fact what is a man in Nature? A Nothing in comparison with the Infinite, an All in comparison with the Nothing, a mean between nothing and everything"- Blaise Pascal

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    I'd suggest going back to the beginning and look at what you want to do. Then tackle just one step at a time. For instance, in C++ struct are usually declared like this:


    struct Person
    {
    //declarations
    };

    without the typedef keyword like in C. Also it's

    int main()

    not

    main()

    Then think about the struct/class you are going to use as a node/link of the list. What all does that struct/class need, and what is the relationship between the node/link struct/class and the list class. Then write one list function at a time. Make sure that function is up and running before moving to the next function. In the case of some functions, like an insertion/add function, maybe just get one case up and running before tackling the others. I strongly suggest you don't write the whole program and try to debug it all at once.

  5. #5
    Registered User ProgrammingDlux's Avatar
    Join Date
    Jan 2002
    Posts
    86
    Thanks Elad.. you're advice helped me out. I took a deep breath and just focused on what I wanted to do (one step at a time). In doing so, I encountered another obstacle. I am making a PrintBackward() function and I realized I need to have Tail identifiable.. What should I add to this code to make it work?

    Code:
    void DlistClass::DListInsert(int NewPosition,
                               DlistItemType NewItem,
                               bool& Success)
    {
       int NewLength = DListLength() + 1;
    
       Success = bool( (NewPosition >= 1) &&
                       (NewPosition <= NewLength) );
    
       if (Success)
       {  // create new node and place NewItem in it
          ptrType NewPtr = new DlistNode;
          Success = bool(NewPtr != NULL);
          if (Success)
          {  Size = NewLength;
             NewPtr->DItem = NewItem;
    
             // attach new node to list
             if (NewPosition == 1)
             {  // insert new node at beginning of list
                NewPtr->DNext = Head;
                Head = NewPtr;
             }
    
             else
             {  ptrType Prev = DPtrTo(NewPosition-1);
                // insert new node after node
                // to which Prev points
                NewPtr->DNext = Prev->DNext;
                Prev->DNext = NewPtr;
    
             }  // end if
          }  // end if
       }  // end if
    } // end ListInsert
    my PrintBackward() function looks like this by the way..
    Code:
    void DlistClass::DprintBwd()
    {
           cout<< endl<< "The contents of the backwards list are";
           ptrType Cur = Tail;
             while(Cur != NULL)
              { Cur->DisplayLink();
                Cur=Cur->DPrev;}
            cout<<endl;
    }
    "For in fact what is a man in Nature? A Nothing in comparison with the Infinite, an All in comparison with the Nothing, a mean between nothing and everything"- Blaise Pascal

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Since this is a doubly linked list make sure DListNode has two members that are of type pointer to ptrType; one called DNext, and the other, presumably, DPrev. Each time you create a new ptrType object, initialize DNext and DPrev to NULL. If you don't, then in DprintBwd() Cur will never be NULL and your current code will be in an infinite loop.

    I suggest you write out how the insertion will occur. For example, "insertion will always be at the front of the list", or "insertion will always be a the back of the list", or whatever. But make sure you can write out where you want to insert the new node in very specific terms--it will make the code you need to write much easier.

    If you do specifically designate a Tail node, then you need to keep track of it just like you do Head. That means, if there are no nodes in the list then Tail should be NULL, just like Head. If there is just one node in the list then Head and Tail should be the same node. Only if there is more than one node in the list will Tail be different than Head.

    If you don't want to keep track of a Tail node, that's all right too, because there will only be one node with DNext == NULL in the entire list, the last one. And there will only be one node in the list with DPrev == NULL, the first one, usually called Head. That means you can always use a loop to find Tail if you don't specifically keep track of it during insertions and deletions. Remember, Tail and Head may or may not change during any given insertion, depending on relationship of position of insertion relative to Tail and Head.

    If you insert into the middle of the list someplace you need two nodes from the list to work with: NewPtr, Prev, and maybe something like Cur; and you will have four pointers to update: Prev->DNext, NewPtr->DPrev, NewPtr->DNext, and Cur->DPrev. If you always insert at the front of the list, always insert at the end of the list, always insert just after Head, or always insert just before Tail, then you will have fewer nodes and pointers to keep track of.

    Not having to keep track of all the nodes and pointers is one of the reasons that using std::list class is so tempting.

  7. #7
    Registered User ProgrammingDlux's Avatar
    Join Date
    Jan 2002
    Posts
    86
    I think I got it- almost Could you possibly put sample code? I feel so burnt out and I just wanna finish..
    "For in fact what is a man in Nature? A Nothing in comparison with the Infinite, an All in comparison with the Nothing, a mean between nothing and everything"- Blaise Pascal

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    WARNING: the following code has not been compiled. There may be, and probably are, errors. It is meant as an example, demonstrating some ideas, not necessarily working code.
    Code:
    //node struct for a doubly linked list
    struct node
    {
       int data;
       node * next;
       node * prev;
    };
     
    //a doubly linked list, implemented as a struct so I don't have to worry about access.  
    //You SHOULD be concerned with access rights in your code!
    struct List
    {
       node * head;
       node * tail;
       List () : head(NULL), tail(NULL) {};
       void insert(int);
       void revDisplay();
       //etc;
    };
     
    void List::insert(int i)
    {
       //always insert at the end of the list
       //explicitly keep track of tail
     
       //declare new node and initialize members
       node * newNode = new Node;
       newNode->data = i;
       newNode->next = NULL;
       newNode->prev = NULL;
    	  
       if(head == NULL)
       {
    	  //means no nodes in list at this time
    	  head = tail = newNode;
    	}
       else if(head == tail)
       {
    	  //means only one node in list at this time
    	  tail = newNode;
    	  head->next = newNode;
    	  tail->prev = head;
       }
    	else
    	{
    	   //there is more than one node in list at this time.  
    	   tail->next = newNode;
    	   newNode->prev = tail;
    	   tail = tail->next;
    	 }
    }
     
    void List::revDisp()
    {
       //display data in list backwards, one line per node
     
       node * cur = tail;
       while(cur != NULL)
    	{
    	   cout << cur->data << endl;
    	   cur = cur->next;
    	}
    }

  9. #9
    Registered User ProgrammingDlux's Avatar
    Join Date
    Jan 2002
    Posts
    86
    ELAD, You are the man!! I just took a little part from what you typed, changed the variables, and it compiled and ran perfectly on the first time.

    I tip my hat to you.. I hope to be that good some day.. Thanks a million...


    Code:
    void DlistClass::DListInsert(int NewPosition,
                               DlistItemType NewItem,
                               bool& Success)
    {
    
            int NewLength = DListLength() + 1;
           Success = bool( (NewPosition >= 1) &&
                                  (NewPosition <= NewLength) );
    
        if (Success)
          {  // create new node and place NewItem in it
              ptrType NewPtr = new DlistNode;
              Success = bool(NewPtr != NULL);
        if (Success)
          {  Size = NewLength;
              NewPtr->DItem = NewItem;
    
             // attach new node to list
               if (NewPosition == 1)
               {  
                     NewPtr->DNext = Head;
                     Head =Tail= NewPtr;
               }
    
               else if (Head == Tail)
               {    Tail = NewPtr;
                     Head->DNext = NewPtr;
                     Tail->DPrev = Head;
               }
    
              else 
               {
                  Tail ->DNext = NewPtr;
                  NewPtr->DPrev = Tail;
                  Tail = Tail->DNext;
               }
          
    
          }  // end if
       }  // end if
    } // end ListInsert
    Thanks Again
    "For in fact what is a man in Nature? A Nothing in comparison with the Infinite, an All in comparison with the Nothing, a mean between nothing and everything"- Blaise Pascal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  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