LinkedLit模拟实现
package com.jelly.test;import java.util.ConcurrentModificationException;import java.util.Iterator;import java.util.NoSuchElementException;/** * LinkedLit模拟实现 * * @author Jelly * * @param <T> */public class MyLinkedList<T> implements Iterable<T> {private int theSize;private int modCount = 0;private Node<T> beginMarker;private Node<T> endMarker;public MyLinkedList() {clear();}public void clear() {beginMarker = new Node<T>(null, null, null);endMarker = new Node<T>(null, beginMarker, null);beginMarker.next = endMarker;theSize = 0;modCount++;}public int size() {return theSize;}public boolean isEmpty() {return size() == 0;}public boolean add(T t) {return add(size(), t);}public boolean add(int idx, T t) {addBefor(getNode(idx), t);return true;}public T get(int idx) {return getNode(idx).data;}public T set(int idx, T newVal) {Node<T> p = getNode(idx);T oldVal = p.data;p.data = newVal;return oldVal;}public T remove(int idx) {return remove(getNode(idx));}private void addBefor(Node<T> node, T t) {Node<T> newNode = new Node<T>(t, node.prev, node);newNode.prev.next = newNode;node.prev = newNode;theSize++;modCount++;}private T remove(Node<T> node) {node.next.prev = node.prev;node.prev.next = node.next;theSize--;modCount++;return node.data;}private Node<T> getNode(int idx) {Node<T> p;if (idx < 0 || idx > size()) {throw new IndexOutOfBoundsException();}if (idx < size() / 2) {p = beginMarker.next;for (int i = 0; i < idx; i++) {p = p.next;}} else {p = endMarker;for (int i = size(); i > idx; i--) {p = p.prev;}}return p;}private class LinkedListIterator implements Iterator<T> {private Node<T> current = beginMarker.next;private int expectedModCount = modCount;private boolean okToRemove = false;@Overridepublic boolean hasNext() {return current != endMarker;}@Overridepublic T next() {if (modCount != expectedModCount) {throw new ConcurrentModificationException();}if (!hasNext()) {throw new NoSuchElementException();}T nextItem = current.data;current = current.next;okToRemove = true;return nextItem;}@Overridepublic void remove() {if (modCount != expectedModCount) {throw new ConcurrentModificationException();}if (!okToRemove) {throw new IllegalStateException();}MyLinkedList.this.remove(current.prev);okToRemove = false;expectedModCount++;}}@Overridepublic Iterator<T> iterator() {return new LinkedListIterator();}private static class Node<T> {public Node(T data, Node<T> p, Node<T> n) {this.data = data;this.prev = p;this.next = n;}public T data;public Node<T> prev;public Node<T> next;}}