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 singly linked list each node stores a data item and a single pointer to the next node in sequence. This means that the list can only be processed in one direction. A doubly linked list allows the node data to be processed in two directions by storing an extra pointer with each node. 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. Insertion works by copying the current node's next pointer into the next pointer of the new node, and then having the current node point to the new node. This ensures that the current node will point to the new node in the list and the new node will point to the next node in sequence. 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. 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. After the node is detached from the list it can be de-allocated from memory.
The SNodeBase class is a base class for singly 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 SNodeBase class to serve as base class for any node class.
class SNodeBase
{
protected:
friend class SLListBase;
protected:
void InsertAfter(SNodeBase *Node);
SNodeBase *RmvNext();
void SelfRef() { Next = this; }
protected:
SNodeBase *Next;
};
void SNodeBase::InsertAfter(SNodeBase *Node) - Protected member function used to insert the specified node after this one.
SNodeBase *SNodeBase::RmvNext() - Protected member function used to remove the node following this node, giving this node a new next node in the process. This function assumes that the next pointer is not a null value. Returns a pointer to the node detached.
void SNodeBase::SelfRef() - Protected member function used to make this node's next pointer reference itself. This function was added to help support circular lists.
The SLListBase class is an abstract base derived from the SNodeBase class. It is implemented with no data and can be used for many singly linked list classes to manipulate SNodeBase pointers. This class inherits the next pointer, which is interpreted to point to the front of the list. The list itself becomes the list's 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. The SLListBase class adds a back pointer that always points to the last node in the list. This allows nodes to be inserted to the end of the list without having to scan the entire list.
SLListBase::SLListBase() - Class constructor used to construct a new, empty list.
virtual SLListBase::~SLListBase() - Class destructor provided for virtuality. The class destructor does not do anything. It cannot reliably free nodes from memory because the node date types are not known.
virtual void SLListBase::Clear() - Public member function used to clear the list.
int SLListBase::IsEmpty() const - Public member function that returns true if the list is empty. A list is empty if its next pointer points to the list itself.
int SLListBase::IsHeader(const SNodeBase *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 SNodeBase *SLListBase::DupNode(const SNodeBase *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 SLListBase::FreeNode(SNodeBase *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 SLListBase::MakeEmpty() - Protected virtual member function used to make the list empty by making the header node point to itself. Also points the back pointer to the header. This is an internal function that assumes there are no nodes currently in the list, (except for the header, which is always there.)
SNodeBase *SLListBase::GetHeader() - Protected member function that returns a pointer to the header node.
const SNodeBase *SLListBase::GetHeader() const - Protected member function that returns a pointer to the header node of the list.
SNodeBase *SLListBase::GetFront() - Protected member function that returns a pointer to the first node of the list. Returns a pointer to the header node if the list is empty.
const SNodeBase *SLListBase::GetFront() const - Protected member function that returns a pointer to the first node of the list. Returns a pointer to the header node if the list is empty.
SNodeBase *SLListBase::GetBack() - Protected member function that returns a pointer to the last node of the list. Returns a pointer to the header node if the list is empty.
const SNodeBase *SLListBase::GetBack() const - Protected member function that returns a pointer to the last node of the list. Returns a pointer to the header node if the list is empty.
void SLListBase::InsertAfter(SNodeBase *A, SNodeBase *B) - Protected member function used to attach node B after node A, which is presumed to reside in the list. A check is made to see if A is the back node. If so, then B becomes the back node.
void SLListBase::AttachToFront(SNodeBase *Node) - Protected member function used to insert the specified node after header node and before the rest of the nodes in the list.
void SLListBase::AttachToBack(SNodeBase *Node) - Protected member function used to insert the specified node after the current last node in the list.
SNodeBase *SLListBase::RmvNext(SNodeBase *Node) - Protected member function used to detach the node following this node, pointing this node a new next node in the process. This function assumes that this node's next pointer is not a null value. If the node to detach is the list header, the operation is disallowed, and a null pointer is returned. Returns a pointer to the node detached.
SNodeBase *SLListBase::RmvFront() - Protected member function used to detach the first node from the list.
int SLListBase::Copy(const SLListBase &List) - Protected member function used to copy the nodes from the specified list into this list. Clears the current nodes from this list first before copying. Returns one if successful or zero if node allocation fails.
int SLListBase::Cat(const SLListBase &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 could not be allocated or an attempt is made to concatenate the list onto itself.
The SNode class is a generic singly linked list node class derived from the SNodeBase class. This class adds the node data to the list. NOTE: Both a template and non-template versions of this class 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, ChSNode, uses a type definition to define char * as its data type. If your application cannot use templates, you can code the ChSNode and ChSList classes directly for the data type being used by changing the SLTYPE type definition to the data type being used. Also the ChSList::Find() would have to be re-coded to perform a comparison on the data type being used.
template<class TYPE>
class SNode: public SNodeBase
{
public:
SNode() { } // Implicitly call default constructor for Data
SNode(const TYPE &X) : Data(X) { } // Call copy constructor for TYPE
public:
SNode<TYPE> *GetNext() { return (SNode<TYPE> *)Next; }
const SNode<TYPE> *GetNext() const { return (SNode<TYPE> *)Next; }
public:
TYPE Data;
};
SNode<TYPE> *SNode<TYPE>::GetNext() - Public member function that returns the next pointer typecast as a pointer to an SNode object.
The SLList class is derived from the SLListBase base class. It serves as a type-specific interface for the SLListBase class. Most of the SLList functions are typecasting interfaces. NOTE: Both a template and non-template versions of this class 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, ChSList, uses a type definition to define char * as its data type. If your application cannot use templates, you can code the ChSNode and ChSList classes directly for the data type being used by changing the SLTYPE type definition to the data type being used. Also the ChSList::Find() would have to be re-coded to perform a comparison on the data type being used.
SLList<TYPE>::SLList() - Class constructor used to construct an empty list.
virtual SLList<TYPE>::~SLList() - Class destructor responsible for clearing the list.
SLList<TYPE>::SLList(const SLList<TYPE> &X) - Class copy constructor used to copy all of the nodes of the specified SLList object into the object that invoked the call.
void SLList<TYPE>::operator=(const SLList<TYPE> &X) - Class assignment operator used to turn this list into a copy of the specified SLList object. This overloaded assignment operator does not allow the object to assign itself to itself or allow chained assignment.
int SLList<TYPE>::Copy(const SLList<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 SLList<TYPE>::Cat(const SLList<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 SNode<TYPE> *SLList<TYPE>::Find(const TYPE &X, const SNode<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.
SNode<TYPE> *SLList<TYPE>::Find(const TYPE &X, SNode<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 SLList<TYPE>::DeleteNext(SNode<TYPE> *Node, TYPE *X = 0) - Public member function used to detach and delete the node following this node, pointing this node a new next node in the process. This function assumes that this node's next pointer is not a null value. 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 SLList<TYPE>::DeleteFront(TYPE *X = 0) - Public member function used to detach and delete the first node from 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.
SNode<TYPE> *SLList<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.
SNode<TYPE> *SLList<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.
SNode<TYPE> *SLList<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.
SNode<TYPE> *SLList<TYPE>::AddAfter(const TYPE &X, SNode<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.
SNode<TYPE> *SLList<TYPE>::GetHeader() - Public member function that returns a pointer to the list header, typecasting if to an SNode type. This function is provided for typecasting convenience when iterating through a list and cannot be used by SNode class members.
const SNode<TYPE> *SLList<TYPE>::GetHeader() const - Public member function that returns a pointer to the list header, typecasting if to an SNode type. This function is provided for typecasting convenience when iterating through a list and cannot be used by SNode class members.
SNode<TYPE> *SLList<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 SNodeBase, is not a SNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
SNode<TYPE> *SLList<TYPE>::GetBack() - Public member function that returns a pointer to the last node in the list. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from SNodeBase, is not a SNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
const SNode<TYPE> *SLList<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 SNodeBase, is not a SNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
const SNode<TYPE> *SLList<TYPE>::GetBack() cons - Public member function that returns a pointer to the last node in the list. NOTE: A pointer to the header node will be returned if the list is empty. The header node, while being derived from SNodeBase, is not a SNode type and does not have an info member. Therefore the list cannot be empty when calling this function.
int SLList<TYPE>::IsHeader(const SNode<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 *SLList<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 *SLList<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 *SLList<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 *SLList<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 SLList<TYPE>::InsertAfter(SNode<TYPE> *A, SNode<TYPE> *B) - Public member function used to attach node B after node A, which is presumed to reside in the list, with the proper typecasting. A check is made to see if A is the back. If so, then B becomes the back.
void SLList<TYPE>::AttachToFront(SNode<TYPE> *Node) - Public member function used to insert the specified node after header node and before the rest of the nodes in the list with the proper typecasting.
void SLList<TYPE>::AttachToBack(SNode<TYPE> *Node) - Public member function used to insert the specified node after the current last node in the list with the proper typecasting.
SNode<TYPE> *SLList<TYPE>::RmvFront() - Public member function used to detach the first node from the list. Returns a pointer to the node detached with the proper typecast.
SNode<TYPE> *SLList<TYPE>::RmvNext(SNode<TYPE> *Node) - Public member function used to detach the node following this node, pointing this node to a new next node in the process. This function assumes that this node's next pointer is not a null value. If the node to detach is the list header, the operation is disallowed and a null is returned. Returns a pointer to the node detached with the proper typecast.
virtual SNode<TYPE> *SLList<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 SNodeBase *SLList<TYPE>::DupNode(const SNodeBase *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 SNode type. This function is declared virtual in case a derived list allocates nodes some other way.
virtual void SLList<TYPE>::FreeNode(SNodeBase *Node) - Protected member function, overriding the base class version, used to delete the specified node. This function assumes that the specified node is a SNode type. This function is declared virtual in case a derived list de-allocates nodes some other way.
int SLList<TYPE>::operator+=(const SLList<TYPE> &X) - Overloaded member operator used to add a copy of the specified list onto the end of this list.