Commit | Line | Data |
---|---|---|
54d3f5b3 | 1 | |
78c725c5 JB |
2 | @ClassPreamble ( |
3 | author = "Jérôme Benoit", | |
4 | date = "05/12/2011" | |
5 | ) | |
54d3f5b3 JB |
6 | public class Liste extends Structure { |
7 | ||
8 | private class IntNode { | |
9 | private int data; | |
10 | private IntNode next; | |
11 | ||
12 | IntNode(int value) { | |
13 | setData(value); | |
14 | setNext(null); | |
15 | } | |
16 | ||
17 | IntNode(int value, IntNode nextNode) { | |
18 | setData(value); | |
19 | setNext(nextNode); | |
20 | } | |
21 | ||
22 | public int getData() { | |
23 | return data; | |
24 | } | |
25 | ||
26 | public void setData(int value) { | |
27 | data = value; | |
28 | } | |
29 | ||
30 | public IntNode getNext() { | |
31 | return next; | |
32 | } | |
33 | ||
34 | public void setNext(IntNode nextNode) { | |
35 | next = nextNode; | |
36 | } | |
37 | ||
38 | } | |
39 | ||
40 | private IntNode headNode; | |
41 | private int list_counter; | |
42 | ||
43 | Liste() { | |
44 | setHeadNode(null); | |
45 | setSize(0); | |
46 | } | |
47 | ||
48 | private boolean isEmpty() | |
49 | { | |
50 | return getHeadNode() == null; | |
51 | } | |
52 | ||
53 | public int getSize() { | |
54 | return list_counter; | |
55 | } | |
56 | ||
57 | public void setSize(int size) { | |
58 | list_counter = size; | |
59 | } | |
60 | ||
61 | public void setHeadNode(IntNode node) { | |
62 | headNode = node; | |
63 | } | |
64 | ||
65 | public IntNode getHeadNode() { | |
66 | return headNode; | |
67 | } | |
68 | ||
69 | public boolean inserer(int value) { | |
70 | boolean found = false; | |
71 | if (isEmpty()) { | |
72 | headNode = new IntNode(value); | |
73 | list_counter++; | |
74 | return true; | |
75 | } else if (value == headNode.getData()) { | |
76 | found = true; | |
77 | return true; | |
78 | } else { | |
79 | IntNode nodeCursorNext = headNode.getNext(); | |
80 | while (nodeCursorNext != null) { | |
81 | if (value == nodeCursorNext.getData()) { | |
82 | found = true; | |
83 | break; | |
84 | } else { | |
85 | nodeCursorNext = nodeCursorNext.getNext(); | |
86 | } | |
87 | } | |
88 | if (!found) { | |
89 | headNode = new IntNode(value, headNode); | |
90 | list_counter++; | |
91 | } | |
92 | // Insertion in a linked list can't fail | |
93 | return true; | |
94 | } | |
95 | } | |
96 | ||
97 | public boolean supprimer(int value) { | |
98 | boolean deleted = false; | |
99 | if (isEmpty()) { | |
100 | return deleted; | |
101 | } else if (value == headNode.getData()) { | |
102 | headNode = headNode.getNext(); | |
103 | deleted = true; | |
104 | list_counter--; | |
105 | } else { | |
106 | IntNode nodeCursor = headNode; | |
107 | IntNode nodeCursorNext = headNode.getNext(); | |
108 | while (nodeCursorNext != null) { | |
109 | if (value == nodeCursorNext.getData()) { | |
110 | nodeCursor.setNext(nodeCursorNext.getNext()); | |
111 | deleted = true; | |
112 | list_counter--; | |
113 | break; | |
114 | } else { | |
115 | nodeCursor = nodeCursorNext; | |
116 | nodeCursorNext = nodeCursorNext.getNext(); | |
117 | } | |
118 | } | |
119 | } | |
120 | return deleted; | |
121 | } | |
122 | ||
123 | public void afficher() { | |
c7c510eb | 124 | String className = this.getClass().getSimpleName(); |
5731ae5f | 125 | int i = 0; |
c7c510eb | 126 | System.out.println("---- " + className + " ----"); |
54d3f5b3 | 127 | if (isEmpty()) { |
c7c510eb | 128 | return; |
54d3f5b3 | 129 | } else if (headNode.getNext() == null) { |
5731ae5f | 130 | System.out.println("element " + i + " : " + headNode.getData()); |
54d3f5b3 | 131 | } else { |
5731ae5f JB |
132 | IntNode nodeCursorNext = headNode.getNext(); |
133 | System.out.println("element " + i + " : " + headNode.getData()); | |
134 | i++; | |
135 | while (nodeCursorNext != null) { | |
136 | System.out.println("element " + i + " : " + nodeCursorNext.getData()); | |
137 | nodeCursorNext = nodeCursorNext.getNext(); | |
54d3f5b3 JB |
138 | i++; |
139 | } | |
54d3f5b3 JB |
140 | } |
141 | } | |
142 | ||
97929775 | 143 | public void compacter(int nElements) { |
5731ae5f | 144 | // Remove the first nElements |
dbd5b977 | 145 | if (isEmpty() || nElements == 0) { |
5731ae5f | 146 | return; |
22758baf | 147 | } else if (headNode != null && headNode.getNext() == null) { |
5731ae5f JB |
148 | headNode = null; |
149 | } else { | |
150 | // We have at least 2 nodes in the linked list | |
22758baf | 151 | IntNode nodeCursor = headNode; |
5731ae5f | 152 | int i = 0; |
22758baf | 153 | // Go to the node at the nElements place |
39d73320 | 154 | while (i < nElements - 1 && nodeCursor.getNext() != null && nElements > 1) { |
5731ae5f JB |
155 | nodeCursor = nodeCursor.getNext(); |
156 | i++; | |
157 | } | |
158 | // Set the nElements + 1 node as the root node | |
22758baf JB |
159 | // It might be null |
160 | setHeadNode(nodeCursor.getNext()); | |
5731ae5f | 161 | } |
97929775 JB |
162 | } |
163 | ||
54d3f5b3 | 164 | } |