1 | public class Cons
|
2 | {
|
3 | public Object obj; // das Objekt in dieser Zelle
|
4 | public Cons next; // Verweis auf die naechste Zelle
|
5 | public Cons(Object obj) {
|
6 | this.obj = obj;
|
7 | next = null;
|
8 | }
|
9 | }
|
10 |
|
11 | public class ConsList
|
12 | {
|
13 | private Cons head, foot; // Kopf und Fuss der Liste
|
14 | public ConsList() { head = foot = null; /* neue leere Liste */ }
|
15 | public boolean contains(Object obj) { return contains(head, obj); }
|
16 | protected boolean contains(Cons cons, Object obj) {
|
17 | if (cons == null) return false;
|
18 | else if (cons.obj == obj) return true;
|
19 | else return contains(cons.next, obj);
|
20 | }
|
21 | public void print() {
|
22 | System.out.print("Liste [");
|
23 | print(head); // rekursive Ausgabe der Cons-Zellen
|
24 | System.out.println("]");
|
25 | }
|
26 | protected void print(Cons cons) {
|
27 | if (cons == null) return ; // letzte Zelle erreicht
|
28 | System.out.print(cons.obj); // Objekt ausgeben
|
29 | if (cons.next != null) {
|
30 | System.out.print(", ");
|
31 | print(cons.next); // Rekursiv weiter
|
32 | }
|
33 | }
|
34 | public void insert(Object obj) {
|
35 | Cons cons = new Cons(obj); // neue Cons-Zelle
|
36 | cons.next = head; // vorne anfuegen..
|
37 | head = cons; // .. und Kopf der Liste anpassen
|
38 | if (foot == null) foot = cons; // eventuell auch den Fuss
|
39 | }
|
40 | public void append(Object obj) {
|
41 | Cons cons = new Cons(obj); // neue Cons-Zelle
|
42 | if (foot == null) head = foot = cons; // genau eine Cons-Zelle
|
43 | else { // hinten anfuegen und Fuss anpassen
|
44 | foot.next = cons;
|
45 | foot = cons;
|
46 | }
|
47 | }
|
48 | public void remove(Object obj) {
|
49 | if (head == null) return ;
|
50 | if (head.obj == obj) {
|
51 | if (head == foot) foot = head = null;
|
52 | else head = head.next; // erste Cons-Zelle entfernen
|
53 | } else remove(head, head.next, obj);
|
54 | }
|
55 | protected void remove(Cons prev, Cons cons, Object obj) {
|
56 | if (cons == null) return ;
|
57 | if (cons.obj == obj) {
|
58 | // vorherige Cons-Zelle auf Nachfolgende zeigen lassen,
|
59 | // somit faellt 'cons' aus der Liste
|
60 | prev.next = cons.next;
|
61 | if (foot == cons) // evtl. Fuss anpassen
|
62 | foot = prev;
|
63 | } else remove(cons, cons.next, obj);
|
64 | }
|
65 | public boolean isEmpty() { return head == null; }
|
66 | public Object removeHead() {
|
67 | if (head == null) return null;
|
68 | Object res = head.obj;
|
69 | if (head == foot) head = foot = null;
|
70 | else head = head.next;
|
71 | return res;
|
72 | }
|
73 |
|
74 | public static void main (String ... args) {
|
75 | // Kleines Testprogramm fuer Listen:
|
76 | ConsList l = new ConsList();
|
77 | System.out.println("leer? " + l.isEmpty());
|
78 | String s1 = "Hallo", s2 = "Welt";
|
79 | l.insert(s1);
|
80 | System.out.println("leer? " + l.isEmpty());
|
81 | l.print();
|
82 | l.insert(s2);
|
83 | l.print();
|
84 | l.remove(s2);
|
85 | l.print();
|
86 | l.append(s2);
|
87 | l.print();
|
88 | l.remove(s2);
|
89 | l.remove(s1);
|
90 | l.print();
|
91 | System.out.println("leer? " + l.isEmpty());
|
92 | }
|
93 | }
|