Datei: LinkedList.java

1/**

2 * @author Uwe Schmidt

3 *

4 * Eine Klasse fuer verkettete Listen

5 *

6 * Die leere Liste wird durch das einzige aus der Klasse Empty

7 * erzeugte Objekt repraesentiert, dessen Referenz int der

8 * statischen Variablen empty gespeichert wird.

9 *

10 * Diese Referenz muss aber int der erzeugenden statischen

11 * Funktion mkEmpty int eine Referenz des jeweils erforderlichen

12 * Listentyps knvertiert werden.

13 *

14 * Dieses geht nur mit einer ungeprueften Konversion,

15 * ist aber moeglich, da die Resultate der Empty-Methoden nicht von

16 * dem Typparameter E abhaengen

17 *

18 * Die Hilfsklassen Empty und Node und die Konstruktoren

19 * sind nicht oeffentlich,

20 * Sie werden nur ueber die statischen Methoden aus LinkedList

21 * aufgerufen.

22 *

23 */

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

27public abstract

28class LinkedList<E> {

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

31 //

32 // die leere Liste wird durch die Referenz

33 // in der Variablen empty repraesentiert

35 protected static final

36 LinkedList<Object> empty = new Empty<Object>();

38 //--------------------

40 @SuppressWarnings("unchecked")

41 public static

42 <E> LinkedList<E> mkEmptyList() {

43 return

44 (LinkedList<E>)empty; // unchecked cast

45 }

47 public static

48 <E> LinkedList<E> mkOne(E info) {

49 LinkedList<E> r = mkEmptyList();

50 return

51 r.cons(info);

52 }

54 //--------------------

56 public

57 LinkedList<E> cons(E info)

58 {

59 return

60 new Node<E>(info, this);

61 }

63 public

64 boolean isEmpty() {

65 return

66 false;

67 }

69 public

70 E hd()

71 throws IndexOutOfBoundsException

72 {

73 throw

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

75 }

77 public

78 LinkedList<E> tl()

79 throws IndexOutOfBoundsException

80 {

81 throw

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

83 }

85 public abstract

86 int len();

88 public

89 E at(int i)

90 throws IndexOutOfBoundsException

91 {

92 throw

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

94 }

96 public abstract

97 boolean isIn(E o);

99 public

100 LinkedList<E> insert(E o) {

101 if ( isIn(o) )

102 return

103 this;

104

105 return

106 cons(o);

107 }

108

109 public abstract

110 LinkedList<E> remove(E o);

111

112

113 public abstract

114 LinkedList<E> concat(LinkedList<E> l2);

115

116 public

117 LinkedList<E> append(E o) {

118 return

119 concat(mkOne(o));

120 }

121}

122

123//--------------------

124//

125// Keine Methode in Empty besitzt als Resultat E, daher

126// ist die Typkonversion in mkEmpty in der Klasse List harmlos

127

128class Empty<E> extends LinkedList<E> {

129 // nicht public

130 Empty() {

131 }

132

133 public

134 boolean isEmpty() {

135 return

136 true;

137 }

138

139 public

140 int len() {

141 return 0;

142 }

143

144 public

145 boolean isIn(E o) {

146 return

147 false;

148 }

149

150 public

151 LinkedList<E> remove(E o) {

152 return

153 this;

154 }

155

156 public

157 LinkedList<E> concat(LinkedList<E> l2) {

158 return l2;

159 }

160}

161

162//--------------------

163

164class Node<E> extends LinkedList<E> {

165 private

166 E info;

167

168 private

169 LinkedList<E> next;

170

171 Node(E info, LinkedList<E> next) {

172 this.info = info;

173 this.next = next;

174 }

175

176 public

177 int len() {

178 return

179 1 + next.len();

180 }

181

182 public

183 boolean isIn(E o) {

184 return

185 info.equals(o)

186 ||

187 next.isIn(o);

188 }

189

190 public

191 LinkedList<E> remove(E o) {

192 if (info.equals(o))

193 return next;

194 next = next.remove(o);

195 return

196 this;

197 }

198

199 public

200 LinkedList<E> concat(LinkedList<E> l2) {

201 if (next.isEmpty())

202 next = l2;

203 else

204 next = next.concat(l2);

205 return

206 this;

207 }

208}

209

210//--------------------

Die Datei: LinkedList.java