-
Notifications
You must be signed in to change notification settings - Fork 0
/
List.java
345 lines (302 loc) · 10.7 KB
/
List.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
/**
* <p>
* Materialien zu den zentralen NRW-Abiturpruefungen im Fach Informatik ab 2018
* </p>
* <p>
* Generische Klasse List<ContentType>
* </p>
* <p>
* Objekt der generischen Klasse List verwalten beliebig viele linear
* angeordnete Objekte vom Typ ContentType. Auf hoechstens ein Listenobjekt,
* aktuellesObjekt genannt, kann jeweils zugegriffen werden.<br />
* Wenn eine Liste leer ist, vollstaendig durchlaufen wurde oder das aktuelle
* Objekt am Ende der Liste geloescht wurde, gibt es kein aktuelles Objekt.<br />
* Das erste oder das letzte Objekt einer Liste koennen durch einen Auftrag zum
* aktuellen Objekt gemacht werden. Ausserdem kann das dem aktuellen Objekt
* folgende Listenobjekt zum neuen aktuellen Objekt werden. <br />
* Das aktuelle Objekt kann gelesen, veraendert oder geloescht werden. Ausserdem
* kann vor dem aktuellen Objekt ein Listenobjekt eingefuegt werden.
* </p>
*
* @author Qualitaets- und UnterstuetzungsAgentur - Landesinstitut fuer Schule
* @version Generisch_06 2015-10-25
*/
public class List<ContentType> {
/* --------- Anfang der privaten inneren Klasse -------------- */
private class ListNode {
private ContentType contentObject;
private ListNode next;
/**
* Ein neues Objekt wird erschaffen. Der Verweis ist leer.
*
* @param pContent das Inhaltsobjekt vom Typ ContentType
*/
private ListNode(ContentType pContent) {
contentObject = pContent;
next = null;
}
/**
* Der Inhalt des Knotens wird zurueckgeliefert.
*
* @return das Inhaltsobjekt des Knotens
*/
public ContentType getContentObject() {
return contentObject;
}
/**
* Der Inhalt dieses Kontens wird gesetzt.
*
* @param pContent das Inhaltsobjekt vom Typ ContentType
*/
public void setContentObject(ContentType pContent) {
contentObject = pContent;
}
/**
* Der Nachfolgeknoten wird zurueckgeliefert.
*
* @return das Objekt, auf das der aktuelle Verweis zeigt
*/
public ListNode getNextNode() {
return this.next;
}
/**
* Der Verweis wird auf das Objekt, das als Parameter uebergeben
* wird, gesetzt.
*
* @param pNext der Nachfolger des Knotens
*/
public void setNextNode(ListNode pNext) {
this.next = pNext;
}
}
/* ----------- Ende der privaten inneren Klasse -------------- */
// erstes Element der Liste
ListNode first;
// letztes Element der Liste
ListNode last;
// aktuelles Element der Liste
ListNode current;
/**
* Eine leere Liste wird erzeugt.
*/
public List() {
first = null;
last = null;
current = null;
}
/**
* Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthaelt,
* sonst liefert sie den Wert false.
*
* @return true, wenn die Liste leer ist, sonst false
*/
public boolean isEmpty() {
// Die Liste ist leer, wenn es kein erstes Element gibt.
return first == null;
}
/**
* Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt,
* sonst liefert sie den Wert false.
*
* @return true, falls Zugriff moeglich, sonst false
*/
public boolean hasAccess() {
// Es gibt keinen Zugriff, wenn current auf kein Element verweist.
return current != null;
}
/**
* Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses
* nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in
* der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach
* Ausfuehrung des Auftrags kein aktuelles Objekt, d.h. hasAccess() liefert
* den Wert false.
*/
public void next() {
if (this.hasAccess()) {
current = current.getNextNode();
}
}
/**
* Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles
* Objekt. Ist die Liste leer, geschieht nichts.
*/
public void toFirst() {
if (!isEmpty()) {
current = first;
}
}
/**
* Falls die Liste nicht leer ist, wird das letzte Objekt der Liste
* aktuelles Objekt. Ist die Liste leer, geschieht nichts.
*/
public void toLast() {
if (!isEmpty()) {
current = last;
}
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das
* aktuelle Objekt zurueckgegeben, andernfalls (hasAccess() == false) gibt
* die Anfrage den Wert null zurueck.
*
* @return das aktuelle Objekt (vom Typ ContentType) oder null, wenn es
* kein aktuelles Objekt gibt
*/
public ContentType getContent() {
if (this.hasAccess()) {
return current.getContentObject();
} else {
return null;
}
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent
* ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst
* geschieht nichts.
*
* @param pContent
* das zu schreibende Objekt vom Typ ContentType
*/
public void setContent(ContentType pContent) {
// Nichts tun, wenn es keinen Inhalt oder kein aktuelles Element gibt.
if (pContent != null && this.hasAccess()) {
current.setContentObject(pContent);
}
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues
* Objekt vor dem aktuellen Objekt in die Liste eingefuegt. Das aktuelle
* Objekt bleibt unveraendert. <br />
* Wenn die Liste leer ist, wird pContent in die Liste eingefuegt und es
* gibt weiterhin kein aktuelles Objekt (hasAccess() == false). <br />
* Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste
* nicht leer ist oder pContent gleich null ist, geschieht nichts.
*
* @param pContent
* das einzufuegende Objekt vom Typ ContentType
*/
public void insert(ContentType pContent) {
if (pContent != null) { // Nichts tun, wenn es keinen Inhalt gibt.
if (this.hasAccess()) { // Fall: Es gibt ein aktuelles Element.
// Neuen Knoten erstellen.
ListNode newNode = new ListNode(pContent);
if (current != first) { // Fall: Nicht an erster Stelle einfuegen.
ListNode previous = this.getPrevious(current);
newNode.setNextNode(previous.getNextNode());
previous.setNextNode(newNode);
} else { // Fall: An erster Stelle einfuegen.
newNode.setNextNode(first);
first = newNode;
}
} else { //Fall: Es gibt kein aktuelles Element.
if (this.isEmpty()) { // Fall: In leere Liste einfuegen.
// Neuen Knoten erstellen.
ListNode newNode = new ListNode(pContent);
first = newNode;
last = newNode;
}
}
}
}
/**
* Falls pContent gleich null ist, geschieht nichts.<br />
* Ansonsten wird ein neues Objekt pContent am Ende der Liste eingefuegt.
* Das aktuelle Objekt bleibt unveraendert. <br />
* Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefuegt
* und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false).
*
* @param pContent
* das anzuhaengende Objekt vom Typ ContentType
*/
public void append(ContentType pContent) {
if (pContent != null) { // Nichts tun, wenn es keine Inhalt gibt.
if (this.isEmpty()) { // Fall: An leere Liste anfuegen.
this.insert(pContent);
} else { // Fall: An nicht-leere Liste anfuegen.
// Neuen Knoten erstellen.
ListNode newNode = new ListNode(pContent);
last.setNextNode(newNode);
last = newNode; // Letzten Knoten aktualisieren.
}
}
}
/**
* Falls es sich bei der Liste und pList um dasselbe Objekt handelt,
* pList null oder eine leere Liste ist, geschieht nichts.<br />
* Ansonsten wird die Liste pList an die aktuelle Liste angehaengt.
* Anschliessend wird pList eine leere Liste. Das aktuelle Objekt bleibt
* unveraendert. Insbesondere bleibt hasAccess identisch.
*
* @param pList
* die am Ende anzuhaengende Liste vom Typ List<ContentType>
*/
public void concat(List<ContentType> pList) {
if (pList != this && pList != null && !pList.isEmpty()) { // Nichts tun,
// wenn pList und this identisch, pList leer oder nicht existent.
if (this.isEmpty()) { // Fall: An leere Liste anfuegen.
this.first = pList.first;
this.last = pList.last;
} else { // Fall: An nicht-leere Liste anfuegen.
this.last.setNextNode(pList.first);
this.last = pList.last;
}
// Liste pList loeschen.
pList.first = null;
pList.last = null;
pList.current = null;
}
}
/**
* Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess()
* == false), geschieht nichts.<br />
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das
* aktuelle Objekt geloescht und das Objekt hinter dem geloeschten Objekt
* wird zum aktuellen Objekt. <br />
* Wird das Objekt, das am Ende der Liste steht, geloescht, gibt es kein
* aktuelles Objekt mehr.
*/
public void remove() {
// Nichts tun, wenn es kein aktuelle Element gibt oder die Liste leer ist.
if (this.hasAccess() && !this.isEmpty()) {
if (current == first) {
first = first.getNextNode();
} else {
ListNode previous = this.getPrevious(current);
if (current == last) {
last = previous;
}
previous.setNextNode(current.getNextNode());
}
ListNode temp = current.getNextNode();
current.setContentObject(null);
current.setNextNode(null);
current = temp;
//Beim loeschen des letzten Elements last auf null setzen.
if (this.isEmpty()) {
last = null;
}
}
}
/**
* Liefert den Vorgaengerknoten des Knotens pNode. Ist die Liste leer, pNode
* == null, pNode nicht in der Liste oder pNode der erste Knoten der Liste,
* wird null zurueckgegeben.
*
* @param pNode
* der Knoten, dessen Vorgaenger zurueckgegeben werden soll
* @return der Vorgaenger des Knotens pNode oder null, falls die Liste leer ist,
* pNode == null ist, pNode nicht in der Liste ist oder pNode der erste Knoten
* der Liste ist
*/
private ListNode getPrevious(ListNode pNode) {
if (pNode != null && pNode != first && !this.isEmpty()) {
ListNode temp = first;
while (temp != null && temp.getNextNode() != pNode) {
temp = temp.getNextNode();
}
return temp;
} else {
return null;
}
}
}