<?xml version="1.0" encoding="utf-8"?>
<!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. -->
<!-- This component and the accompanying materials are made available under the terms of the License 
"Eclipse Public License v1.0" which accompanies this distribution, 
and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". -->
<!-- Initial Contributors:
    Nokia Corporation - initial contribution.
Contributors: 
-->
<!DOCTYPE concept
  PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd">
<concept id="GUID-9D3637D4-43BD-51ED-B4BC-1F234F09E24B" xml:lang="en"><title>How
to construct and manipulate a singly linked list</title><shortdesc>Code fragments showing how to create a singly linked list and how
to manipulate the list and the elements of the list.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody>
<p>The following code fragments show how a singly linked list can be constructed
and manipulated. The list consists of instances of an example class, <codeph>CItem</codeph>,
which forms items on a stack implemented as a singly linked list using the <codeph>iSlink</codeph> data
member as the link object. In this example, a <codeph>CItem</codeph> object
can contain an item of text implemented as an <codeph>HBufC</codeph>.</p>
<p>The class is declared as:</p>
<codeblock id="GUID-EF742BDF-7292-51DF-B7D4-6219D9CDFFCE" xml:space="preserve">class CItem : public CBase
    {
public  :
    static CItem* NewL(const TDesC&amp; aText);
    static CItem* NewLC(const TDesC&amp; aText); 
                  CItem();
    virtual       ~CItem();
    const HBufC*  GetText(); 
public  :        
    static const  TInt iOffset;
private :
    void          ConstructL(const TDesC&amp; aText);
private :    
    TSglQueLink   iSlink;
    HBufC*        iText;
    friend  class CStack;
    };</codeblock>
<p>The <codeph>CItem</codeph> member functions are implemented as:</p>
<codeblock id="GUID-2B4A1C64-7C4C-5950-93F0-2A80A0AEF343" xml:space="preserve">const TInt CItem::iOffset = _FOFF(CItem,iSlink);</codeblock>
<codeblock id="GUID-67788B52-9B64-556B-B4BF-D940C49B2E3E" xml:space="preserve">CItem* CItem::NewLC(const TDesC&amp; aText)
    {
    CItem* self = new (ELeave) CItem();
    CleanupStack::PushL(self);
    self-&gt;ConstructL(aText);
    return self;
    }</codeblock>
<codeblock id="GUID-5CC6AD98-E877-5699-9BAC-14DE0A4413E2" xml:space="preserve">CItem* CItem::NewL(const TDesC&amp; aText)
    {
    CItem* self = CItem::NewLC(aText);
    CleanupStack::Pop();
    return self;
    }</codeblock>
<codeblock id="GUID-14D5FB76-1FC9-5D7D-A35C-9AC87222DA64" xml:space="preserve">void CItem::ConstructL(const TDesC&amp; aText)
    {
    iText    = aText.AllocL();
    }</codeblock>
<codeblock id="GUID-44FB4D1A-D567-5181-B425-D988BF364A55" xml:space="preserve">CItem::CItem()
    {}</codeblock>
<codeblock id="GUID-DF4603B2-56E0-5CC1-8920-27C04FCE2899" xml:space="preserve">CItem::~CItem()
    {
    delete iText;
    }</codeblock>
<codeblock id="GUID-E306FFA8-9A93-5047-9999-A36DE087D9BF" xml:space="preserve">const HBufC* CItem::GetText()
    {
    return (iText);
    }
</codeblock>
<p>As part of the construction process, a <codeph>CItem</codeph> constructs
an <codeph>HBufC</codeph> of the correct length and copies the content of
the descriptor parameter into it.</p>
<p>The stack is implemented by an instance of the example class <codeph>CStack</codeph>.
This maintains the stack by adding <codeph>CItem</codeph> 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 <codeph>CItem</codeph> object
is returned.</p>
<p>In this example, the list header, <codeph>iStack</codeph>, and the iterator, <codeph>iStackIter</codeph>,
are declared as data members of the class and are constructed when the <codeph>CStack</codeph> object
is constructed. A C++ constructor must be supplied so that <codeph>iStackIter</codeph> can
be constructed. (<codeph>TSglQueIter</codeph> has no default constructor).</p>
<p><codeph>AddToStack()</codeph> takes a <codeph>CItem</codeph> object and
adds it to the end of the singly linked list.</p>
<p><codeph>RemoveFromStack()</codeph> takes the <codeph>CItem</codeph> object
at the end of the singly linked list, removes it from the list and returns
a pointer to it.</p>
<p>The <codeph>CStack</codeph> class is declared as:</p>
<codeblock id="GUID-9640ACCC-5C02-5238-9866-C3E5F24BF256" xml:space="preserve">class CStack : public CBase
    {
public :
    static CStack* NewL();
    static CStack* NewLC();
                   CStack();
    void           Construct();
    virtual        ~CStack();
    CItem*         RemoveFromStack();
    void           AddToStack(CItem&amp; anItem);
private :
    TSglQue&lt;CItem&gt;     iStack; 
    TSglQueIter&lt;CItem&gt; iStackIter;
    };
</codeblock>
<p>The <codeph>CStack</codeph> member functions are implemented as:</p>
<codeblock id="GUID-6DB67609-DFD9-5C3E-B0DE-DCBF24E2004B" xml:space="preserve">CStack* CStack::NewLC()
    {
    CStack* self = CStack::NewL();
    CleanupStack::PushL(self);
    return self;
    }</codeblock>
