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