Class xbLinkList and xbLinkListOrd

Chapter Updated 07/02/25

Class xbLinkList - Basic Link List Structure


Class xbLinkList provides standard linked list functionality.

  • Template based class, supports a list of any object type
  • Supports additions at the beginning or end of the list
  • Supports deletions at the beginning or end of the list
  • Can be used to support a stack data structure by always adding to the end and removing from the end
  • xbLLN is a linked list node of type xbNodeType
  • Class is available if XB_LINKLIST_SUPPORT is compiled in library


    MethodDescription
    xbLinkList()Constructor
    ~xbLinkList()Destructor
    xbLinkListNode *GetHeadNode() constReturn the head node
    xbLinkListNode *GetEndNode() constReturn the last node
    xbLinkListNode *GetNodeForNo( xbUInt32 ulNodeNo ) constReturn the node for a given number
    void Clear()Clear the linked list
    xbUInt32 GetNodeCnt() constRetrun the number of nodes in the linked list
    xbInt16 InsertAtEnd( const xbNodeType &xbLLN )Insert a node at the end os the list
    xbInt16 InsertAtEnd( const xbNodeType &ntKey, xbLinkListNode **np )Insert a keyed node at the end of the list
    xbInt16 InsertAtFront( const xbNodeType &xbLLN )Insert a node in the beginning of the list
    xbInt16 RemoveByVal( const xbNodeType &xbLLN )Remove a node for a given value
    xbInt16 RemoveFromEnd()Remove a node from the front of the list
    xbInt16 RemoveFromEnd( xbNodeType &xbLLN )Remove a node from the end of the list, returning data
    xbInt16 RemoveFromFront( xbNodeType &xbLLN )Remove a node from the front of the list, returning node data
    xbInt16 SearchFor( const xbNodeType &xbLLN )Search for a node


    Class xbLinkListOrd - Ordered Link List Structure

    Class xbLinkListOrd provides ordered linked list functionality.
  • Template based class, supports an ordered list of any object type.
  • Inserts node into list, placement determined by key value.
  • Supports deletions at the beginning, end or by key value.
  • Class is available if XB_LINKLIST_SUPPORT is compiled in library


    MethodDescription
    xbLinkListOrd()Constructor
    ~xbLinkListOrd()Destructor
    void Clear()Clear the linked list
    xbLinkListNode *GetHeadNode() constReturn the head node
    xbLinkListNode *GetEndNode() constReturn the end node
    xbLinkListNode *GetNodeForKey( const xbString &sKey ) constReturn node for a given key
    xbInt16 GetDataForKey( const xbNodeType &ntKey, xbString &sData )Get the node for a given key
    xbBool GetDupKeys()Get the dup key setting.
    xbTrue - allow dup keys
    xbFalse - dup keys not allowed
    xbUInt32 GetNodeCnt() const
    xbUInt32 GetNodeCnt( const xbString &sNodeKey ) const    		Get the node count
    xbInt16 InsertKey( const xbNodeType &ntKey )
    xbInt16 InsertKey( const xbNodeType &ntKey, const xbString &sData )
    xbInt16 InsertKey( const xbNodeType &ntKey, xbUInt32 ulData )    		Insert into list
    xbBool KeyExists( const xbNodeType &ntKey ) constCheck for existence of key
    xbInt16 RemoveKey( const xbNodeType &ntKey )Remove a node from the list, based on key
    xbInt16 RemoveFromEnd( xbNodeType &ntKey )Remove node from end of list
    xbInt16 RemoveFromFront( xbNodeType &ntKey )
    xbInt16 RemoveFromFront()    		Remove node from front of list
    void SetDupKeys( xbBool bAllowDupKeys )Set dup key setting
    xbTrue - allow dup keys
    xbFalse - dup keys not allowed
    xbInt16 UpdateForKey( const xbNodeType &ntKey, const xbString &sData )Update node for a given key


    Example program using xbLinkList methods

    /* xb_ex_linklist.cpp XBase64 Software Library Copyright (c) 1997,2003,2014,2022,2023,2024 Gary A Kunkel The xb64 software library is covered under the terms of the GPL Version 3, 2007 license. Email Contact: XDB-devel@lists.sourceforge.net XDB-users@lists.sourceforge.net */ // This program demonstrates usage of the linked list functionality conatined within the library #include "xbase.h" using namespace xb; int main( int argCnt, char **av ) { int iRc = 0; xbXBase x; xbString s; // set up a linked list of strings xbLinkList<xbString> ll; // add a bunch of stuff to the front ll.InsertAtFront( "A" ); ll.InsertAtFront( "B" ); ll.InsertAtFront( "C" ); ll.InsertAtFront( "D" ); ll.InsertAtFront( "E" ); ll.InsertAtFront( "F" ); ll.InsertAtFront( "G" ); ll.InsertAtFront( "H" ); // add a bunch of stuff to the end ll.InsertAtEnd( "1" ); ll.InsertAtEnd( "2" ); ll.InsertAtEnd( "3" ); ll.InsertAtEnd( "4" ); ll.InsertAtEnd( "5" ); ll.InsertAtEnd( "6" ); ll.InsertAtEnd( "7" ); ll.InsertAtEnd( "8" ); std::cout << "iterate list begin to end" << std::endl; xbLinkListNode<xbString> * llN = ll.GetHeadNode(); xbUInt32 ulCnt = ll.GetNodeCnt(); for( xbUInt32 i = 0; i < ulCnt; i++ ){ s = llN->GetKey(); std::cout << s.Str() << " "; llN = llN->GetNextNode(); } std::cout << std::endl << "iterate list end to begin" << std::endl; llN = ll.GetEndNode(); for( xbUInt32 i = 0; i < ulCnt; i++ ){ s = llN->GetKey(); std::cout << s.Str() << " "; llN = llN->GetPrevNode(); } std::cout << std::endl; ll.RemoveFromFront( s ); std::cout << "Removed [" << s.Str() << "] from front" << std::endl; ll.RemoveFromEnd( s ); std::cout << "Removed [" << s.Str() << "] from end" << std::endl; std::cout << "Node count before clear = " << ll.GetNodeCnt() << std::endl; ll.Clear(); std::cout << "Node count after clear = " << ll.GetNodeCnt() << std::endl; // ordered link list xbLinkListOrd<xbString> llO; llO.SetDupKeys( 0 ); llO.InsertKey( "J" ); if(( iRc = llO.InsertKey( "J" )) != XB_KEY_NOT_UNIQUE ) std::cout << "This should error, no dups allowed" << std::endl; llO.InsertKey( "M" ); llO.InsertKey( "C" ); llO.InsertKey( "F" ); llO.InsertKey( "Q" ); llO.InsertKey( "A" ); llO.InsertKey( "T" ); std::cout << "dumping ordered list begin to end\n"; llN = llO.GetHeadNode(); while( llN ){ s = llN->GetKey(); std::cout << s.Str() << " "; llN = llN->GetNextNode(); } std::cout << std::endl << "dumping node chain from end to begine\n"; llN = llO.GetEndNode(); while( llN ){ s = llN->GetKey(); std::cout << s.Str() << " "; llN = llN->GetPrevNode(); } std::cout << std::endl; s = "A"; if( llO.KeyExists( s )){ std::cout << s.Str() << " exists, deleting." << std::endl; llO.RemoveKey( s ); } if( llO.KeyExists( s )) std::cout << s.Str() << " exists" << std::endl; else std::cout << s.Str() << " does not exist" << std::endl; return iRc; }