Doubly Linked List.. please Help!!

**ProgrammingDlux** · 10-22-2004

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.

**The Brain** · 10-23-2004

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

**ProgrammingDlux** · 10-23-2004

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.

**elad** · 10-23-2004

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.

**ProgrammingDlux** · 10-24-2004

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

**elad** · 10-24-2004

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.

**ProgrammingDlux** · 10-24-2004

I think I got it- almost

Could you possibly put sample code? I feel so burnt out and I just wanna finish..

**elad** · 10-24-2004

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

**ProgrammingDlux** · 10-24-2004

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

Thread: Doubly Linked List.. please Help!!

Thread Tools

Search Thread

Display

Doubly Linked List.. please Help!!

Similar Threads

help! Placement of nodes in a Linked List

Reverse function for linked list

airport Log program using 3D linked List : problem reading from file

Linked List

singly linked list