Datei: LinkedList.java

1/**

2 * @author Uwe Schmidt

3 *

4 * Eine Klasse fuer verkettete Listen

5 *

6 * Die leere Liste wird durch einen speziellen

7 * Endeknoten repraesentiert, bei dem die info-Komponente

8 * nie genutzt wird, die next-Komponente enthaelt die

9 * ungueltige Referenz.

10 *

11 * Die Routinen sind alle in rekursiver Form,

12 * die meisten Rekursionen sind Endrekursionen

13 * oder lineare, koennen also einfach in Schleifen

14 * transformiert werden.

15 *

16 * In der Routine remove wird mit Seiteneffekten

17 * gearbeitet, hier wird also der rein funktionale

18 * Stil verlassen, um Kopieroperationen zu vermeiden.

19 *

20 * Die Konstruktoren sind nicht oeffentlich,

21 * sie sind durch statische Methoden ersetzt.

22 *

23 */

25//--------------------

27public

28class LinkedList<E> {

30 //--------------------

31 //

32 // protected als Zugriffsattribut

33 // erlaubt die schrittweise Erweiterung

34 // der Menge der Methoden

36 protected

37 E info;

39 protected

40 LinkedList<E> next;

42 //--------------------

43 //

44 // Objekte werden nur in der Klasse erzeugt

45 // die eigentlichen Konstruktoren sind

46 // mkEmptyList und mkOne

48 protected

49 LinkedList(E info, LinkedList<E> next)

50 {

51 this.info = info;

52 this.next = next;

53 }

55 //--------------------

56 //

57 // mkEmptyList erzeugt immer ein neues Objekt.

58 // Dieses wird durch die schwache Implementierung von

59 // generics in Java notwendig.

60 // Dieser Nachteil kann nur mit "unsave conversions"

61 // umgangen werden.

63 public static

64 <E> LinkedList<E> mkEmptyList()

65 {

66 return

67 new LinkedList<E>(null, null);

68 }

70 //--------------------

71 //

72 // mkOne ist in Analogie zu mkEmptyList

73 // definiert worden

75 public static

76 <E> LinkedList<E> mkOne(E info)

77 {

78 LinkedList<E> res = mkEmptyList();

79 return

80 res.cons(info);

81 }

83 //--------------------

85 public

86 LinkedList<E> cons(E info)

87 {

88 return

89 new LinkedList<E>(info, this);

90 }

92 //--------------------

94 public

95 boolean isEmpty()

96 {

97 return

98 next == null;

99 }

100

101 //--------------------

102

103 public

104 E hd()

105 throws IndexOutOfBoundsException

106 {

107 if ( isEmpty() )

108 throw

109 new IndexOutOfBoundsException("hd of empty list");

110

111 return

112 info;

113 }

114

115 //--------------------

116

117 public

118 LinkedList<E> tl()

119 throws IndexOutOfBoundsException

120 {

121 if ( isEmpty() )

122 throw

123 new IndexOutOfBoundsException("tl of empty list");

124

125 return

126 next;

127 }

128

129 //--------------------

130

131 public

132 int len()

133 {

134 return

135 isEmpty()

136 ? 0

137 : 1 + next.len();

138 }

139

140 //--------------------

141

142 public

143 E at(int i)

144 throws IndexOutOfBoundsException

145 {

146 if ( i < 0 || isEmpty() )

147 throw

148 new IndexOutOfBoundsException("illegal index into linked list");

149

150 return

151 ( i == 0 )

152 ? hd()

153 : next.at(i - 1);

154 }

155

156 //--------------------

157

158 public

159 boolean isIn(E o)

160 {

161 return

162 ! isEmpty()

163 &&

164 ( info.equals(o)

165 ||

166 next.isIn(o) );

167 }

168

169 //--------------------

170

171 /**

172 * erzeugt eine neue Liste

173 * die das Objekt o enthaelt

174 */

175

176 public

177 LinkedList<E> insert(E o)

178 {

179 if ( isIn(o) )

180 return

181 this;

182

183 return

184 cons(o);

185 }

186

187 //--------------------

188

189 /**

190 * erzeugt eine neue Liste

191 * die das Objekt o nicht mehr enthaelt

192 */

193

194 public

195 LinkedList<E> remove(E o)

196 {

197 if ( isEmpty() )

198 return

199 this;

200

201 if ( info.equals(o) )

202 return

203 next;

204

205 next = next.remove(o);

206 // !!! Seiteneffekt

207 // Liste wird veraendert

208

209 return

210 this;

211 }

212

213 //--------------------

214

215 public

216 LinkedList<E> concat(LinkedList<E> l2)

217 {

218 if ( isEmpty() )

219 return

220 l2;

221

222 if ( next.isEmpty() ) {

223 next = l2;

224 } else {

225 next = next.concat(l2);

226 }

227

228 return

229 this;

230 }

231

232 //--------------------

233

234 public

235 LinkedList<E> append(E o)

236 {

237 return

238 concat(mkOne(o));

239 }

240

241 //--------------------

242

243 public

244 String toString()

245 {

246 if ( isEmpty() )

247 return

248 "[]";

249

250 return

251 "[" + info.toString() + next.toString0();

252

253

254 }

255

256 private

257 String toString0()

258 {

259 String s = "";

260 if ( isEmpty() )

261 return

262 "]";

263

264 return

265 "," + info.toString() + next.toString0();

266 }

267

268 //--------------------

269 // forall zur Verarbeitung aller Werte einer Liste

270

271 public

272 <Result> Result forall(Accumulate <E, Result> ac)

273 {

274 LinkedList<E> l1 = this;

275

276 while ( ! l1.isEmpty() ) {

277 ac.process(l1.info);

278 l1 = l1.next;

279 }

280

281 return

282 ac.getResult();

283 }

284

285 //--------------------

286 // len implementiert mit forall

287

288 public

289 int len1()

290 {

291 // auto unboxing

292 return

293 forall(new NoOfElements<E>());

294 }

295

296 //--------------------

297 // toString implementiert mit forall

298

299 public

300 String toString1()

301 {

302 return

303 forall(new ToString <E>("[", ",", "]"));

304 }

305

306 //--------------------

307 // len implementiert mit forall

308 // und einer statischen lokalen Klasse

309 // fuer das Kommando

310

311 // Ziel:

312 // Vermeidung von globalen Namen

313 // fuer lokale Hilfsklassen

314

315 public

316 int len2()

317 {

318 return

319 forall(new LocalNoOfElements <E> ());

320 }

321

322 //--------------------

323 // Quelle hier nur aus Demozwecken aus der

324 // globalen Klasse NoOfElements uebernommen

325

326 static

327 private

328 class LocalNoOfElements <E>

329 extends Accumulate <E, Integer>

330 {

331 int result = 0;

332

333 public

334 void process(E element)

335 {

336 ++result;

337 }

338

339 public

340 Integer getResult()

341 {

342 return

343 result;

344 }

345 }

346

347 /*---------------------------------------------------------*/

348

349}

Die Datei: LinkedList.java