UML
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, Serializable { // linkedList大小 transient int size = 0； // 头节点 transient Node first; // 尾节点 transient Node last; public LinkedList() {} public LinkedList(Collection c) { this(); addAll(c); } /** * 在头部插入一个元素 */ private void linkedFirst(E e) { // 原头部元素 final Node f = first; // 新建节点 final Node newNode = new Node<>(null, e, f); // 头部节点指向新建节点 first = newNode; if(f == null) { // 如果原头部节点为null，则说明链表是空的，将尾指针也指向新建节点 last = newNode; }else { // 原头部节点不为空，说明链表不为空，将原头部的前驱设置为新建节点 f.prev = newNode; } size++; modCount++; } /** * 在尾部插入元素 */ void linkedLast(E e) { // 原尾部元素 final Node l = last; // 新建节点 final Node newNode = new Node<>(l, e, null); // 将尾节点指向newNode last = newNode; if(l == null) { // 如果原尾节点为null，说明原链表为空，将first也指向新建节点 first = newNode }else { // 如果原尾节点不为null，说明原链表不为空，将原尾节点的后驱指向新建节点 l.next = newNode; } size++; modCount++; } /** * 在非空节点succ前插入节点e */ void linkedBefore(E e, Node succ) { // 获取succ的前驱 final Node pred = succ.prev; // 新建节点 final Node newNode = new Node<>(pred, e, succ); // 将succ的前驱指向newNode succ.prev = newNode; if(pred == null) { // 如果succ的原前驱为null，说明succ是头节点，则将头节点指向新建节点 first = newNode; }else { // succ的前驱不为null，则将succ前驱的next指向newNode pred.next = newNode; } size++; modCount++; } /** * 移除头节点 */ private E unlinkedFirst(Node f) { // 头节点值 final E element = f.item; // 头节点的后驱 final Node next = f.next; // 将头节点的值和next设置为空 f.item = null; f.next = null; // 将后驱设置为头节点 first = next; if(next == null) { // 如果next为null，说明只有一个元素，将last也设置为null last == null; }else { // 将next的前驱设置为null next.prev = null; } size--; modCount++; return element; } /** * 移除尾节点 */ private E unlinkLast(Node l) { // 尾节点值 final E element = l.item; // 尾节点的前驱 final Node prev = l.prev; // 将尾节点的值和前驱设置为null l.item = null; l.prev = null; // 将尾节点指向prev last = prev; if(prev == null) { // 如果prev为null，说明只有一个元素，移除后链表为空，所以把first设置为null first = null; }else { // 前驱的next设置为null prev.next = null; } size--; modCount++; return element; } /** * 删除某个节点 */ E unlink(Node x) { // 获取到x的的值，前驱、后驱 final E element = x.item; final Node next = x.next; final Node prev = x.prev; if(prev == null) { // x的前驱为null，说明x是头节点，移除x之后，next为头节点 first = next; }else { // x的前驱不为null，将x的前驱的next指向next prev.next = next; // x的前驱设为null x.prev = null; } if(next == null) { // x的后驱为null，说明是尾节点，将x的前驱设置为尾节点 last = prev; }elsee { // x的后驱不为null，将next的前驱设置为x的前驱 next.prev = prev; // 将x的后驱设置为null x.next = null; } // x的值设为null x.item = null; size--; modCount++; return element; } /** * 获取头节点元素值 * 如果头节点为null，抛出异常，不空返回item */ public E getFirst() { final Node f = first; if(f == null) { throw new NoSuchElementException(); } return f.item; } /** * 获取尾节点元素值 * 如果尾节点为null，抛出异常，不空返回item */ public E getLast() { final Node l = last; if(l == null) { throw new NoSuchElemtnException(); } return l.item; } /** * 移除头部节点 */ public E removeFirst() { final Node f = first; if(f == null) { throw new NoSuchElementException(); } return unlinkFirst(f); } /** * 移除尾部节点 */ public E removeLast() { final Node l = last; if(l == null) { throw new NoSuchElementException(); } return unlinkLast(); } /** * 添加元素至头部 */ public void addFirst(E e) { linkFirst(e); } /** * 添加元素到尾部 */ public void addLast(E e) { linkLast(e); } /** * 是否包含对象o * 如果对象o的索引位置不等于-1，则表示包含对象o */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * 返回元素数量 */ public int size() { return size; } /** * 添加元素到头部 */ public boolean add(E e) { linkFist(e); return true; } /** * 移除某个元素。 如果移除对象存在返回true，否则返回false */ public boolean remove(Object o) { // 移除对象为null，则从头部开始查找第一个为null的元素 if(o == null) { for(Node x = first; x != null; x = x.next) { if(x.item == null) { // 找到为null的元素，进行移除，返回true unlink(x); return true; } } } // 移除元素不为null，从头部开始查找第一个与o相等得元素 else { for(Node x = first; x != null; x = x.next) { if(o.equals(x.item)) { // 找到与object相等的元素，进行移除，返回true unlink(x); return true; } } } // 没有找到，返回false return false; } /** * 在尾部添加一个集合c */ public boolean addAll(Collection c) { return addAll(size, c); } /** * 添加一个集合c在index位置 */ public boolean addAll(int index, Collection c) { // 检查index对象是否越界，index大于等于0，小于等于size checkPositionIndex(index); // 集合转数组 Object[] a = c.toArray(); int numNew = a.length; // 如果添加的元素个数为0，返回false if(numNew == 0) { return false; } Node pred, succ; // 如果index == size，说明是添加在尾部，只需要获取到尾部节点即可 if(index == size) { succ = null; pred = last; } // 添加位置不是尾部，不需要获取到index位置的元素succ，并获取到succ的前驱 else { succ = node(index); pred = succ.prev; } // 遍历数组形成链表 for(Object o : a) { // 强转 E e = (E) o; // 新建节点 Node newNode = new Node<>(pred, e, null); // 如果pred为null，说明是空链表，将新建节点设置头节点 if(pred == null) { first = newNode; } // 不是空链表，将当前节点设为pred的后驱 else { pred.next = newNode; } // 新建节点为pred pred = newNode; } // 如果index位置不存在节点，即添加在尾部 if(succ == null) { // 最后一个新建节点作为last last = newNode; } // index位置存在节点 else { // 最后一个集合元素的next指向原index位置元素 pred.next = succ; // 原index位置的元素的前驱指向集合最后一个节点 succ.prev = pred; } size++; modCount++; return true; } /** * 清空链表 * 遍历节点将每个节点的item，next、prev置空，同时将first、、last置空，size置为0 */ public void clear() { // 遍历节点，置空item。next、prev for(Node x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } // 置空first、last first = last = null; // size置为0 size = 0; modCount++; } /** * 获取index位置的元素值 */ public E get(int index) { // 检查是否越界 checkElementIndex(index); return node(index).item; } /** * 将index位置的元素的元素自设置为element */ public E set(int index, E element) { // 检车是否越界 checkElementIndex(index); // 获取index位置的元素 Node x = node(index); // 获取到旧元素值 E oldVal = x.item; // 赋值为新的元素值 x.item = element; // 返回旧的元素值 return oldVal; } /** * 添加元素至index位置 */ public void add(int index, E element) { // 检查是否越界 checkPositionIndex(index); if(index == size) { // 如果index == size，那么添加到队列尾部 linkLast(element); }else { // 添加在index位置，找到原index位置元素，添加在其位置，原元素后移一位 linkBefore(element, node(index)); } } /** * 移除index位置的元素 */ public E remove(int index) { // 检查是否越界 checkElementIndex(index); return unlink(node(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } private String checkElementIndex(int index) { if(!isElementIndex(index)) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } private void checkPositionIndex(int index) { if(!isPositionIndex(index)) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } /** * 获取index位置的元素 */ Node node(int index) { // 如果是前半部分 if(index < (size >> 1)) { // 从头开始向后查找 Node x = first; for(int i = 0; i < index; i++) { x = x.next; } return x; } // 如果是后半部分 else { Node x = last; // 从尾部开始向前查找 for(int i = size - 1; i > index; i--) { x = x.prev; } return x; } } /** * 获取对象在链表中位置（相对于头部） */ public int indexOf(Object o) { int index = 0; // 对象o为null if(o == null) { for(Node x = first; x != null; x.next) { if(x.item == null) { return index; } index++; } } // 对象o不为null else { for(Node x = first; x != null; x.next) { if(o.equals(x.item)) { return index; } index++; } } return -1; } /** * 获取对象在链表中位置（相对于尾部） */ public int lastIndexOf(Object o) { int index = size; // 对象o为null if(o == null) { for(Node x = last; x != null; x = x.prev) { index--; if(x.item == null) { return index; } } } // 对象o不为null else { for(Node x = last; x != null; x.prev) { index--; if(o.equals(x.item)) { return index; } } } return -1; } /** * 获取头部元素 */ public E peek() { final Node f = first; return (f == null) ? null : f.item; } /** * 获取头部元素 */ public E element() { return getFirst(); } /** * 移除一个元素，从头部移除 */ public E poll() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } /** * 移除一个元素，模式移除头部，链表为空，将会抛出异常 */ public E remove() { return removeFirst(); } /** * 添加一个元素到尾部 */ public boolean offer(E e) { return add(e); } /** * 添加一个元素到头部 */ public boolean offerFirst(E e) { addFirst(e); return retrue; } /** * 添加一个元素到尾部 */ public boolean offerLast(E e) { addLast(e); return true; } /** * 返回头部元素值 */ public E peekFirst() { final Node f = first; return (f == null) ? null : f.item; } /** * 返回尾部元素值 */ public E peekLast() { final Node l = last; return (l == null) ? null : l.item } /** * 移除头部元素 */ public E pollFirst() { final Node f = first; return (f == null) ? f : unlinkFirst(f); } /** * 移除尾部元素 */ public E pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l); } /** * 头部添加元素 */ public void push(E e) { addFirst(e); } /** * 头部移除元素 */ public void pop() { return removeFirst(); } /** * 链表转数组 */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for(Node x = first; x != null; x = x.next) { result[i++] = x.item; } return result; } /** * 序列化 */ private void writeObject(ObjectOutputStream s) throw IOException { s.defaultWriteObject(); s.writeInt(size); for(Node x = first; x != null; x = x.next) { s.writeObject(x.item); } } /** * 反序列化 */ private void readObject(ObjectInputStream s) throw IOEception{ s.defaultReadObject(); int size = s.readInt(); for(int i = 0; i < size; i++) { linkLast((E)s.readObject()); } } private static class Node { E item; Node next; Node prev; Node(Node , prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }}
| add(E e) | 添加在尾部 |
| remove(Object o) | 找到并移除 |
| addFirst(E e) | 头部添加一个元素 |
| removeFirst() | 头部移除一个元素，如果链表为空，抛出异常 |
| addLast(E e) | 尾部添加一个元素 |
| removeLast() | 尾部移除一个元素，如果链表为空，抛出异常 |
| remove() | 调用removeFirst(), 从头部移除一个元素 |
| peek() | 取到第一个元素，不会对元素进行移除 |
| element() | 取到第一个元素，不会对元素进行移除，但如果链表为空，抛出异常 |
| poll() | 头部移除一个元素，链表空时返回null |
| remove() | 头部移除一个元素，链表为空时抛出异常 |
| offer(E) | 添加元素到链表尾部 |
| offerFirst(E) | 添加元素到链表头部 |
| offerLast(E) | 添加元素到链表尾部 |
| push() | 头部添加一个元素 |
| pop() | 头部移除一个元素，链表为空时抛出异常 |