<codeblock id="GUID-1A43592A-6670-5DB7-A66C-586F054DA96B" xml:space="preserve">CStack* CStack::NewL()
    {
    CStack* self = new (ELeave) CStack;
    return self;
    }</codeblock>
<codeblock id="GUID-7B084689-CEFA-5F12-A112-F57E3969EF64" xml:space="preserve">CStack::CStack()
    : iStack(CItem::iOffset),iStackIter(iStack) 
    {}</codeblock>
<section id="GUID-6C00AE42-5876-4C9B-8530-4E3BCEC12295"><title>Using the list
iterator</title> <p>The C++ constructor is needed so that the list header
(<codeph>iStack</codeph>) and the list iterator (<codeph>iStackIter</codeph>)
can be properly constructed.</p> <p>Before destroying a <codeph>CStack</codeph> object,
the list is destroyed. This is achieved using the iterator (<codeph>iStackIter</codeph>).
The iterator pointer is set to point to each element in turn, removing that
element from the list before destroying it.</p> <p>Once the iterator has reached
the end of the list, the operator<codeph>++</codeph> returns <codeph>NULL</codeph>.</p> <p>The
destruction process is safe if the list is empty; the statement <codeph>iStackIter.SetToFirst()</codeph> is
harmless, the operator<codeph>++</codeph> returns <codeph>NULL</codeph> and
execution of the body of the <codeph>while</codeph> loop never happens.</p> <codeblock id="GUID-05A85DC1-BA5A-52BD-BC3A-6DD27F050B3A" xml:space="preserve">CStack::~CStack()
    {
    CItem*  item;
    
    iStackIter.SetToFirst(); 
    while ((item = iStackIter++) != NULL)
        {
        iStack.Remove(*item);
        delete item;
        };
    }</codeblock> </section>
<section id="GUID-9B58504D-1C1C-4D2C-93BB-085F04EA62B3"><title>Adding an element
to the stack</title> <p>Adding an element to the stack simply involves adding
the <codeph>CItem</codeph> object to the end of the list.</p> <codeblock id="GUID-819F3511-AFC1-57CB-A6B6-0A3A778B9737" xml:space="preserve">void CStack::AddToStack(CItem&amp; anItem)
    {
    iStack.AddLast(anItem);
    }</codeblock> </section>
<section id="GUID-99C58AE1-4EA3-41FA-82AF-C1B9D08FB57F"><title>Removing an
element from the stack</title> <p>The <codeph>RemoveFromStack()</codeph> function
returns <codeph>NULL</codeph>, if the list is empty, otherwise it just uses
the <codeph>Last()</codeph> member function to return a pointer to the last
element in the list before removing it.</p> <codeblock id="GUID-5BDC3F9B-1C99-534B-82CC-18731E3C22B9" xml:space="preserve">CItem* CStack::RemoveFromStack()
    {
    CItem* lastitem;
    
    if (iStack.IsEmpty())
        return NULL;
    
    lastitem = iStack.Last();
    iStack.Remove(*lastitem); 
    
    return (lastitem);
    }</codeblock> </section>
<section id="GUID-BC25EB70-D1D2-4045-8345-C002C17D9114"><title>Executing the
code</title> <p>Executing the code results in a singly linked list of <codeph>CItem</codeph> objects
each containing a pointer to an <codeph>HBufC</codeph> descriptor each of
which, in turn, contains the text “8”, “89”, and so on through to “89ABCDEF”:</p> <codeblock id="GUID-F00B6DDF-54C8-541D-8688-FDD227DC48F4" xml:space="preserve">    {
    CStack*  stack;
    CItem*   item;
    TBuf&lt;16&gt; buffer;
    
    TRAPD(leavecode,stack = CStack::NewL());
    if (leavecode != KErrNone)
        {
        // Cannot create stack
        return;
        }</codeblock> <codeblock id="GUID-18506411-26D8-5866-A80E-D36BD20DFD01" xml:space="preserve">    for (TUint jj = 8; jj &lt; 16; jj++)
        {
        buffer.AppendNumUC(jj,EHex); 
        TRAPD(leavecode,item = CItem::NewL(buffer));
        if (leavecode != KErrNone)
            {
            // Cannot create item
            delete stack;
            return;
            }
        stack-&gt;AddToStack(*item);
        }</codeblock> <p>as the following shows:</p> <fig id="GUID-27C947C7-3035-54A4-BA6E-C701C3007DD6">
<title>Example singly linked list</title>
<image href="GUID-BF155E49-35AF-5BC1-80C5-8D6C68C464F8_d0e219903_href.png" placement="inline"/>
</fig> </section>
<section id="GUID-CB47362B-7068-45AD-9D60-7D93174ED858"><title>Removing elements
from list</title> <p>The following code removes each <codeph>CItem</codeph> element
from the list, starting with the last and working through to the first until
the list is empty.</p> <codeblock id="GUID-36122717-2CA8-5E9E-B223-4921860A4027" xml:space="preserve">    while ((item = stack-&gt;RemoveFromStack()) != NULL)
        {
        // item-&gt;GetText());can be used to access the text.
        delete item;
        };</codeblock> <codeblock id="GUID-7A4C3458-9676-5ED2-82DB-703C48F347DB" xml:space="preserve">    delete stack;</codeblock> <p>Note
that unlike doubly linked lists, elements can only be added to the start or
the end of a singly linked list. Elements <i>cannot</i> be added to the middle
of the list.</p> </section>
</conbody></concept>