<?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& 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;

    };</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->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& anItem);

private :

    TSglQue<CItem>     iStack; 

    TSglQueIter<CItem> 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<16> 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->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_d0e218642_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->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>