Datei: LinkedList.java

1/**

2 * @author Uwe Schmidt

3 *

4 * eine Klasse fuer verkettete Listen

5 *

6 * die ungueltige Referenz wird durch

7 * eine spezielle Referenz repraesentiert

8 * die beim Laden der Klasse erzeugt wird

9 *

10 * die Routinen sind alle in rekursiver Form

11 * die meisten Rekursionen sind Endrekursionen

12 * oder lineare, koennen also einfach in Schleifen

13 * transformiert werden

14 *

15 * in der Routine remove wird mit Seiteneffekten

16 * gearbeitet, hier wird also der rein funktionale

17 * Stil verlassen, um Kopieroperationen zu vermeiden

18 */

20//--------------------

22public

23class LinkedList {

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

26 //

27 // die leere Liste wird durch die Referenz

28 // in der Variablen empty repraesentiert

30 protected static final

31 LinkedList empty = new LinkedList(null, null);

33 //--------------------

34 //

35 // protected als Zugriffsattribut

36 // erlaubt die schrittweise Erweiterung

37 // der Menge der Methoden

39 protected

40 Object info;

42 protected

43 LinkedList next;

45 //--------------------

46 //

47 // Objekte werden nur in der Klasse erzeugt

48 // die eigentlichen Konstruktoren sind

49 // mkEmptyList und mkOne

51 protected

52 LinkedList(Object info, LinkedList next)

53 {

54 this.info = info;

55 this.next = next;

56 }

58 //--------------------

59 //

60 // mkEmptyList erzeugt kein neues Objekt

61 // das Objekt fuer die leere Liste ist immer dasgleiche

63 public static

64 LinkedList mkEmptyList()

65 {

66 return

67 empty;

68 }

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

71 //

72 // mkOne ist in Analogie zu mkEmptyList

73 // definiert worden

75 public static

76 LinkedList mkOne(Object info)

77 {

78 return

79 new LinkedList(info, empty);

80 }

82 //--------------------

84 public

85 LinkedList cons(Object info)

86 {

87 return

88 new LinkedList(info, this);

89 }

91 //--------------------

93 public

94 boolean isEmpty()

95 {

96 return

97 this == empty;

98 }

100 //--------------------

101

102 public

103 Object hd()

104 throws IndexOutOfBoundsException

105 {

106 if ( isEmpty() )

107 throw

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

109

110 return

111 info;

112 }

113

114 //--------------------

115

116 public

117 LinkedList tl()

118 throws IndexOutOfBoundsException

119 {

120 if ( isEmpty() )

121 throw

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

123

124 return

125 next;

126 }

127

128 //--------------------

129

130 public

131 int len()

132 {

133 return

134 isEmpty()

135 ? 0

136 : 1 + next.len();

137 }

138

139 //--------------------

140

141 public

142 Object at(int i)

143 throws IndexOutOfBoundsException

144 {

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

146 throw

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

148

149 return

150 ( i == 0 )

151 ? hd()

152 : next.at(i - 1);

153 }

154

155 //--------------------

156

157 public

158 boolean isIn(Object o)

159 {

160 return

161 ! isEmpty()

162 &&

163 ( info.equals(o)

164 ||

165 next.isIn(o) );

166 }

167

168 //--------------------

169

170 /**

171 * erzeugt eine neue Liste

172 * die das Objekt o enthaelt

173 */

174

175 public

176 LinkedList insert(Object o)

177 {

178 if ( isIn(o) )

179 return

180 this;

181

182 return

183 cons(o);

184 }

185

186 //--------------------

187

188 /**

189 * erzeugt eine neue Liste

190 * die das Objekt o nicht mehr enthaelt

191 */

192

193 public

194 LinkedList remove(Object o)

195 {

196 if ( isEmpty() )

197 return

198 this;

199

200 if ( info.equals(o) )

201 return

202 next;

203

204 next = next.remove(o);

205 // !!! Seiteneffekt

206 // Liste wird veraendert

207

208 return

209 this;

210 }

211

212 //--------------------

213

214 public

215 LinkedList concat(LinkedList l2)

216 {

217 if ( isEmpty() )

218 return

219 l2;

220

221 if ( next.isEmpty() ) {

222 next = l2;

223 } else {

224 next = next.concat(l2);

225 }

226

227 return

228 this;

229 }

230

231 //--------------------

232

233 public

234 LinkedList append(Object o)

235 {

236 return

237 concat(mkOne(o));

238 }

239

240 //--------------------

241

242 public

243 String toString()

244 {

245 if ( isEmpty() )

246 return

247 "[]";

248

249 return

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

251

252

253 }

254

255 private

256 String toString0()

257 {

258 String s = "";

259 if ( isEmpty() )

260 return

261 "]";

262

263 return

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

265 }

266

267 //--------------------

268 // forall zur Verarbeitung aller Werte einer Liste

269

270 public

271 Object forall(Accumulate ac)

272 {

273 LinkedList l1 = this;

274

275 while ( ! l1.isEmpty() ) {

276 ac.process(l1.info);

277 l1 = l1.next;

278 }

279

280 return

281 ac.getResult();

282 }

283

284 //--------------------

285 // len implementiert mit forall

286

287 public

288 int len1()

289 {

290 return

291 ((Integer)

292 forall(new NoOfElements())

293 ).intValue();

294 }

295

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

297 // toString implementiert mit forall

298

299 public

300 String toString1()

301 {

302 return

303 (String)forall(new ToString("[", ",", "]"));

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 ((Integer)

320 forall(new LocalNoOfElements())

321 ).intValue();

322 }

323

324 //--------------------

325 // Quelle hier nur aus Demozwecken aus der

326 // globalen Klasse NoOfElements uebernommen

327

328 static

329 private

330 class LocalNoOfElements

331 extends Accumulate

332 {

333 int result;

334

335 LocalNoOfElements() {

336 result = 0;

337 }

338

339 public

340 void process(Object element)

341 {

342 ++result;

343 }

344

345 public

346 Object getResult()

347 {

348 return

349 new Integer(result);

350 }

351 }

352}

Die Datei: LinkedList.java