|
1 <?xml version="1.0" encoding="utf-8"?> |
|
2 <!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. --> |
|
3 <!-- This component and the accompanying materials are made available under the terms of the License |
|
4 "Eclipse Public License v1.0" which accompanies this distribution, |
|
5 and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". --> |
|
6 <!-- Initial Contributors: |
|
7 Nokia Corporation - initial contribution. |
|
8 Contributors: |
|
9 --> |
|
10 <!DOCTYPE concept |
|
11 PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd"> |
|
12 <concept id="GUID-9D3637D4-43BD-51ED-B4BC-1F234F09E24B" xml:lang="en"><title>How |
|
13 to construct and manipulate a singly linked list</title><shortdesc>Code fragments showing how to create a singly linked list and how |
|
14 to manipulate the list and the elements of the list.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody> |
|
15 <p>The following code fragments show how a singly linked list can be constructed |
|
16 and manipulated. The list consists of instances of an example class, <codeph>CItem</codeph>, |
|
17 which forms items on a stack implemented as a singly linked list using the <codeph>iSlink</codeph> data |
|
18 member as the link object. In this example, a <codeph>CItem</codeph> object |
|
19 can contain an item of text implemented as an <codeph>HBufC</codeph>.</p> |
|
20 <p>The class is declared as:</p> |
|
21 <codeblock id="GUID-EF742BDF-7292-51DF-B7D4-6219D9CDFFCE" xml:space="preserve">class CItem : public CBase |
|
22 { |
|
23 public : |
|
24 static CItem* NewL(const TDesC& aText); |
|
25 static CItem* NewLC(const TDesC& aText); |
|
26 CItem(); |
|
27 virtual ~CItem(); |
|
28 const HBufC* GetText(); |
|
29 public : |
|
30 static const TInt iOffset; |
|
31 private : |
|
32 void ConstructL(const TDesC& aText); |
|
33 private : |
|
34 TSglQueLink iSlink; |
|
35 HBufC* iText; |
|
36 friend class CStack; |
|
37 };</codeblock> |
|
38 <p>The <codeph>CItem</codeph> member functions are implemented as:</p> |
|
39 <codeblock id="GUID-2B4A1C64-7C4C-5950-93F0-2A80A0AEF343" xml:space="preserve">const TInt CItem::iOffset = _FOFF(CItem,iSlink);</codeblock> |
|
40 <codeblock id="GUID-67788B52-9B64-556B-B4BF-D940C49B2E3E" xml:space="preserve">CItem* CItem::NewLC(const TDesC& aText) |
|
41 { |
|
42 CItem* self = new (ELeave) CItem(); |
|
43 CleanupStack::PushL(self); |
|
44 self->ConstructL(aText); |
|
45 return self; |
|
46 }</codeblock> |
|
47 <codeblock id="GUID-5CC6AD98-E877-5699-9BAC-14DE0A4413E2" xml:space="preserve">CItem* CItem::NewL(const TDesC& aText) |
|
48 { |
|
49 CItem* self = CItem::NewLC(aText); |
|
50 CleanupStack::Pop(); |
|
51 return self; |
|
52 }</codeblock> |
|
53 <codeblock id="GUID-14D5FB76-1FC9-5D7D-A35C-9AC87222DA64" xml:space="preserve">void CItem::ConstructL(const TDesC& aText) |
|
54 { |
|
55 iText = aText.AllocL(); |
|
56 }</codeblock> |
|
57 <codeblock id="GUID-44FB4D1A-D567-5181-B425-D988BF364A55" xml:space="preserve">CItem::CItem() |
|
58 {}</codeblock> |
|
59 <codeblock id="GUID-DF4603B2-56E0-5CC1-8920-27C04FCE2899" xml:space="preserve">CItem::~CItem() |
|
60 { |
|
61 delete iText; |
|
62 }</codeblock> |
|
63 <codeblock id="GUID-E306FFA8-9A93-5047-9999-A36DE087D9BF" xml:space="preserve">const HBufC* CItem::GetText() |
|
64 { |
|
65 return (iText); |
|
66 } |
|
67 </codeblock> |
|
68 <p>As part of the construction process, a <codeph>CItem</codeph> constructs |
|
69 an <codeph>HBufC</codeph> of the correct length and copies the content of |
|
70 the descriptor parameter into it.</p> |
|
71 <p>The stack is implemented by an instance of the example class <codeph>CStack</codeph>. |
|
72 This maintains the stack by adding <codeph>CItem</codeph> objects onto the |
|
73 end of the list and removing them from the end of the list. When removing |
|
74 them from the end of the list, a pointer to the removed <codeph>CItem</codeph> object |
|
75 is returned.</p> |
|
76 <p>In this example, the list header, <codeph>iStack</codeph>, and the iterator, <codeph>iStackIter</codeph>, |
|
77 are declared as data members of the class and are constructed when the <codeph>CStack</codeph> object |
|
78 is constructed. A C++ constructor must be supplied so that <codeph>iStackIter</codeph> can |
|
79 be constructed. (<codeph>TSglQueIter</codeph> has no default constructor).</p> |
|
80 <p><codeph>AddToStack()</codeph> takes a <codeph>CItem</codeph> object and |
|
81 adds it to the end of the singly linked list.</p> |
|
82 <p><codeph>RemoveFromStack()</codeph> takes the <codeph>CItem</codeph> object |
|
83 at the end of the singly linked list, removes it from the list and returns |
|
84 a pointer to it.</p> |
|
85 <p>The <codeph>CStack</codeph> class is declared as:</p> |
|
86 <codeblock id="GUID-9640ACCC-5C02-5238-9866-C3E5F24BF256" xml:space="preserve">class CStack : public CBase |
|
87 { |
|
88 public : |
|
89 static CStack* NewL(); |
|
90 static CStack* NewLC(); |
|
91 CStack(); |
|
92 void Construct(); |
|
93 virtual ~CStack(); |
|
94 CItem* RemoveFromStack(); |
|
95 void AddToStack(CItem& anItem); |
|
96 private : |
|
97 TSglQue<CItem> iStack; |
|
98 TSglQueIter<CItem> iStackIter; |
|
99 }; |
|
100 </codeblock> |
|
101 <p>The <codeph>CStack</codeph> member functions are implemented as:</p> |
|
102 <codeblock id="GUID-6DB67609-DFD9-5C3E-B0DE-DCBF24E2004B" xml:space="preserve">CStack* CStack::NewLC() |
|
103 { |
|
104 CStack* self = CStack::NewL(); |
|
105 CleanupStack::PushL(self); |
|
106 return self; |
|
107 }</codeblock> |
|
108 <codeblock id="GUID-1A43592A-6670-5DB7-A66C-586F054DA96B" xml:space="preserve">CStack* CStack::NewL() |
|
109 { |
|
110 CStack* self = new (ELeave) CStack; |
|
111 return self; |
|
112 }</codeblock> |
|
113 <codeblock id="GUID-7B084689-CEFA-5F12-A112-F57E3969EF64" xml:space="preserve">CStack::CStack() |
|
114 : iStack(CItem::iOffset),iStackIter(iStack) |
|
115 {}</codeblock> |
|
116 <section id="GUID-6C00AE42-5876-4C9B-8530-4E3BCEC12295"><title>Using the list |
|
117 iterator</title> <p>The C++ constructor is needed so that the list header |
|
118 (<codeph>iStack</codeph>) and the list iterator (<codeph>iStackIter</codeph>) |
|
119 can be properly constructed.</p> <p>Before destroying a <codeph>CStack</codeph> object, |
|
120 the list is destroyed. This is achieved using the iterator (<codeph>iStackIter</codeph>). |
|
121 The iterator pointer is set to point to each element in turn, removing that |
|
122 element from the list before destroying it.</p> <p>Once the iterator has reached |
|
123 the end of the list, the operator<codeph>++</codeph> returns <codeph>NULL</codeph>.</p> <p>The |
|
124 destruction process is safe if the list is empty; the statement <codeph>iStackIter.SetToFirst()</codeph> is |
|
125 harmless, the operator<codeph>++</codeph> returns <codeph>NULL</codeph> and |
|
126 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() |
|
127 { |
|
128 CItem* item; |
|
129 |
|
130 iStackIter.SetToFirst(); |
|
131 while ((item = iStackIter++) != NULL) |
|
132 { |
|
133 iStack.Remove(*item); |
|
134 delete item; |
|
135 }; |
|
136 }</codeblock> </section> |
|
137 <section id="GUID-9B58504D-1C1C-4D2C-93BB-085F04EA62B3"><title>Adding an element |
|
138 to the stack</title> <p>Adding an element to the stack simply involves adding |
|
139 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& anItem) |
|
140 { |
|
141 iStack.AddLast(anItem); |
|
142 }</codeblock> </section> |
|
143 <section id="GUID-99C58AE1-4EA3-41FA-82AF-C1B9D08FB57F"><title>Removing an |
|
144 element from the stack</title> <p>The <codeph>RemoveFromStack()</codeph> function |
|
145 returns <codeph>NULL</codeph>, if the list is empty, otherwise it just uses |
|
146 the <codeph>Last()</codeph> member function to return a pointer to the last |
|
147 element in the list before removing it.</p> <codeblock id="GUID-5BDC3F9B-1C99-534B-82CC-18731E3C22B9" xml:space="preserve">CItem* CStack::RemoveFromStack() |
|
148 { |
|
149 CItem* lastitem; |
|
150 |
|
151 if (iStack.IsEmpty()) |
|
152 return NULL; |
|
153 |
|
154 lastitem = iStack.Last(); |
|
155 iStack.Remove(*lastitem); |
|
156 |
|
157 return (lastitem); |
|
158 }</codeblock> </section> |
|
159 <section id="GUID-BC25EB70-D1D2-4045-8345-C002C17D9114"><title>Executing the |
|
160 code</title> <p>Executing the code results in a singly linked list of <codeph>CItem</codeph> objects |
|
161 each containing a pointer to an <codeph>HBufC</codeph> descriptor each of |
|
162 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"> { |
|
163 CStack* stack; |
|
164 CItem* item; |
|
165 TBuf<16> buffer; |
|
166 |
|
167 TRAPD(leavecode,stack = CStack::NewL()); |
|
168 if (leavecode != KErrNone) |
|
169 { |
|
170 // Cannot create stack |
|
171 return; |
|
172 }</codeblock> <codeblock id="GUID-18506411-26D8-5866-A80E-D36BD20DFD01" xml:space="preserve"> for (TUint jj = 8; jj < 16; jj++) |
|
173 { |
|
174 buffer.AppendNumUC(jj,EHex); |
|
175 TRAPD(leavecode,item = CItem::NewL(buffer)); |
|
176 if (leavecode != KErrNone) |
|
177 { |
|
178 // Cannot create item |
|
179 delete stack; |
|
180 return; |
|
181 } |
|
182 stack->AddToStack(*item); |
|
183 }</codeblock> <p>as the following shows:</p> <fig id="GUID-27C947C7-3035-54A4-BA6E-C701C3007DD6"> |
|
184 <title>Example singly linked list</title> |
|
185 <image href="GUID-BF155E49-35AF-5BC1-80C5-8D6C68C464F8_d0e218642_href.png" placement="inline"/> |
|
186 </fig> </section> |
|
187 <section id="GUID-CB47362B-7068-45AD-9D60-7D93174ED858"><title>Removing elements |
|
188 from list</title> <p>The following code removes each <codeph>CItem</codeph> element |
|
189 from the list, starting with the last and working through to the first until |
|
190 the list is empty.</p> <codeblock id="GUID-36122717-2CA8-5E9E-B223-4921860A4027" xml:space="preserve"> while ((item = stack->RemoveFromStack()) != NULL) |
|
191 { |
|
192 // item->GetText());can be used to access the text. |
|
193 delete item; |
|
194 };</codeblock> <codeblock id="GUID-7A4C3458-9676-5ED2-82DB-703C48F347DB" xml:space="preserve"> delete stack;</codeblock> <p>Note |
|
195 that unlike doubly linked lists, elements can only be added to the start or |
|
196 the end of a singly linked list. Elements <i>cannot</i> be added to the middle |
|
197 of the list.</p> </section> |
|
198 </conbody></concept> |