Topics
:Overview
vbDNode Base Class
vbDLList Base Class
vbDNode Class
Doubly Linked List Class
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 c alled a circular linked list.
The vbDNodeBase 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 vbDNodeBase class to serve as base class for any node class.
class vbDNodeBase { protected: friend class vbDLListBase; protected: void InsertAfter(vbDNodeBase *Node); void InsertBefore(vbDNodeBase *Node); vbDNodeBase *Rmv(); void SelfRef() { Prior = this; Next = this; } protected: vbDNodeBase *Prior; // Pointer the previous node in sequence vbDNodeBase *Next; // Pointer to the next node in sequence };
vbDNodeBase::InsertAfter()
vbDNodeBase::InsertBefore()
vbDNodeBase::Rmv()
vbDNodeBase::SelfRef()
void vbDNodeBase::InsertAfter(vbDNodeBase *Node)
- Protected member function used to insert the specified node after this one.void vbDNodeBase::InsertBefore(vbDNodeBase *Node)
- Protected member function used to insert the specified node before this one.vbDNodeBase *vbDNodeBase::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. - 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 vbDLListBase class is an abstract base derived from the vbDNodeBase class. It is implemented with no data and can be used for many doubly linked list classes to manipulate vbDNodeBase 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.
vbDLListBase::vbDLListBase()
vbDLListBase::~vbDLListBase()
vbDLListBase::AttachToBack()
vbDLListBase::AttachToFront()
vbDLListBase::Cat()
vbDLListBase::Clear()
vbDLListBase::Copy()
vbDLListBase::DupNode()
vbDLListBase::FreeNode()
vbDLListBase::GetBack()
vbDLListBase::GetFront()
vbDLListBase::GetHeader()
vbDLListBase::InsertAfter()
vbDLListBase::InsertBefore()
vbDLListBase::IsEmpty()
vbDLListBase::IsHeader()
vbDLListBase::MakeEmpty()
vbDLListBase::Rmv()
vbDLListBase::RmvBack()
vbDLListBase::RmvFront()
virtual vbDLListBase::~vbDLListBase()
- Class destructor provided for virtuality. The class destructor does not perform any action. It cannot reliably free the nodes from memory, because the node data types are not known.void vbDLListBase::AttachToBack(vbDNodeBase *Node)
- Protected member function used to insert the specified node after the current last node in the list.void vbDLListBase::AttachToFront(vbDNodeBase *Node)
- Protected member function used to insert the specified node after header and before the rest of the nodes in the list.int vbDLListBase::Cat(const vbDLListBase &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.virtual void vbDLListBase::Clear()
- Public member function used to clear the list.int vbDLListBase::Copy(const vbDLListBase &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.virtual vbDNodeBase *vbDLListBase::DupNode(const vbDNodeBase *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 vbDLListBase::FreeNode(vbDNodeBase *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.vbDNodeBase *vbDLListBase::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.vbDNodeBase *vbDLListBase::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.vbDNodeBase *vbDLListBase::GetHeader()
- Protected member function that returns a pointer to the header node.void vbDLListBase::InsertAfter(vbDNodeBase *A, vbDNodeBase *B)
Protected member function used to insert node "B" after node "A".void vbDLListBase::InsertBefore(vbDNodeBase *A, vbDNodeBase *B)
- Protected member function used to insert node "B" before node "A". - 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 vbDLListBase::IsHeader(const vbDNodeBase *Node)
- 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 void vbDLListBase::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.)vbDNodeBase *vbDLListBase::Rmv(vbDNodeBase *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. functionvbDNodeBase *vbDLListBase::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.vbDNodeBase *vbDLListBase::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.The vbDNode class is a generic doubly-linked list node class derived from the vbDNodeBase class. This class adds the node data to the list. NOTE: A template version is supplied as part of the class library. 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. If your application cannot use templates non-template versions can be easily constructed by inheriting the vbDNodeBase class.
template<class TYPE> class vbDNode : public vbDNodeBase { public: vbDNode() { } // Implicitly call default constructor for Data vbDNode(const TYPE &X) : Data(X) { } // Call copy constructor public: vbDNode<TYPE> *GetPrior() { return (vbDNode<TYPE> *)Prior; } vbDNode<TYPE> *GetPrev() { return (vbDNode<TYPE> *)Prior; } vbDNode<TYPE> *GetNext() { return (vbDNode<TYPE> *)Next; } public: TYPE Data; };
vbDNode::GetNext()
vbDNode::GetPrev()
vbDNode::GetPrior()
vbDNode<TYPE> *vbDNode::GetNext()
- Public member function that returns the next pointer typecast as a pointer to a vbDNode object.vbDNode<TYPE> *vbDNode::GetPrev()
- Public member function that returns the prev pointer typecast as a pointer to a vbDNode object.vbDNode<TYPE> *vbDNode::GetPrior()
- Public member function that returns the prev pointer typecast as a pointer to a vbDNode object.The vbDLList class is derived from the vbDLListBase base class. It serves as a type-specific interface for the vbDLListBase class. Most of the vbDLList functions are typecasting interfaces. NOTE: A template version is supplied as part of the class library. 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. If your application cannot use templates non-template versions can be easily constructed by inheriting the vbDLListBase class.
vbDLList::vbDLList()
vbDLList::~vbDLList()
vbDLList::AddAfter()
vbDLList::AddBefore()
vbDLList::AddToBack()
vbDLList::AddToFront()
vbDLList::AllocNode()
vbDLList::AttachToBack()
vbDLList::AttachToFront()
vbDLList::Cat()
vbDLList::Copy()
vbDLList::Delete()
vbDLList::DeleteBack()
vbDLList::DeleteFront()
vbDLList::DupNode()
vbDLList::Find()
vbDLList::FreeNode()
vbDLList::GetBack()
vbDLList::GetBackNode()
vbDLList::GetFront()
vbDLList::GetFrontNode()
vbDLList::GetHeader()
vbDLList::InsertAfter()
vbDLList::InsertBefore()
vbDLList::IsHeader()
vbDLList::Rmv()
vbDLList::RmvBack()
vbDLList::RmvFront()
vbDLList::StoreNode()
vbDLList::operator+=()
vbDLList::operator=()
vbDLList::vbDLList(const vbDLList<TYPE> &X)
- Class copy constructor used to copy all of the nodes of the specified vbDLList object into the object that invoked the call. - Class destructor responsible for clearing the list.vbDNode<TYPE> *vbDLList::AddAfter(const TYPE &X, vbDNode<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.vbDNode<TYPE> *vbDLList::AddBefore(const TYPE &X, vbDNode<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.vbDNode<TYPE> *vbDLList::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.vbDNode<TYPE> *vbDLList::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.virtual vbDNode<TYPE> *vbDLList::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.void vbDLList::AttachToBack(vbDNode<TYPE> *Node)
- Public member function used to insert the specified node after the current last node in the list with the proper typecasting.void vbDLList::AttachToFront(vbDNode<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.int vbDLList::Cat(const vbDLList<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.int vbDLList::Copy(const vbDLList<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 vbDLList::Delete(vbDNode<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 vbDLList::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.int vbDLList::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.virtual vbDNodeBase *vbDLList::DupNode(const vbDNodeBase *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 vbDNode type. This function is declared virtual in case a derived list allocates nodes some other way.vbDNode<TYPE> *vbDLList::Find(const TYPE &X, vbDNode<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.virtual void vbDLList::FreeNode(vbDNodeBase *Node)
- Protected member function, overriding the base class version, used to delete the specified node. This function assumes that the specified node is a vbDNode type. This function is declared virtual in case a derived list de-allocates nodes some other way.vbDNode<TYPE> *vbDLList::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 vbDNodeBase, is not a vbDNode type and does not have an info member. Therefore the list cannot be empty when calling this function. - Public member function that returns a pointer to the node data of the back node or zero if the list is empty.vbDNode<TYPE> *vbDLList::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 vbDNodeBase, is not a vbDNode type and does not have an info member. Therefore the list cannot be empty when calling this function.TYPE *vbDLList::GetFrontNode()
- Public member function that returns a pointer to the node data of the front node or zero if the list is empty.vbDNode<TYPE> *vbDLList::GetHeader()
- Public member function that returns a pointer to the list header typecasting it to a vbDNode type. This function is provided for typecasting convenience when iterating through a list, and cannot be used with any of the vbDNode class members.void vbDLList::InsertAfter(vbDNode<TYPE> *A, vbDNode<TYPE> *B)
- Public member function used to insert node "B" after node "A", with the proper typecasting.void vbDLList::InsertBefore(vbDNode<TYPE> *A, vbDNode<TYPE> *B)
- Public member function used to insert node "B" before node "A", with the proper typecasting.int vbDLList::IsHeader(const vbDNode<TYPE> *Node)
- 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.vbDNode<TYPE> *vbDLList::Rmv(vbDNode<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. functionvbDNode<TYPE> *vbDLList::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.vbDNode<TYPE> *vbDLList::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.vbDNode<TYPE> *vbDLList::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.int vbDLList::operator+=(const vbDLList<TYPE> &X)
- Public member functionvoid vbDLList::operator=(const vbDLList<TYPE> &X)
- Class assignment operator used to turn this list into a copy of the specified vbDLList object. This overloaded assignment operator does not allow the object to assign itself to itself or allow chained assignment.
End Of Document |