public class LinkedList<T> implements Iterable<T> { private int size; private int modCount; private final Node<T> startNode; private final Node<T> endNode;
public MyLinkedList(){ this.startNode = new Node<T>(null, null, null); this.endNode = new Node<T>(null, this.startNode, null); this.startNode.next = this.endNode;
this.size = 0; modCount++; }
public int size(){ return size; }
public boolean isEmpty(){ return size() == 0; }
public boolean contains(T item){ Node<T> curr = startNode; while (curr.next != null) { curr = curr.next; if (curr.data == item) return true; } return false; }
public boolean add(T item) { add(size(), item); return true; }
public void add(int index, T item){ addBefore(getNode(index, 0, size()), item); }
private void addBefore(Node<T> node, T item){ Node<T> newNode = new Node<T>(item, node.prev, node); newNode.prev.next = newNode; node.prev = newNode; size++; modCount++; }
public boolean remove(T item){ Node<T> curr = startNode; while (curr.next != endNode){ curr = curr.next; if (curr.data == item){ remove(curr); return true; } } return false; }
public void remove(int index){ remove(getNode(index)); }
private void remove(Node<T> node){ node.prev.next = node.next; node.next.prev = node.prev; size--; modCount++; }
public Node<T> getNode(int index){ return getNode(index, 0, size() - 1); }
public Node<T> getNode(int index, int lower, int upper){ Node<T> node; if (index < lower || index > upper) throw new IndexOutOfBoundsException(); if (index < size() / 2){ node = startNode.next; for (int i = 0; i < index; i++) node = node.next; }else { node = endNode; for (int i = size(); i > index; i--) node = node.prev; } return node; }
public T get(int index){ return getNode(index).data; }
public T set(int index, T item){ Node<T> node = getNode(index); T oldValue = node.data; node.data = item; return oldValue; }
public Iterator<T> iterator() { return new LinkedListIterator(); }
public static class Node<T>{ public T data; public Node<T> prev; public Node<T> next;
public Node(T data, Node<T> prev, Node<T> next){ this.data = data; this.prev = prev; this.next = next; } }
public class LinkedListIterator implements Iterator<T>{ private Node<T> curr = startNode.next; private int expectedModCount = modCount; private boolean okToRemove = false;
public boolean hasNext() { return curr != endNode; }
public T next() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (!hasNext()) throw new NoSuchElementException(); T nextItem = curr.data;; curr = curr.next; okToRemove = true; return nextItem; }
public void remove() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (!okToRemove) throw new IllegalStateException(); MyLinkedList.this.remove(curr.prev); expectedModCount++; okToRemove = false; } } }
|