A linked list class

This example shows a linked list class and an application
   using it.

The header file, containing the class definition, is
   llist.h
The implementation of the class methods is provided in file
   llist.C
The application using the class is provided in file
   myapp.C

To compile the two .C files into object code we use:
   g++ -c llist.C
   g++ -c myapp.C

This produces two .o files:
   llist.o and myapp.o

To compile the .o files into a single executable we use:
   g++ myapp.o llist.o -o myapp

To run the executable file we use:
   ./myapp

// ======================================================
// file llist.h
// ======================================================
#ifndef LLIST_H 
#define LLIST_H 1

#include <string>
using namespace std;

// a sorted linked list of words and their meanings
//   (sorted by the words)
class LList {
   public:
      LList();                  // create an empty list
      LList(LList *L);          // create a list, duplicating L's contents
      ~LList();                 // deallocate the list
      int getSize();            // count the elements in the list
      bool mergeWith(LList *L); // add copies of L's elements to our list
      bool insert(string word, string meaning); 
                                // create and insert a word/meaning pair
      bool remove(string word); // remove the first instance of the word
      bool removeNext();        // remove the next instanc of the word
      string lookup(string word); 
                    // lookup the meaning of the first instance of the word
      string lookupNext();
                    // lookup the meaning of the next instance of the word
      void printAll();          // print all the word/meaning pairs
      
   private:
      // contents of an individual node within the list
      struct ListNode {
         string word;
         string meaning;
         ListNode *next;
         ListNode *prev;
      };
      ListNode *front, *back; // first and last list elements
      string    searchWord;   // most recently searched-for word
      ListNode *searchFrom;   // the node *after* the most recent search ended
      ListNode *findNode();   // starting from 'searchFrom', finds the first
                              // instance of 'searchWord'
      void      printOne(ListNode *n); // print a single word/meaning
      void      seperateNode(ListNode *victim); 
                    // cut the victim out of the list and delete it
};

#endif

// ======================================================
// file myapp.C
// ======================================================
#include "llist.h"
#include <iostream>
using namespace std;

int main()
{
   LList L;
   L.insert("csci161", "cruel torture");
   L.insert("adt", "abstract data type");
   L.insert("literal", "a hard-coded value within the source code");
   L.insert("adt", "a dave thing");
   cout << "Original list" << endl;
   L.printAll();
   LList *copy = new LList(&L);
   cout << "\nCopy of list" << endl;
   copy->printAll();
   cout << "\nList with one adt removed" << endl;
   L.remove("adt");
   L.printAll();
   return 0;
}

// ======================================================
// file llist.C
// ======================================================
#include <iostream>
#include "llist.h"
using namespace std;

// private components of class LList
//    struct ListNode {
//       string word;
//       string meaning;
//       ListNode *next;
//       ListNode *prev;
//    };
//    ListNode *front, *back;
//    ListNode *searchFrom;
//    string    searchWord;

LList::LList()
{
   front = NULL;
   back = NULL;
   searchWord = "";
   searchFrom = NULL;
}

LList::LList(LList *L)
{
   front = NULL;
   back = NULL;
   searchWord = "";
   searchFrom = NULL;
   mergeWith(L);
}

LList::~LList()
{
   while (front != NULL) {
      ListNode *victim = front;
      front = front->next;
      delete victim;
   }
}

int LList::getSize()
{
   ListNode *curr = front;
   int size = 0;
   while (curr != NULL) {
      curr = curr->next;
      size++;
   }
   return size;
}

bool LList::mergeWith(LList *L)
{
   if (L == NULL) {
      return false;
   }
   ListNode *curr = L->front;
   while (curr != NULL) {
      string w = curr->word;
      string m = curr->meaning;
      if (!insert(w, m)) {
         return false;
      }
      curr = curr->next;
   }
   return true;
}

bool LList::insert(string word, string meaning)
{
   ListNode *entry = new ListNode;
   if (entry == NULL) {
      return false;
   }
   entry->word = word;
   entry->meaning = meaning;
   entry->next = NULL;
   entry->prev = NULL;
   if (front == NULL) {
      front = entry;
      back = entry;
   } else if (word <= front->word) {
      front->prev = entry;
      entry->next = front;
      front = entry;
   } else if (back == NULL) {
      return false; // corrupt list
   } else if (word >= back->word) {
      back->next = entry;
      entry->prev = back;
      back = entry;
   } else {
      ListNode *curr = front;
      while ((curr != NULL) && (word > curr->word)) {
         curr = curr->next;
      }
      if (curr == NULL) {
         return false; // corrupt list
      } else {
         entry->prev = curr;
         entry->next = curr->next;
         curr->next = entry;
         entry->next->prev = entry;
      }
   }
   return true;
}

LList::ListNode *LList::findNode()
{
   ListNode *curr = searchFrom;
   while ((curr != NULL) && (curr->word != searchWord)) {
      curr = curr->next;
   }
   return curr;
}

bool LList::remove(string word)
{
   searchWord = word;
   searchFrom = front;
   return removeNext();
}

void LList::seperateNode(ListNode *victim)
{
   if (victim == NULL) {
      return;
   } else if (victim == front) {
      front = front->next;
      if (front == NULL) {
         back = NULL;
      } else {
         front->prev = NULL;
      }
   } else if (victim == back) {
      back = back->prev;
      if (back == NULL) {
         // means list was only element long,
         //    but victim didn't match front
         // so list must be corrupt!
         return; 
      }
      back->next = NULL;
   } else {
      if ((victim->prev == NULL) || (victim->next == NULL)) {
         return; // corrupt list again
      }
      victim->prev->next = victim->next;
      victim->next->prev = victim->prev;
   }
}

bool LList::removeNext()
{
   ListNode *victim = findNode();
   if (victim != NULL) {
      searchFrom = victim->next;
      seperateNode(victim);
      delete victim;
      return true;
   } else {
      return false;
   }
}

string LList::lookup(string word)
{
   searchFrom = front;
   searchWord = word;
   return lookupNext();
}

string LList::lookupNext()
{
   ListNode *target = findNode();
   if (target == NULL) {
      return "";
   } else {
      searchFrom = target->next;
      return target->meaning;
   }
}

void LList::printOne(ListNode *n)
{
   if (n != NULL) {
      cout << n->word << ":";
      cout << n->meaning << endl;
   }
}

void LList::printAll()
{
   ListNode *curr = front;
   while (curr != NULL) {
      printOne(curr);
      curr = curr->next;
   }
}