Double linked list implementation

Question

I am having some syntax problems with a double linked list program I am writing for educational purposes. I have created a struct in my header file, and my main program seems to be alright, but implementing my functions in the .cpp file is giving me immense difficulty. I am having trouble discerning the three cases for inserting a record into the list. Specifically, allocating the memory, initializing the list head and tail, and the order of statements is confusing to me, as is passing a copy of the record to be added to my list.

My header file is as follows:

struct rec
{
   char * id;
   char firstname[15];
   char lastname[15];
   struct rec* prev;
   struct rec* next;
};


int AddItem ( rec r );
int DeleteItem ( char* delid );
void PrintList ( int order );

My .cpp file, which is where the difficulty lies, is as follows:

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

// These pointers refer to the head and tail of the list.
rec* first = NULL;
rec* last = NULL;

int AddItem( Rec r )
{

   rec* newRecEntry;
   rec* current = NULL;
   rec* previous = NULL;

   // Check for duplicate id
   current = first;
   while (current)
   {
     if( strcmp(current -> id, r.id) == 0)
      {
         return 0;
      }
     else
      // Create a new node
      {
         newRecEntry = new Rec;
         newRecEntry->id = new char[strlen(r.id)+1];
         strcpy(newRecEntry->id, r.id);
         strcpy(newRecEntry->firstname,r.firstname);
         strcpy(newRecEntry->lastname,r.lastname);
         newRecEntry->next = NULL;
         newRecEntry->prev = NULL;
      }
      // Find the appropriate position for the node and insert accordingly
      // Check to see if the list is empty
      if (first == NULL)
      {
         first = newRecEntry;
         last = newRecEntry;
      }
      else if ( r.lastname>last.lastname)
      {




      else
      {

   return 0;
}

/*int DeleteItem(char* ID)

I am supposed to be able to insert at the beginning, middle, and end of the list. Delete an item from the list based on the ID, and print the list in ascending or descending order based on user input, but I'd first simply like to handle the addition of items to said list. My function definitions are as follows and also contains some errors

lists.cpp

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

// These pointers refer to the head and tail of the list.
   rec* first = NULL;
   rec* last = NULL;

int AddItem( Rec r )
{

   rec* newRecEntry;
   rec* current = NULL;
   rec* previous = NULL;

   // Check for duplicate id
   current = first;
   while (current)
   {
     if( strcmp(current -> id, r.id) == 0)
      {
         return 0;
      }
     else
     // Create a new node
      {
         newRecEntry = new Rec;
         newRecEntry->id = new char[strlen(r.id)+1];
         strcpy(newRecEntry->id, r.id);
         strcpy(newRecEntry->firstname,r.firstname);
         strcpy(newRecEntry->lastname,r.lastname);
         newRecEntry->next = NULL;
         newRecEntry->prev = NULL;
      }
      // Find the appropriate position for the node and insert accordingly
      // Check to see if the list is empty
      if (first == NULL)
      {
         first = newRecEntry;
         last = newRecEntry;
      }
      else if ( r.lastname>last.lastname)
      {




      else
      {

   return 0;
}

/*int DeleteItem(char* ID)
{
   rec
}
*/



/*void printList(int order)
{
loop
 {
   cout << ptr -> Id << " ";
   cout << ptr -> firstname << " ";
   cout << ptr -> lastname << " ";
   cout << ptr -> prev << " ";  // address of previous
   cout <<  ptr << " ";   // address of item
   cout << ptr -> next << " ";  //  address of next item
 }

}

Main is as follows:

#include <iostream>
#include "list.h"
#include <string.h>  // <string>

using namespace std;

void main (void)
{
   int choice, printorder;
   char idbuffer[100];
   rec r;


do
{
  cout << "Enter your choice 1 Add, 2 Delete, 3 Print, 0 quit "<<endl;
  cin >> choice;

   switch ( choice )
   {
      case 1:  //AddItem
         cout << "\nEnter ID ";
         cin >> idbuffer;

         r.id = idbuffer;
         cout << "\nFirst Name ";
         cin >> r.firstname;
         cout << "\nLast Name ";
         cin >>  r.lastname;
         if ( AddItem ( r ) )
         {
            cout << "\nSuccess!\n";
         }
         else
         {
            cout << "\nItem failed to be added\n";
         }

         break;
      case 2:  //Delete
         cout << "\nEnter id :";
         cin >> idbuffer;
         if ( DeleteItem ( idbuffer ) )
         {
            cout << "\nDelete OK\n";
         }
         else
         {
            cout << "\nDelete Failed for " << idbuffer;
         }
         break;
      case 3: // Print
        cout << "Enter order 0 - Ascending, 1 - Descending\n";
        cin >> printorder;
        PrintList (printorder);
        break;
      case 0:  // quit
         break;


      default: // bad choice
         break;
   } // end switch

}
while ( choice != 0 );// end do while
}  // end main

Answer 1

It may not seem like it, but even this function

int AddItem(Record entry)
{
   Record* newRecordPointer;
   newRecordPointer=new Record;
   strcpy(newRecordPointer->firstName,entry.firstName);
   strcpy(newRecordPointer->lastName,entry.lastName);
   newRecordPointer->ID=new char[strlen(entry.ID)+1];
   strcpy(newRecordPointer->ID, entry.ID);
   return 0;
}

is trying to do too many things.

Let's write the pseudocode description of adding an item to a list:

1. create a new node
2. populate the new node with the values provided
3. attach the new node to the list

I've marked the verbs and nouns involved, and you can already see one of the nouns is missing from your function. You're asking AddItem to add an item to a list ... but you don't give it a list to work on.

It's also useful to write out your expectations clearly:

1. before AddItem is called:
   • it needs a list to work on
   • we don't have a list container class, just the records, so we have to pass a Record
   • let's say we want to add our new item after the Record passed in
2. after AddItem is called:
   • whatever Record we passed in, its Next should point to the new node
   • the new node's Previous should point to the node passed in
   • etc. etc. (these are the standard doubly-linked list insertion behaviours)
3. note for later: we haven't described how we store an empty list
   • if it's a circular list, an empty list will be a Record whose Next and Previous members point to itself
   • if it's linear, they might both be NULL instead
   • it could just be a NULL pointer, but then adding the first node to an empty list needs more effort

So, let's say the minimal function that could possibly work is:

void AddItem(Record *insert_after, Record value)
{
    Record *new_node = CreateRecord();
    CopyRecordValues(new_node, &value);
    AttachAfter(insert_after, new_node);
}

Note that if we were writing real C++ the first two lines could just use the copy constructor Record *new_node = new Record(value), but it will take more changes than that to reach idiomatic C++ code from where we started.

---

Now, given that, can you:

• implement those three functions? (CreateRecord and CopyRecordValues are already handled in your current code)
• write the equivalent pseudocode for your other operations, and translate it yourself?

Answer 2

Try changing this:

int AddItem(Record entry);

To this:

Record* AddItem(Record entry, Record *insertion_point = NULL );

If insertion_point is NULL, you can assume that the Record is the beginning of a new list.

Now you have enough information to set Next and Previous pointers, and return the newly created node.