A Two-Way Sorted List Implemented as a linked structure in C++
Header file for a list class
//----------------------------------------------------------------------
// File: Code118_List.h
// Purpose: Header file for a demonstration of a sorted list
// implemented as a implemented as a two-way (double) linked list.
// Programming Language: C++
// Author: Dr. Rick Coleman
//----------------------------------------------------------------------
#pragma once;
#include <iostream>
using namespace std;
// Define a structure to use as the list item
struct ListItem
{
int key;
double theData;
ListItem *prev;
ListItem *next;
};
class Code118_List
{
private:
ListItem *head; // Pointer to head of the list
public:
Code118_List(); // Class constructor
~Code118_List(); // Class destuctor
void ClearList(); // Remove all items from the list
bool Insert(int key, double f);// Add an item to the list
ListItem *Delete(int key); // Remove and return an item from the list
ListItem *Search(int key); // Search for an item in the list
int ListLength(); // Return number of items in list
bool isEmpty(); // Return true if list is empty
bool isFull(); // Return true if list is full
void PrintList(); // Print all items in the list
};
Implementation (.cpp) file for a list class
//---------------------------------------------------------------------
// File: Code118_List.cpp
// Purpose: Header file for a demonstration of a sorted list
// implemented as a implemented as a two-way (double) linked list.
// Programming Language: C++
// Author: Dr. Rick Coleman
//---------------------------------------------------------------------
#include "Code118_List.h"
//--------------------------------------------
// Function: Code118_List()
// Purpose: Class constructor
// Returns: void
//--------------------------------------------
Code118_List::Code118_List()
{
head = NULL;
}
//--------------------------------------------
// Function: Code118_List()
// Purpose: Class destructor
// Returns: void
//--------------------------------------------
Code118_List::~Code118_List()
{
// Clear the list to free any memory being used
ClearList();
}
//--------------------------------------------
// Function: ClearList()
// Purpose: Remove all items from the list
// Returns: void
//--------------------------------------------
void Code118_List::ClearList()
{
ListItem *temp;
if(!isEmpty())
{
temp = head;
// Scan list and free all nodes
while(head != NULL)
{
temp = head;
head = head->next;
delete temp;
}
}
}
//--------------------------------------------
// Function: Insert()
// Purpose: Insert an item into the list.
// Returns: true if insertion was successful
// or false if the insertion failed.
//--------------------------------------------
bool Code118_List::Insert(int key, double f)
{
ListItem *temp, *newNode;
// Create a new node and insert the data
newNode = new ListItem();
// Check to see if memory allocation failed
if(newNode == NULL) return false;
// If all OK then insert the data
newNode->key = key;
newNode->theData = f;
newNode->next = NULL; // Very import to init these pointers to NULL
newNode->prev = NULL;
// Check to see if the list is empty
if(isEmpty())
{
// Insert new node as first in the list
head = newNode;
}
else
{
// Find location for new node in the list.
temp = head;
while((temp->next != NULL) && (temp->key < key))
{
temp = temp->next;
}
// Check to see if adding at head of list
if(temp->prev == NULL)
{
head->prev = newNode; // Set former head's prev pointer
newNode->next = head;
head = newNode;
}
// Check to see if adding at tail of list
else if((temp->next == NULL) && (newNode->key > temp->key))
{
temp->next = newNode;
newNode->prev = temp;
}
else // Insert somewhere else in list
{
newNode->prev = temp->prev; // Set newNode's pointers
newNode->next = temp;
temp->prev->next = newNode; // Set next pointer for node before newNode
temp->prev = newNode; // Set prev pointer for node after newNode
}
}
return true; // Signal successful insertion
}
//---------------------------------------------------
// Function: Delete()
// Purpose: Remove and return an item from the list.
// Returns: Item to be removed or NULL if not found.
//---------------------------------------------------
ListItem *Code118_List::Delete(int key)
{
ListItem *temp;
// Check for empty list
if(isEmpty()) return NULL;
// Search the list for the item to delete
temp = head;
// The order of the two conditionals in the while()
// loop is VERY important. You want to check first
// to see if temp is NULL before trying to reference
// the memory temp is pointing to. If temp is NULL
// then, because this is a && (AND) condition the
// second condition will never be tested. Testing
// the second condition when temp==NULL will result
// in a crash and burn.
while((temp != NULL) && (key != temp->key))
{
temp = temp->next;
}
// Check to see if the item was found
if(temp == NULL)
return NULL; // Not found so return NULL
else if(temp->prev == NULL) // Check to see if item is first in list
{
head = head->next; // Advance head pointer to next item in the list
if(head != NULL) // This wasn't the last node in the list
head->prev = NULL; // Set it's prev pointer to NULL
return temp; // Dispose of the node removed from the list
}
else // Delete node elsewhere in the list
{
// Move pointer of node before the one temp points to
temp->prev->next = temp->next;
// Check to make sure this is not the last item in the list
if(temp->next != NULL)
temp->next->prev = temp->prev;// Move pointer of node after the one temp points to
return temp; // Dispose of the node removed from the list
}
return NULL; // Should never get here but this is to keep the compiler from giving a warning
}
//--------------------------------------------
// Function: Search()
// Purpose: Search for an item by key and copy
// the value into the variable pointed to
// by *retVal.
// Returns: true if search was successful
// or false if the search failed.
// Note: The search in a double linked list
// is identical to that in a single
// linked list.
//--------------------------------------------
ListItem *Code118_List::Search(int key)
{
ListItem *temp;
temp = head;
// See note on the order of the conditional in this
// while() loop in Delete() function above.
while((temp != NULL) && (key != temp->key))
{
temp = temp->next;
}
// If item not found or list is empty return false
if(temp == NULL) return false;
else
{
ListItem *retItem = new ListItem;
*retItem = *temp; // Block copy the structure to return
retItem->next = retItem->prev = NULL; // Clear the pointers
return retItem; // Return the duplicate copy
}
}
//--------------------------------------------
// Function: ListLength()
// Purpose: Return the number of items in the
// list.
// Returns: Number of items in list.
//--------------------------------------------
int Code118_List::ListLength()
{
ListItem *temp;
int count = 0;
temp = head;
while(temp != NULL)
{
temp = temp->next;
count++;
}
return count;
// An alternate way to do this is to maintain
// a member variable in this class, e.g. int m_iCount.
// This can be incremented each time a node is added
// and decremented each time a node is deleted.
}
//--------------------------------------------
// Function: isEmpty()
// Purpose: Return true if the list is empty
// Returns: true if empty, otherwise false
//--------------------------------------------
bool Code118_List::isEmpty()
{
return (head == NULL);
}
//--------------------------------------------
// Function: isFull()
// Purpose: Return true if the list is full
// Returns: true if full, otherwise false
// Note: In theory a linked list cannot be
// full (unless you run out of memory) so
// this function defaults to returning false.
//--------------------------------------------
bool Code118_List::isFull()
{
return false;
}
//--------------------------------------------
// Function: PrintList()
// Purpose: Print all items in the list with
// their priority.
// Returns: void
//--------------------------------------------
void Code118_List::PrintList()
{
ListItem *temp;
cout << "\nItems in the List\n";
cout << "-----------------------------------------------------------\n";
cout << "Key\t\tData\n";
cout << "-----------------------------------------------------------\n";
if(head == NULL) // Report no items in the list
{
cout << "\t List is currently empty.\n";
}
else
{
temp = head;
while(temp != NULL)
{
cout << temp->key << "\t\t" << temp->theData << "\n";
temp=temp->next;
}
}
cout << "-----------------------------------------------------------\n";
}
Main file used to test the list
//---------------------------------------------------------------
// File: ListMain.cpp
// Purpose: Main file with tests for a demonstration of a sorted
// list implemented as a two-way (double) linked list.
// Programming Language: C++
// Author: Dr. Rick Coleman
// Date: February 2012
//---------------------------------------------------------------
#include "Code118_List.h"
int main()
{
Code118_List *theList;
ListItem *theItem;
cout << "Simple Double Linked List Demonstration\n\n";
cout << "Create a list and add a few items to the list\n";
theList = new Code118_List(); // Instantiate a list object
cout << "Adding (4, 2.5) as first item in the list.\n";
theList->Insert(4, 2.5); // Insert first item (4)
cout << "Adding (1, 5.6) at the head of the list.\n";
theList->Insert(1, 5.6); // Insert at head (1 4)
cout << "Adding (2, 3.1) in the middle of the list.\n";
theList->Insert(2, 3.1); // Insert in middle (1 2 4)
cout << "Adding (3, 8.3) in the middle of the list.\n";
theList->Insert(3, 8.3); // Insert in middle (1 2 3 4)
cout << "Adding (5, 7.4) at the tail of the list.\n";
theList->Insert(5, 7.4); // Insert at tail (1 2 3 4 5)
// Show what is in the list
theList->PrintList();
// Test the list length function
cout << "List now contains " << theList->ListLength() << " items.\n\n";
// Test delete function
cout << "Testing delete of last item in list.\n";
theItem = theList->Delete(5);
if((theItem != NULL) && (theItem->key == 5))
{
cout << "\tSuccessfully removed the last item in the list.\n";
delete theItem; // It is now our responsibility to delete it.
}
theList->PrintList();
// Test delete function
cout << "Testing delete of first item in list.\n";
theItem = theList->Delete(1);
if((theItem != NULL) && (theItem->key == 1))
{
cout << "\tSuccessfully removed the first item in the list.\n";
delete theItem; // It is now our responsibility to delete it.
}
theList->PrintList();
// Test delete function
cout << "Testing delete of a middle item in list.\n";
theItem = theList->Delete(3);
if((theItem != NULL) && (theItem->key == 3))
{
cout << "\tSuccessfully removed a middle item from the list.\n";
delete theItem; // It is now our responsibility to delete it.
}
theList->PrintList();
// Test delete function with a known failure argument
cout << "Testing failure to find item (key = 6) in delete function.\n";
if(theList->Delete(6) != NULL)
cout << "\tOops! Should not have been able to delete.\n";
else
cout << "\tUnable to locate item to delete.\n\n";
// Test search (known failure)
cout << "Testing Search function. Search for key 3 (not in the list).\n";
theItem = theList->Search(3);
if((theItem != NULL) && (theItem->key == 3))
{
cout << "\tSearch result for key 3: theData = %f\n\n", theItem->theData;
delete theItem; // It is now our responsibility to delete the duplicate returned.
}
else
cout << "\tSearch result for key 3: Unable to locate item in list\n\n";
// Test search (known success)
cout << "Testing Search function. Search for key 2 (in the list).\n";
theItem = theList->Search(2);
if((theItem != NULL) && (theItem->key == 2))
{
cout << "\tSearch result for key 2: theData = " << theItem->theData << endl << endl;
delete theItem; // It is now our responsibility to delete the duplicate returned.
}
else
cout << "\tSearch result for key 2: Unable to locate item in list\n\n";
cout << "\n\nEnd list demonstration...\n\n";
return 0;
}