Linked List Class

Topics:

The gxListNode and gxList classes makeup a generic doubly linked-list class that includes stack and queue functions.

A linked-list is a non-contiguous data structure used to link a collection of nodes together. A node is a container used to store pointers to other nodes and some type of data. In a doubly linked list each node stores a data item and pointers to the next node and previous node in sequence allowing the list nodes to be processed in two directions.

A stack is a data structure that stores nodes in last-in-first-out (LIFO) order using push and pop operations. A push operation adds a new node to the top of the stack and a pop operation removes a node from the top of the stack.

A queue is a data structure that stores node in first-in-first-out (FIFO) order using insert and extract operations. An insert operation adds a new node to tail of the queue and an extract operation removes a node from the head of the queue.

Data Structures

The linked-list node structure is a generic class used to store the node data, previous and next pointers.

template<class TYPE>
class gxListNode
{
public:
  gxListNode() { next = prev = 0; }
  gxListNode(TYPE &X) : data(X) { next = prev = 0; }
  ~gxListNode() { }

public: 
  TYPE data; // Node data
  gxListNode<TYPE> *next; // Pointer to the next node in the list
  gxListNode<TYPE> *prev; // Pointer to the previous node in the list
};

Functions

gxList::gxList()
gxList::~gxList()
gxList::Add()
gxList::AddAfter()
gxList::AddBefore()
gxList::AddToBack()
gxList::AddToFront()
gxList::AllocNode()
gxList::ClearList()
gxList::DestroyList()
gxList::DetachNode()
gxList::FreeNode()
gxList::GetHead()
gxList::GetTail()
gxList::InsertAfter()
gxList::InsertAtHead()
gxList::InsertAtTail()
gxList::InsertBefore()
gxList::IsEmpty()
gxList::MakeEmpty()
gxList::MoveAfter()
gxList::MoveBefore()
gxList::MoveToBack()
gxList::MoveToFront()
gxList::Remove()
gxList::RemoveHead()
gxList::RemoveTail()

Stack Functions:
gxList::Pop()
gxList::Push()

Queue Functions:
gxList::Insert()
gxList::Extract()

gxList::gxList() - Default class constructor.

gxList::gxList(const gxList<TYPE> &ob) - Private class copy constructor used to disallow copying.

void gxList::operator=(const gxList<TYPE> &ob) - Private assignment operator used to disallow assignment.

gxList::~gxList() - Class destructor responsible for clearing the list when a list object is destroyed.

gxListNode<TYPE> *gxList::Add(TYPE &X) - Public member function used to add a new list node to the back of the list. Returns a pointer to the newly created node or a null value if heap space could not be allocated for the node.

gxListNode<TYPE> *gxList::AddAfter(gxListNode<TYPE> *pos, TYPE &X) - Public member function used to add a list node after the specified node. Returns a pointer to the newly created node or a null value if heap space could not be allocated for the node.

gxListNode<TYPE> *gxList::AddBefore(gxListNode<TYPE> *pos, TYPE &X) - Public member function used to add a list node before the specified node. Returns a pointer to the newly created node or a null value if heap space could not be allocated for the node.

gxListNode<TYPE> *gxList::AddToBack(TYPE &X) - Public member function used to add a list node to the back of the list. Returns a pointer to the newly created node or a null value if heap space could not be allocated for the node.

gxListNode<TYPE> *gxList::AddToFront(TYPE &X) - Public member function used to add a list node to the front of the list. Returns a pointer to the newly created node or a null value if heap space could not be allocated for the node.

gxListNode<TYPE> *gxList::AllocNode(TYPE &X) - Private member function used to allocate a new list node.

void gxList::ClearList() - Public member function used to clear the list.

void gxList::DestroyList() - Public member function used to clear the list and destroy the node data.

void gxList::DetachNode(gxListNode<TYPE> *n) - Public member function used to detach the node from its current location.

int gxList::Extract(TYPE &X) - Public queue operation used to extract a list node from the list. Returns true if the node was extracted.

int gxList::FreeNode(gxListNode<TYPE> *n, TYPE &X) - Private member function used to free the memory location of the node without releasing the nodes data pointer. NOTE: This function assumes that the node has already been detached from the list. Returns a true if the node was deleted.

gxListNode<TYPE> *gxList::GetHead() - Public member function that returns the head of the list.

gxListNode<TYPE> *gxList::GetTail() - Public member function that returns the tail of the list.

gxListNode<TYPE> *gxList::Insert(TYPE &X) - Public queue operation used to insert a list node into the list. Returns a pointer to the node or a null value if memory for the node could not be allocated.

void gxList::InsertAfter(gxListNode<TYPE> *pos, gxListNode<TYPE> *n) - Public member function used to insert a new or detached node after the node residing at the specified location.

void gxList::InsertAtHead(gxListNode<TYPE> *n) - Public member function used to insert a node at the head of the list.

void gxList::InsertAtTail(gxListNode<TYPE> *n) - Public member function used to insert a node at the tail of the list.

void gxList::InsertBefore(gxListNode<TYPE> *pos, gxListNode<TYPE> *n) - Public member function used to insert a new or detached node before the node residing at the specified location.

int gxList::IsEmpty() - Public member function that returns true if the list is empty.

void gxList::MakeEmpty() - Public member function used to reset the head and tail pointers. NOTE: This function should only be called only if all the nodes have been removed.

void gxList::MoveAfter(gxListNode<TYPE> *pos, gxListNode<TYPE> *n) - Public member function used to move an existing node after the node residing at the specified location.

void gxList::MoveBefore(gxListNode<TYPE> *pos, gxListNode<TYPE> *n) - Public member function used to move an existing node before the node residing at the specified location.

void gxList::MoveToBack(gxListNode<TYPE> *n) - Public member function used to move the specified node to the back of the list.

void gxList::MoveToFront(gxListNode<TYPE> *n) - Public member function used to move the specified node to the front of the list.

int gxList::Pop(TYPE &X) - Public stack operation used to pop a list node from the list. Returns a true if the node was popped.

gxListNode<TYPE> *gxList::Push(TYPE &X) - Public stack operation used to push a list node into the list. Returns a pointer to the node or a null value if memory for the node could not be allocated.

int gxList::Remove(gxListNode<TYPE> *n, TYPE &X) - Public member function used to remove the specified node from the list and pass back the node data. Returns true if the node was removed.

int gxList::Remove(gxListNode<TYPE> *n) - Public member function used to remove the specified node from the list. Returns true if the node was removed.

int gxList::RemoveHead(TYPE &X) - Public member function used to remove the first node in the list. Returns true if the node was removed.

int gxList::RemoveTail(TYPE &X) - Public member function used to remove the last node in the list. Returns true if the node was removed.

End Of Document