Ordered List ADT implemented with pointers

The ordered list ADT can be implemented as a linked list, with a pointer to the front of the linked list

Here we have an ordered list of integers, with integer 3 at the front of the ordered list and integer 7 at the rear of the ordered list. The integers are in ascending order.

Each node is declared as:

const int MAX_LENGTH_NAME = 30;

struct Info

{

char lastname[MAX_LENGTH_NAME +1];

char firstname[MAX_LENGTH_NAME +1];

double salary;

};

struct Node

{

int key;

Info info;

Node* next;

};

An empty ordered list has a NULL value stored in its front pointer and an initial size of 0

The ordered list of integers will have a constructor, a copy constructor, a destructor, methods for inserting, deleting, and searching for items, methods for determining if an ordered list is empty or full, a method that returns the size of the ordered list, and methods for traversing the ordered list.

#ifndef ORDERED_LIST_H

#define ORDERED_LIST_H

#include <stddef.h>

...

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;

private:

struct Node

{

int key;

Info info;

Node* next;

};

Node* front;

int size;

Node* current;

};

#endif

Implementation of the ordered list's constructor

The ordered list's front pointer is initialized to NULL. The ordered list's initial size is 0.

OrderedList::OrderedList()

{

front = NULL;

size = 0;

}

Implementation of the ordered list's copy constructor

OrderedList::OrderedList(

/* in */ const OrderedList& srcOrderedList )

{

front = NULL;

size = srcOrderedList.size;

Node* newPtr = NULL;

for ( Node* srcPtr = srcOrderedList.front;

srcPtr != NULL;

srcPtr = srcPtr->next )

{

if ( newPtr == NULL )

{

front = new Node;

newPtr = front;

}

else

{

newPtr->next = new Node;

newPtr = newPtr->next;

}

newPtr->key = srcPtr->key;

newPtr->info = srcPtr->info;

newPtr->next = NULL;

}

}

Implementation of the ordered list's destructor

The destructor removes all nodes from the linked list and return them to the heap.

OrderedList::~OrderedList()

{

Node* oldPtr;

while ( front != NULL )

{

oldPtr = front;

front = front->next;

delete oldPtr;

}

}

Implementation of bool IsEmpty() const

An ordered list is empty if its size is 0.

bool OrderedList::IsEmpty() const

{

return (size == 0);

}

Implementation of bool IsFull() const

We assume that the heap cannot be exhausted, so IsFull() always returns false.

bool OrderedList::IsFull() const

{

return false;

}

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

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

{

for ( Node* location = front; location != NULL; location = location->next )

{

if ( key == location->key )

{

info = location->info;

return true;

}

if ( key < location->key )

return false;

}

return false;

}

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

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

{

Node* backup = NULL;

for ( Node* location = front; location != NULL; location = location->next )

{

if ( key == location->key )

return false;

if ( key < location->key )

break;

backup = location;

}

// Create and fill in the new node

Node* newPtr = new Node;

newPtr->key = key;

newPtr->info = info;

// Insert between *backup and *location

newPtr->next = location;

if( backup == NULL )

front = newPtr;

else

backup->next = newPtr;

size++;

return true;

}
Implementation of bool Delete( /* in */ int key )

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

{

Node* backup = NULL;

for ( Node* location = front; location != NULL; location = location->next )

{

if ( key == location->key )

{

if ( backup == NULL )

front = location->next;

else

backup->next = location->next;

delete location;

size--;

return true;

}

if ( key < location->key )

return false;

backup = location;

}

return false;

}

Implementation of ordered list traversal

int OrderedList::Size() const

{

return size;

}

void OrderedList::Reset()

{

current = front;

}

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

{

key = current->key;

info = current->info;

current = current->next;

}