链表是一种数据结构，而LinkedList的实现原理就是链表，相对于ArrayList底层实现为数组，链表在循环遍历方面的效率相比ArrayList要差一些，但在插入和删除的时候优势明显。
写代码实现链表：
package cn.tom.list; import java.util.Iterator; import java.util.ListIterator; import java.util.NoSuchElementException; /** * Created by lenovo on 2017/3/6. * 双项链表的实现 * 双项链表结构改造头尾相连双向链表结构 */ public class LinkList<T> { int size = 0; Node<T> first; Node<T> last; void add(T t) { final Node<T> l = last; final Node<T> newNode = new Node<T>(l, t, null); last = newNode; if (l == null) { first = newNode; //双项链表结构改造头尾相连双向链表结构 // first = newNode; // last.next = first; // first.pre = last; } else { l.next = newNode; //双项链表结构改造头尾相连双向链表结构 // l.next = newNode; // last.next = first; // first.pre = last; } size++; } Iterator<T> iterator() { return new ListItr(0); } public ListIterator<T> listIterator(int index) { if (!checkIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); return new ListItr(index); } private String outOfBoundsMsg(int index) { return "index:" + index + ",size:" + size; } private boolean checkIndex(int index) { return index >= 0 && index <= size; } class ListItr implements ListIterator<T> { private Node<T> lastReturned; private Node<T> next; private int nextIndex; public ListItr(int index) { next = index == size ? null : node(index); nextIndex = index; } @Override public boolean hasNext() { return nextIndex < size; } @Override public T next() { if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; //双项链表结构改造头尾相连双向链表结构 // nextIndex++; // nextIndex = nextIndex == size ? 0 : nextIndex; return lastReturned.item; } @Override public boolean hasPrevious() { return nextIndex > 0; } @Override public T previous() { if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.pre; nextIndex--; //双项链表结构改造头尾相连双向链表结构 // nextIndex--; // nextIndex = nextIndex == 0 ? size : nextIndex; return lastReturned.item; } @Override public int nextIndex() { return nextIndex; } @Override public int previousIndex() { return nextIndex - 1; } @Override public void remove() { } @Override public void set(T t) { } @Override public void add(T t) { } } private Node<T> node(int index) { if (index < size >> 1) { Node<T> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node<T> x = last; for (int i = size - 1; i > index; i--) { x = x.pre; } return x; } } class Node<T> { private Node<T> pre; private T item; private Node<T> next; public Node(Node<T> pre, T element, Node<T> next) { this.pre = pre; this.item = element; this.next = next; } } public static void main(String[] args) { LinkList<String> list = new LinkList<String>(); list.add("1"); list.add("2"); list.add("3"); for (ListIterator<String> item = list.listIterator(3); item.hasPrevious(); ) { //System.out.println(item.nextIndex()); System.out.println(item.previous()); } System.out.println("00000000000000000000000000000000000000000"); /*for (Iterator<String> iterator = list.iterator(); iterator.hasNext();) { System.out.println(iterator.next()); }*/ } }
