How to construct and manipulate a singly linked list

Code fragments showing how to create a singly linked list and how to manipulate the list and the elements of the list.

The following code fragments show how a singly linked list can be constructed and manipulated. The list consists of instances of an example class, CItem , which forms items on a stack implemented as a singly linked list using the iSlink data member as the link object. In this example, a CItem object can contain an item of text implemented as an HBufC .

The class is declared as:

      
       
      
      class CItem : public CBase
    {
public  :
    static CItem* NewL(const TDesC& aText);
    static CItem* NewLC(const TDesC& aText); 
                  CItem();
    virtual       ~CItem();
    const HBufC*  GetText(); 
public  :        
    static const  TInt iOffset;
private :
    void          ConstructL(const TDesC& aText);
private :    
    TSglQueLink   iSlink;
    HBufC*        iText;
    friend  class CStack;
    };
     

The CItem member functions are implemented as:

      
       
      
      const TInt CItem::iOffset = _FOFF(CItem,iSlink);
     

      
       
      
      CItem* CItem::NewLC(const TDesC& aText)
    {
    CItem* self = new (ELeave) CItem();
    CleanupStack::PushL(self);
    self->ConstructL(aText);
    return self;
    }
     

      
       
      
      CItem* CItem::NewL(const TDesC& aText)
    {
    CItem* self = CItem::NewLC(aText);
    CleanupStack::Pop();
    return self;
    }
     

      
       
      
      void CItem::ConstructL(const TDesC& aText)
    {
    iText    = aText.AllocL();
    }
     

      
       
      
      CItem::CItem()
    {}
     

      
       
      
      CItem::~CItem()
    {
    delete iText;
    }
     

      
       
      
      const HBufC* CItem::GetText()
    {
    return (iText);
    }
     

As part of the construction process, a CItem constructs an HBufC of the correct length and copies the content of the descriptor parameter into it.

The stack is implemented by an instance of the example class CStack . This maintains the stack by adding CItem objects onto the end of the list and removing them from the end of the list. When removing them from the end of the list, a pointer to the removed CItem object is returned.

In this example, the list header, iStack , and the iterator, iStackIter , are declared as data members of the class and are constructed when the CStack object is constructed. A C++ constructor must be supplied so that iStackIter can be constructed. ( TSglQueIter has no default constructor).

AddToStack() takes a CItem object and adds it to the end of the singly linked list.

RemoveFromStack() takes the CItem object at the end of the singly linked list, removes it from the list and returns a pointer to it.

The CStack class is declared as:

      
       
      
      class CStack : public CBase
    {
public :
    static CStack* NewL();
    static CStack* NewLC();
                   CStack();
    void           Construct();
    virtual        ~CStack();
    CItem*         RemoveFromStack();
    void           AddToStack(CItem& anItem);
private :
    TSglQue<CItem>     iStack; 
    TSglQueIter<CItem> iStackIter;
    };
     

The CStack member functions are implemented as:

      
       
      
      CStack* CStack::NewLC()
    {
    CStack* self = CStack::NewL();
    CleanupStack::PushL(self);
    return self;
    }
     

      
       
      
      CStack* CStack::NewL()
    {
    CStack* self = new (ELeave) CStack;
    return self;
    }
     

      
       
      
      CStack::CStack()
    : iStack(CItem::iOffset),iStackIter(iStack) 
    {}
     

       
        
       
       CStack::~CStack()
    {
    CItem*  item;
    
    iStackIter.SetToFirst(); 
    while ((item = iStackIter++) != NULL)
        {
        iStack.Remove(*item);
        delete item;
        };
    }
      

       
        
       
       void CStack::AddToStack(CItem& anItem)
    {
    iStack.AddLast(anItem);
    }
      

       
        
       
       CItem* CStack::RemoveFromStack()
    {
    CItem* lastitem;
    
    if (iStack.IsEmpty())
        return NULL;
    
    lastitem = iStack.Last();
    iStack.Remove(*lastitem); 
    
    return (lastitem);
    }
      

Executing the code

Executing the code results in a singly linked list of CItem objects each containing a pointer to an HBufC descriptor each of which, in turn, contains the text “8”, “89”, and so on through to “89ABCDEF”:

       
        
       
       {
    CStack*  stack;
    CItem*   item;
    TBuf<16> buffer;
    
    TRAPD(leavecode,stack = CStack::NewL());
    if (leavecode != KErrNone)
        {
        // Cannot create stack
        return;
        }
      

       
        
       
       for (TUint jj = 8; jj < 16; jj++)
        {
        buffer.AppendNumUC(jj,EHex); 
        TRAPD(leavecode,item = CItem::NewL(buffer));
        if (leavecode != KErrNone)
            {
            // Cannot create item
            delete stack;
            return;
            }
        stack->AddToStack(*item);
        }
      

as the following shows:

Figure 1. Example singly linked list

       
        
       
       while ((item = stack->RemoveFromStack()) != NULL)
        {
        // item->GetText());can be used to access the text.
        delete item;
        };
      

       
        
       
       delete stack;