Ordered List ADT Implemented With a Doubly Linked List

The above ordered list has one item. This item's key is 3.

The header node has a key of -¥ ( INT_MIN ). The trailer node has a key of +¥ ( INT_MAX ).

orderedlist.h

#ifndef ORDERED_LIST_H

#define ORDERED_LIST_H

#include <stddef.h>

#include <limits.h>

struct Info

{

...

};

class OrderedList {

public:

OrderedList();

~OrderedList();

OrderedList( /* in */ const OrderedList& srcOrderedList );

bool Search( /* in */ int key, /* out */ Info& info );

bool Insert( /* in */ int key, /* in */ Info info );

bool Delete( /* in */ int key );

int Size() const;

void Reset();

void Advance( /* out */ int& key, /* out */ Info& info );

bool IsEmpty() const;

bool IsFull() const;

void Traverse( /* in */ void (*) (/* in */ int, /* in */ Info ) );

private:

struct Node

{

int key;

Info info;

Node* next;

Node* prev;

};

Node* front;

int size;

Node* current;

};

#endif

orderedlist.cpp

// Pointer implementation of an ordered list

// Uses headers and trailers

// Uses a doubly linked list

#include "OrderedList.h"

OrderedList::OrderedList()

{

front = new Node;

front->key = INT_MIN;

front->next = new Node;

front->next->key = INT_MAX;

front->next->next = NULL;

front->next->prev = front;

size = 0;

}

OrderedList::~OrderedList()

{

Node* oldPtr;

while ( front != NULL )

{

oldPtr = front;

front = front->next;

delete oldPtr;

}

}

OrderedList::OrderedList( /* in */ const OrderedList& srcOrderedList )

{

front = new Node;

front->key = INT_MIN;

front->next = new Node;

front->next->key = INT_MAX;

front->next->next = NULL;

front->next->prev = front;

Node* srcPtr = srcOrderedList.front->next;

Node* rear = front;

Node* newPtr;

size = srcOrderedList.size;

for ( int i = 0; i < size; i++ )

{

newPtr = new Node;

newPtr->key = srcPtr->key;

newPtr->info = srcPtr->info;

newPtr->next = rear->next;

rear->next->prev = newPtr;

rear->next = newPtr;

newPtr->prev = rear;

rear = newPtr;

srcPtr = srcPtr->next;

}

}

bool OrderedList::IsEmpty() const

{

return (size == 0);

}

bool OrderedList::IsFull() const

{

return false;

}

bool OrderedList::Search( /* in */ int key, /* out */ Info& info )

{

for ( Node* location = front->next;

key > location->key;

location = location->next )

/* do nothing */ ;

// key <= location->key

if ( key == location->key )

{

info = location->info;

return true;

}

else

return false;

}

bool OrderedList::Insert( /* in */ int key, /* in */ Info info )

{

Node* backup;

for ( Node* location = front->next;

key > location->key;

location = location->next )

/* do nothing */ ;

// key <= location->key

if ( key == location->key )

return false;

else

{

// Create and fill in the new node

Node* newPtr = new Node;

newPtr->key = key;

newPtr->info = info;

// Insert before *location

backup = location->prev;

newPtr->next = location;

location->prev = newPtr;

backup->next = newPtr;

newPtr->prev = backup;

size++;

return true;

}

}

bool OrderedList::Delete( /* in */ int key )

{

for ( Node* location = front->next;

key > location->key;

location = location->next )

/* do nothing */ ;

// key <= location->key

if ( key == location->key )

{

location->prev->next = location->next;

location->next->prev = location->prev;

delete location;

size--;

return true;

}

else

return false;

}

int OrderedList::Size() const

{

return size;

}

void OrderedList::Reset()

{

current = front->next;

}

void OrderedList::Advance( /* out */ int& key, /* out */ Info& info )

{

key = current->key;

info = current->info;

current = current->next;

}