1 #include <assert.h>
2
3 template<typename T>
4 class CNode
5 {
6 public:
7 T data;
8 CNode<T> *next;
9 CNode():data(T()),next(NULL)
10 {
11
12 }
13 CNode(const T& initdata):data(initdata),next(NULL)
14 {
15
16 }
17 CNode(const T& initdata,CNode<T> *p):data(initdata),next(p)
18 {
19
20 }
21 };
22
23 template<typename T>
24 class CLinkList
25 {
26 public:
27 CLinkList();
28 CLinkList(const T& initdata);
29 ~CLinkList();
30
31 public:
32 bool IsEmpty() const;
33 int GetCount() const;
34
35 int InsertBefore(const int pos, const T data);
36 int InsertAfter(const int pos, const T data);
37 int AddHead(const T data);
38 int AddTail(const T data);
39 void RemoveAt(const int pos);
40 void RemoveHead();
41 void RemoveTail();
42 void RemoveAll();
43 T& GetTail();
44 T GetTail() const;
45 T& GetHead();
46 T GetHead() const;
47 T& GetAt(const int pos);
48 T GetAt(const int pos) const;
49 void SetAt(const int pos, T data);
50 int Find(const T data) const;
51
52 private:
53 CNode<T>* m_pNodeHead;
54 int m_Count;
55 };
56
57 template<typename T>
58 CLinkList<T>::CLinkList():m_Count(0),m_pNodeHead(NULL)
59 {
60
61 }
62
63 template<typename T>
64 CLinkList<T>::CLinkList(const T& initdata):m_Count(0),m_pNodeHead(NULL)
65 {
66 AddHead(initdata);
67 }
68
69 template<typename T>
70 CLinkList<T>::~CLinkList()
71 {
72 RemoveAll();
73 }
74
75 template<typename T>
76 bool CLinkList<T>::IsEmpty() const
77 {
78 return 0==m_Count;
79 }
80
81 template<typename T>
82 int CLinkList<T>::GetCount() const
83 {
84 return m_Count;
85 }
86
87 template<typename T>
88 int CLinkList<T>::InsertBefore(const int pos, const T data)
89 {
90 CNode<T>* pNewNode;
91 CNode<T>* pTmpNode1;
92
93 assert( 1<=pos && pos<=m_Count);
94
95 pNewNode =new CNode<T>();
96 if ( pNewNode == NULL)
97 {
98 return -1;
99 }
100 pNewNode->data =data;
101
102 //The linklist is empty
103 if( m_pNodeHead==NULL)
104 {
105 pNewNode->next =NULL;
106 m_pNodeHead =pNewNode;
107 m_Count++;
108 return 0;
109 }
110 //Insert the Head
111 if ( pos ==1 )
112 {
113 pNewNode->next =m_pNodeHead;
114 m_pNodeHead =pNewNode;
115 m_Count++;
116 return 0;
117 }
118
119 pTmpNode1 =m_pNodeHead;
120
121 for (int i=2; i<pos; i++)
122 {
123 pTmpNode1 =pTmpNode1->next;
124 }
125
126 pNewNode->next =pTmpNode1->next;
127 pTmpNode1->next =pNewNode;
128 m_Count++;
129
130 return 0;
131 }
132
133 template<typename T>
134 int CLinkList<T>::InsertAfter(const int pos, const T data)
135 {
136 CNode<T>* pNewNode;
137 CNode<T>* pTmpNode1;
138
139 assert( 1<=pos && pos<=m_Count);
140
141 pNewNode =new CNode<T>();
142 if ( pNewNode == NULL)
143 {
144 return -1;
145 }
146 pNewNode->data =data;
147
148 //The linklist is empty
149 if( m_pNodeHead==NULL)
150 {
151 pNewNode->next =NULL;
152 m_pNodeHead =pNewNode;
153 m_Count++;
154 return 0;
155 }
156
157 pTmpNode1 =m_pNodeHead;
158
159 for (int i=1; i<pos; i++)
160 {
161 pTmpNode1 =pTmpNode1->next;
162 }
163
164 pNewNode->next =pTmpNode1->next;
165 pTmpNode1->next =pNewNode;
166 m_Count++;
167
168 return 0;
169 }
170
171 template<typename T>
172 int CLinkList<T>::AddHead(const T data)
173 {
174 CNode<T>* pNewNode;
175
176 pNewNode =new CNode<T>();
177 if ( pNewNode == NULL)
178 {
179 return -1;
180 }
181 pNewNode->data =data;
182
183 if ( m_pNodeHead == NULL)
184 {
185 pNewNode->next =NULL;
186 m_pNodeHead =pNewNode;
187 m_Count++;
188 return 0;
189 }
190 else
191 {
192 pNewNode->next =m_pNodeHead;
193 m_pNodeHead =pNewNode;
194 m_Count++;
195 }
196
197 return 0;
198 }
199
200 template<typename T>
201 int CLinkList<T>::AddTail(const T data)
202 {
203 CNode<T>* pNewNode;
204 CNode<T>* pTmpNode;
205
206 pNewNode =new CNode<T>();
207 if ( pNewNode == NULL)
208 {
209 return -1;
210 }
211
212 pNewNode->data =data;
213 pNewNode->next =NULL;
214
215 if ( m_pNodeHead == NULL)
216 {
217 m_pNodeHead =pNewNode;
218 m_Count++;
219 return 0;
220 }
221
222 pTmpNode =m_pNodeHead;
223 while ( pTmpNode->next != NULL )
224 {
225 pTmpNode =pTmpNode->next;
226 }
227
228 pTmpNode->next =pNewNode;
229 m_Count++;
230
231 return 0;
232 }
233
234 template<typename T>
235 void CLinkList<T>::RemoveAll()
236 {
237 CNode<T>* pTmpNode1 =m_pNodeHead;
238 CNode<T>* pTmpNode2;
239
240 while ( pTmpNode1 != NULL )
241 {
242 pTmpNode2 =pTmpNode1;
243 pTmpNode1 =pTmpNode1->next;
244 delete pTmpNode2;
245 }
246
247 return;
248 }
249
250 template<typename T>
251 T& CLinkList<T>::GetAt(const int pos)
252 {
253 assert( 1<=pos && pos<=m_Count);
254
255 CNode<T>* pTmpNode =m_pNodeHead;
256
257 for (int i=1; i<pos; i++)
258 {
259 pTmpNode =pTmpNode->next;
260 }
261
262 return pTmpNode->data;
263 }