数据结构 - 单链表

  1 package collections;
  2 
  3 import java.util.Iterator;
  4 
  5 public class SingleLinkedList<T> implements Iterable {
  6     private Node<T> head;
  7     private Node<T> cur;
  8     private int len;
  9 
 10     @Override
 11     public Iterator iterator() {
 12         return new SingleLinkedListIterator<>(head);
 13     }
 14 
 15     public SingleLinkedList() {
 16         this.head = new Node<>(null, null);
 17         this.cur = head;
 18         this.len = 0;
 19     }
 20 
 21     /**
 22      * add before
 23      *
 24      * @param var Node{var}
 25      */
 26     public void push(T var) {
 27         head.setNext(new Node<>(var, head.getNext()));
 28         len++;
 29     }
 30 
 31     /**
 32      * add last
 33      *
 34      * @param var Node{var}
 35      */
 36     public void append(T var) {
 37         Node<T> newNode = new Node<>(var, null);
 38         cur.setNext(newNode);
 39         cur = newNode;
 40         len++;
 41     }
 42 
 43     /**
 44      * add element by index
 45      *
 46      * @param index   add position
 47      * @param element element
 48      */
 49     public void insert(int index, T element) {
 50         if (isEmpty() && index == 0) {
 51             push(element);
 52         }
 53         checkIndex(index);
 54         Node<T> lastNode = getLastNode(index);
 55         lastNode.setNext(new Node<>(element, lastNode.getNext()));
 56         len++;
 57     }
 58 
 59     /**
 60      * remove last
 61      */
 62     public void pop() {
 63         if (isEmpty()) {
 64             return;
 65         }
 66         Node<T> lastNode = head;
 67         while (lastNode.getNext().getNext() != null) {
 68             lastNode = lastNode.getNext();
 69         }
 70         lastNode.setNext(null);
 71         cur = lastNode;
 72         len--;
 73     }
 74 
 75     /**
 76      * check index
 77      *
 78      * @param index position
 79      */
 80     private void checkIndex(int index) {
 81         if (index > len - 1 || index < 0) {
 82             throw new ArrayIndexOutOfBoundsException();
 83         }
 84     }
 85 
 86     /**
 87      * get last node by index
 88      *
 89      * @param index current index
 90      * @return last node
 91      */
 92     private Node<T> getLastNode(int index) {
 93         int i = 0;
 94         Node<T> lastNode = head;
 95         while (i++ != index && lastNode.getNext().getNext() != null) {
 96             lastNode = lastNode.getNext();
 97         }
 98         return lastNode;
 99     }
100 
101     /**
102      * remove node by index
103      *
104      * @param index node index from 0 to (length - 1)
105      */
106     public void pop(int index) {
107         checkIndex(index);
108         // left remove
109         if (index == 0) {
110             Node<T> firstNode = head.getNext();
111             head.setNext(firstNode.getNext());
112             firstNode.setNext(null);
113             len--;
114             return;
115         }
116         // right remove
117         if (index == len - 1) {
118             pop();
119             return;
120         }
121         // center remove
122         Node<T> lastNode = getLastNode(index);
123         Node<T> curNode = lastNode.getNext();
124         lastNode.setNext(curNode.getNext());
125         curNode.setNext(null);
126         len--;
127     }
128 
129     /**
130      * remove element by target if existed
131      *
132      * @param target element removed
133      */
134     public void remove(T target) {
135         Node<T> lastNode = head;
136         Node<T> curNode = head;
137         while (curNode != null && curNode.getVar() != target) {
138             lastNode = curNode;
139             curNode = curNode.getNext();
140         }
141         if (curNode != null) {
142             lastNode.setNext(curNode.getNext());
143             curNode.setNext(null);
144             len--;
145         }
146     }
147 
148     /**
149      * check element exist
150      *
151      * @param element element checked
152      * @return if exist return index, if not return -1
153      */
154     public int contain(T element) {
155         if (isEmpty()) {
156             return -1;
157         }
158         int i = 0;
159         Node<T> currentNode = head.getNext();
160         while (currentNode.getVar() != element) {
161             currentNode = currentNode.getNext();
162             if (currentNode == null) {
163                 return -1;
164             }
165             i++;
166         }
167         return i;
168     }
169 
170     /**
171      * update element value
172      *
173      * @param index element position
174      * @param element element updated
175      */
176     public void update(int index, T element) {
177         if (isEmpty()) {
178             return;
179         }
180         checkIndex(index);
181         getLastNode(index).getNext().setVar(element);
182     }
183 
184     /**
185      * get length
186      *
187      * @return size of list
188      */
189     public int length() {
190         return len;
191     }
192 
193     /**
194      * check empty
195      *
196      * @return if empty true, else false
197      */
198     public boolean isEmpty() {
199         return len == 0;
200     }
201 
202 }
203 
204 class Node<T> {
205     private T var;
206     private Node<T> next;
207 
208     public Node(T var, Node<T> next) {
209         this.var = var;
210         this.next = next;
211     }
212 
213     public T getVar() {
214         return var;
215     }
216 
217     public void setVar(T var) {
218         this.var = var;
219     }
220 
221     public Node<T> getNext() {
222         return next;
223     }
224 
225     public void setNext(Node<T> next) {
226         this.next = next;
227     }
228 }
229 
230 class SingleLinkedListIterator<T> implements Iterator {
231 
232     private Node<T> cursor;
233 
234     public SingleLinkedListIterator(Node<T> node) {
235         this.cursor = node;
236     }
237 
238     @Override
239     public boolean hasNext() {
240         if (cursor == null) {
241             return false;
242         }
243         boolean flag = cursor.getNext() != null;
244         cursor = cursor.getNext();
245         return flag;
246     }
247 
248     @Override
249     public Object next() {
250         return cursor;
251     }
252 }