Overview |
Topics |
|
Linked lists are non-contiguous data structures 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. This means that the list nodes can be processed in two directions. Singly linked lists have less overhead because each node only has to maintain a single pointer to the next node in sequence, but the nodes can only be processed in one direction.
Unlike arrays, where the array elements must be the same size, linked lists can handle differently sized data in each node since they do not use contiguous memory. The nodes in a linked list can be resized, rearranged, randomly inserted and deleted as needed. However, searching a linked list can become very slow if the list becomes extremely long due to numerous insertions. Trees offer the same flexibility of linked list and much faster searching by allowing left and right movements.
A node's pointer to the next node in sequence is usually referred to as the next pointer. Its pointer to the previous node in sequence is usually referred to as the prev pointer. Inserting a node into a doubly linked list requires the new node's next pointer to point to the node after it and its prev pointer to point the node before it. The next pointer in the node before the new node must point the new node. The prev pointer in the node after the new node must point to the new node. When removing a node from the list, the next pointer in the node prior to the node being removed is assigned to the next node in sequence after the node being removed. The prev pointer in the node after the node being removed is assigned to the node in front of the node being removed. After the node is detached from the list it can be de-allocated from memory. If the list is null-terminated the last node in the list will always point to zero. If the last node in the list points to the first node in the list, the list is called a circular linked list.
The DNodeBase class is a base class for doubly linked list node classes. This implementation separates the nodes from the data stored in the list by storing pointers to objects in the containers, rather than the objects themselves. This forms a heterogeneous container capable of handling any type of node data. The derived class supplies the node data, allowing the DNodeBase class to serve as base class for any node class.
class DNodeBase
{
protected:
friend class DLListBase;
protected:
void InsertAfter(DNodeBase *Node);
void InsertBefore(DNodeBase *Node);
DNodeBase *Rmv();
void SelfRef() { Prior = this; Next = this; }
protected:
DNodeBase *Prior; // Pointer the previous node in sequence
DNodeBase *Next; // Pointer to the next node in sequence
};
void DNodeBase::InsertAfter(DNodeBase *Node) - Protected member function used to insert the specified node after this one.
void DNodeBase::InsertBefore(DNodeBase *Node) - Protected member function used to insert the specified node before this one.
DNodeBase *DNodeBase::Rmv() - Protected member function used to detach this node from the list. This function assumes that both the next and prev pointers are not a null value. Returns a pointer to the node detached.
void DNodeBase::SelfRef() - Protected member function used to make this node's next and prev pointers reference themselves. This function was added to help support circular lists.
The DLListBase class is an abstract base derived from the DNodeBase class. It is implemented with no data and can be used for many singly linked list classes to manipulate DNodeBase pointers. This class inherits the next and prior pointers, which are interpreted to point to the back and front of the list, respectively. The list itself becomes the list header node. The header node is used as flag to test when the end of the list has been reached during a walk operation and allows new nodes to be inserted before the first node in the list.
DLListBase::DLListBase() - Class constructor used to construct a new, empty list.
virtual DLListBase::~DLListBase() - - Class destructor provided for virtuality. The class destructor does not do anything. It cannot reliably free the nodes from memory, because the node data types are not known.
virtual void DLListBase::Clear() - Public member function used to clear the list.
int DLListBase::IsEmpty() const - Public member function that returns true if the list is empty. A list is empty if its next and prev pointers point to the list itself.
int DLListBase::IsHeader(const DNodeBase *Node) const - Public member function that returns true if the specified node is the head of the list. The header node is used as flag to test when the end of the list has been reached during a walk operation.
virtual DNodeBase *DLListBase::DupNode(const DNodeBase *Node) - Protected pure virtual member function intended to be overridden in the derived class to copy-construct a node holding the proper type of data defined in the derived class.
virtual void DLListBase::FreeNode(DNodeBase *Node) - Protected pure virtual member function intended to be overridden in the derived class to de-allocate a node from memory after it has been detached from the list.
virtual void DLListBase::MakeEmpty() - Protected virtual member function used to make the list empty by making the header node point to the list itself. This is an internal function that assumes there are no nodes currently in the list, (except for the header, which is always there.)
DNodeBase *DLListBase::GetHeader() - Protected member function that returns a pointer to the header node.
const DNodeBase *DLListBase::GetHeader() const - Protected member function that returns a pointer to the header node.
DNodeBase *DLListBase::GetFront() - Protected member function that returns a pointer to the first node in the list. Returns a pointer to the header node if the list is empty.
const DNodeBase *DLListBase::GetFront() const - Protected member function that returns a pointer to the first node in the list. Returns a pointer to the header node if the list is empty.
DNodeBase *DLListBase::GetBack() - Protected member function that returns a pointer to the last node in the list. Returns a pointer to the header node if the list is empty.
const DNodeBase *DLListBase::GetBack() const - Protected member function that returns a pointer to the last node in the list. Returns a pointer to the header node if the list is empty.
void DLListBase::InsertBefore(DNodeBase *A, DNodeBase *B) -Protected member function used to insert node B before node A.
void DLListBase::InsertAfter(DNodeBase *A, DNodeBase *B) - Protected member function used to insert node B after node A.
void DLListBase::AttachToFront(DNodeBase *Node) - Protected member function used to insert the specified node after header and before the rest of the nodes in the list.
void DLListBase::AttachToBack(DNodeBase *Node) - Protected member function used to insert the specified node after the current last node in the list.
DNodeBase *DLListBase::Rmv(DNodeBase *Node) - Protected member function used to detach the specified node from the list. This function assumes that the node is already in the list. If the node is the header a null pointer is returned, or else the to pointer the detached node is returned.
DNodeBase *DLListBase::RmvFront() - Protected member function used to detach the first node from the list. This function assumes that the node is already in the list. If the node is the header a null pointer is returned, or else the pointer to the detached node is returned.
DNodeBase *DLListBase::RmvBack() - Protected member function used to detach the last node from the list. This function assumes that the node is already in the list. If the node is the header a null pointer is returned, or else the pointer to the detached node is returned.
int DLListBase::Copy(const DLListBase &List) - Protected member function used to copy the nodes from the specified list into this list. Clears the current nodes from this list before copying. Returns one if successful or zero if node allocation fails.
int DLListBase::Cat(const DLListBase &List) - Protected member function used to concatenate the specified list onto the end of the list. Returns one if successful or zero if the new nodes couldn't be allocated or an attempt is made to concatenate the list onto itself.
The DNode class is a generic doubly-linked list node class derived from the DNodeBase class. This class adds the node data to the list. NOTE: Both a template and non-template versions are supplied. Templates were used to allow the node class to handle numerous data types without having to provide a different version for each data type used. The non-template version of the node class, ChNode, uses a type definition to define char * as its data type. If your application cannot use templates, you can code the ChNode and ChList classes directly for the data type being used by changing the DLTYPE definition to the data type being used. Also the ChList::Find() would have to be re-coded to perform a comparison on the data type being used.
template<class TYPE>
class DNode : public DNodeBase
{
public:
DNode() { } // Implicitly call default constructor for Data
DNode(const TYPE &X) : Data(X) { } // Call copy constructor
public:
DNode<TYPE> *GetPrior() { return (DNode<TYPE> *)Prior; }
const DNode<TYPE> *GetPrior() const { return (DNode<TYPE> *)Prior; }
DNode<TYPE> *GetNext() { return (DNode<TYPE> *)Next; }
const DNode<TYPE> *GetNext() const { return (DNode<TYPE> *)Next; }
public:
TYPE Data;
};
DNode<TYPE> *DNode<TYPE>::GetNext() - Public member function that returns the next pointer typecast as a pointer to a DNode object.
DNode<TYPE> *DNode<TYPE>::GetPrior() - Public member function that returns the prev pointer typecast as a pointer to a DNode object.
The DLList class is derived from the DLListBase base class. It serves as a type-specific interface for the DLListBase class. Most of the DLList functions are typecasting interfaces. NOTE: Both a template and non-template versions are supplied. Templates were used to allow the linked list class to handle numerous data types without having to provide a different version for each data type used. The non-template version of the node class, ChList, uses a type definition to define char * as its data type. If your application cannot use templates, you can code the ChNode and ChList classes directly for the data type being used by changing the DLTYPE type definition to the data type being used. Also the ChList::Find() would have to be re-coded to perform a comparison on the type being used.
DLList<TYPE>::DLList() - Class constructor used to construct an empty list.
virtual DLList<TYPE>::~DLList() - Class destructor responsible for clearing the list.
DLList<TYPE>::DLList(const DLList<TYPE> &X) - Class copy constructor used to copy all of the nodes of the specified DLList object into the object that invoked the call.
void DLList<TYPE>::operator=(const DLList<TYPE> &X) - Class assignment operator used to turn this list into a copy of the specified DLList object. This overloaded assignment operator does not allow the object to assign itself to itself or allow chained assignment.
int DLList<TYPE>::Copy(const DLList<TYPE> &List) - Public member function used to copy the nodes from the specified list into this list providing the proper typecasting. Clears the current nodes from this list first before copying. Returns one if successful or zero if node allocation fails.
int DLList<TYPE>::Cat(const DLList<TYPE> &X) - Public member function used to concatenate the specified list onto the end of the list providing the proper typecasting. Returns one if successful or zero if the new nodes couldn't be allocated or an attempt is made to concatenate the list onto itself.
const DNode<TYPE> *DLList<TYPE>::Find(const TYPE &X, const DNode<TYPE> *ptr=0) const - Public member function used to find a node in the list node having an element that matched X. Returns a pointer to the node or zero if no match is found.
DNode<TYPE> *DLList<TYPE>::Find(const TYPE &X, DNode<TYPE> *ptr=0) - Public member function used to find a node in the list node having an element that matched X. Returns a pointer to the node or zero if no match is found.
int DLList<TYPE>::Delete(DNode<TYPE> *Node, TYPE *X = 0) - Public member function used to detach and delete the specified node from the list. This function assumes that the node already exists in the list. If the node to detach is the list header, the operation is disallowed and a zero is returned. Returns true if successful. If a value is specified for X, a copy of X is loaded into the node after it is detached and before it is deleted.
int DLList<TYPE>::DeleteFront(TYPE *X = 0) - Public member function used to detach and delete the first node from the list. This function assumes that the node already exists in the list. If the node to detach is the list header, the operation is disallowed and a zero is returned. Returns true if successful. If a value is specified for X, a copy of X is loaded into the node after it is detached and before it is deleted.
int DLList<TYPE>::DeleteBack(TYPE *X = 0) - Public member function used to detach and delete the last node from the list. This function assumes that the node already exists in the list. If the node to detach is the list header, the operation is disallowed and a zero is returned. Returns true if successful. If a value is specified for X, a copy of X is loaded into the node after it is detached and before it is deleted.
DNode<TYPE> *DLList<TYPE>::StoreNode(const TYPE &X) - Public member function used to create a new node containing a copy of X and add the node to the back of the list. Returns a pointer to the node added or zero if the node allocation fails.
DNode<TYPE> *DLList<TYPE>::AddToFront(const TYPE &X) - Public member function used to create a new node containing a copy of X and add the node to the front of the list. Returns a pointer to the node added or zero if the node allocation fails.
DNode<TYPE> *DLList<TYPE>::AddToBack(const TYPE &X) - Public member function used to create a new node containing a copy of X and add the node to the back of the list. Returns a pointer to the node added or zero if the node allocation fails.
DNode<TYPE> *DLList<TYPE>::AddBefore(const TYPE &X, DNode<TYPE> *Node) - Public member function used to create a new node containing a copy of X and add the new node before the specified node. This function assumes that the specified node already exists in the list. Returns a pointer to the node added or zero if the node allocation fails.
DNode<TYPE> *DLList<TYPE>::AddAfter(const TYPE &X, DNode<TYPE> *Node) - Public member function used to create a new node containing a copy of X and add the new node after the specified node. This function assumes that the specified node already exists in the list. Returns a pointer to the node added or zero if the node allocation fails.
DNode<TYPE> *DLList<TYPE>::GetHeader() - Public member function that returns a pointer to the list header typecasting it to a DNode type. This function is provided for typecasting convenience when iterating through a list, and cannot be used with any of the DNode class members.
const DNode<TYPE> *DLList<TYPE>::GetHeader() const - Public member function that returns a pointer to the list header typecasting it to a DNode type. This function is provided for typecasting convenience when iterating through a list, and cannot be used with any of the DNode class members.
DNode<TYPE> *DLList<TYPE>::GetFront() - Public member function that returns a pointer to the first node in the list with the proper typecasting. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from DNodeBase, is not a DNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
DNode<TYPE> *DLList<TYPE>::GetBack() - Public member function that returns a pointer to the last node in the list with the proper typecasting. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from DNodeBase, is not a DNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
const DNode<TYPE> *DLList<TYPE>::GetFront() const - Public member function that returns a pointer to the first node in the list with the proper typecasting. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from DNodeBase, is not a DNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
const DNode<TYPE> *DLList<TYPE>::GetBack() const - Public member function that returns a pointer to the last node in the list with the proper typecasting. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from DNodeBase, is not a DNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
int DLList<TYPE>::IsHeader(const DNode<TYPE> *Node) const - Public member function that returns true is the specified node is the head of the list. The header node is used as flag to test when the end of the list has been reached during a walk operation.
TYPE *DLList<TYPE>::GetFrontNode() - Public member function that returns a pointer to the node data of the front node or zero if the list is empty.
const TYPE *DLList<TYPE>::GetFrontNode() const - Public member function that returns a pointer to the node data of the front node or zero if the list is empty.
TYPE *DLList<TYPE>::GetBackNode() - Public member function that returns a pointer to the node data of the back node or zero if the list is empty.
const TYPE *DLList<TYPE>::GetBackNode() const - Public member function that returns a pointer to the node data of the back node or zero if the list is empty.
void DLList<TYPE>::InsertBefore(DNode<TYPE> *A, DNode<TYPE> *B) - Public member function used to insert node B before node A, with the proper typecasting.
void DLList<TYPE>::InsertAfter(DNode<TYPE> *A, DNode<TYPE> *B) - Public member function used to insert node B after node A, with the proper typecasting.
void DLList<TYPE>::AttachToFront(DNode<TYPE> *Node) - Public member function used to insert the specified node after header and before the rest of the nodes in the list with the proper typecasting.
void DLList<TYPE>::AttachToBack(DNode<TYPE> *Node) - Public member function used to insert the specified node after the current last node in the list with the proper typecasting.
DNode<TYPE> *DLList<TYPE>::RmvFront() - Public member function used to detach the first node from the list with the proper typecasting. This function assumes that the node is already in the list. If the node is the header a null pointer is returned, or else the pointer to the detached node is returned.
DNode<TYPE> *DLList<TYPE>::Rmv(DNode<TYPE> *Node) - Public member function used to detach the specified node from the list with the proper typecasting. This function assumes that the node is already in the list. If the node is the header a null is returned, or else the pointer to the detached node is returned.
DNode<TYPE> *DLList<TYPE>::RmvBack() - Public member function used to detach the last node from the list with the proper typecasting. This function assumes that the node is already in the list. If the node is the header a null is returned, or else the pointer to the detached node is returned
virtual DNode<TYPE> *DLList<TYPE>::AllocNode(const TYPE &X) - Protected member function, overriding the base class version, used to allocate a new node, storing a copy of X with it. This function is declared virtual in case a derived list allocates nodes some other way.
virtual DNodeBase *DLList<TYPE>::DupNode(const DNodeBase *Node) - Protected member function, overriding the base class version, used to copy construct a node holding the proper type of data. This function assumes that the specified node is a DNode type. This function is declared virtual in case a derived list allocates nodes some other way.
virtual void DLList<TYPE>::FreeNode(DNodeBase *Node) - Protected member function, overriding the base class version, used to delete the specified node. This function assumes that the specified node is a DNode type. This function is declared virtual in case a derived list de-allocates nodes some other way.
int DLList<TYPE>::operator+=(const DLList<TYPE> &X) - Overloaded member operator used to add a copy of the specified list onto the end of this list.