日常开发中，数组和集合使用的很多，而数组的无序插入和删除效率都是偏低的，这点在学习ArrayList源码的时候就知道了，因为需要把要
插入索引后面的所以元素全部后移一位。
而本文会详细讲解链表，可以解决数组的部分问题，相比数组的大小不可更改，链表更加灵活，在学习LinkedList源码对链表有了一个大致的
了解。
ArrayList和LinkedList源码请参考：
本文我们会学习：单链表、双端链表、有序链表、双向链表和有迭代器的链表，并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述
栈和队列，如何用链表代替数组来实现栈和队列。
链节点：
在链表中，每个元素都被包含在链节点Link中。一个链节点是某个类的对象，这个类可以叫做Link。每个Link对象都包含对下一个Link引用的
字段（通常叫next）。但是链表本身有个字段指向对第一个Link的引用。
代码示例：
public class Link { private Object data; private Link next;} 单链表：
单链表的机构比较简单，每个Node包含data和next(指向下个Node)，最后一个Node的next指向null
图例：
代码实现：
public class SingleLinkList{ private int size; //链表长度大小 private Node head; //头结点 public SingleLinkList() { size = 0; head = null; } //添加元素到head public void addFirst(E data) { Node newNode = new Node(data); if (size == 0) { head = newNode; } else { newNode.next = head; head = newNode; } size++; } //删除头结点 public E deleteFirst() { final E data = (E)head.data; head = head.next; size--; return data; } //查询某个元素是否存在 public E find(E object) { Node current = head; int tempSize = size; while (tempSize > 0) { if (object == current.data) { return (E)current.data; } else { current = current.next; } tempSize--; } return null; } //删除链表中某个元素 public boolean delete(E object) { if (null != object) { Node current = head; Node previous = head; while (!object.equals(current.data)) { if (current.next == null) { return false; } else { previous = current; current = current.next; } } if (current == head) { head = current.next; } else { previous.next = current.next; } size--; } return true; } //遍历打印链表 public void displayList() { Node current = head; int tempSize = size; if (tempSize == 0) { System.out.print("[]"); } else { System.out.print("["); while (current != null) { if (current.next == null) { System.out.print(current.data);; } else { System.out.print(current.data + "-->");; } current = current.next; } System.out.println("]"); } } public boolean isEmpty() { return size == 0; } private static class Node { E data; Node next; Node(E data) { this.data = data; } }}
public static void main(String[] args) { SingleLinkList singleList = new SingleLinkList (); singleList.addFirst(22); //添加节点 singleList.addFirst(44); singleList.addFirst(66); singleList.addFirst(88); singleList.displayList(); //打印链表结构 singleList.delete(44); //删除某个节点 singleList.displayList(); System.out.println(singleList.find(66)); //查询某个节点 } 打印结果：[88-->66-->44-->22][88-->66-->22]66
双端链表：
双端链表和单向链表很相似，但是增加了一个新特性：就是对最后一个节点的引用，最后一个节点定义为tail
PS：双端链表不是双向链表，只能单向遍历，只是可以在双端添加/删除数据
图例：
代码实现：
public class DoubleLinkList{ private int size; //链表长度大小 private Node head; //头结点 private Node tail; //尾结点 public DoubleLinkList() { size = 0; head = null; tail = null; } //添加元素到head public void addFirst(E data) { Node newNode = new Node(data); if (size == 0) { head = newNode; tail = newNode; } else { newNode.next = head; head = newNode; } size++; } //添加元素到tail public void addLast(E data) { Node newNode = new Node(data); if (size == 0) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } size++; } //删除头结点 public E deleteFirst() { if (isEmpty()) { return null; } final E data = (E)head.data; if (head.next == null) { tail = null; } head = head.next; size--; return data; } //删除尾结点 public E deleteLast() { if (isEmpty()) { return null; } final E data = (E)tail.data; if (head.next == null) { head = null; } int tempSize = size; Node current = head; Node previous = head; while (tempSize > 0) { if (current.next == null) { previous.next = null; break; } previous = current; current = current.next; tempSize--; } tail = previous; size--; return data; } //查询某个元素是否存在 public E find(E object) { Node current = head; int tempSize = size; while (tempSize > 0) { if (object == current.data) { return (E)current.data; } else { current = current.next; } tempSize--; } return null; } //删除链表中某个元素 public boolean delete(E object) { if (null != object) { Node current = head; Node previous = head; while (!object.equals(current.data)) { if (current.next == null) { return false; } else { previous = current; current = current.next; } } if (current == head) { head = current.next; }else { previous.next = current.next; } size--; } return true; } //遍历打印链表 public void displayList() { Node current = head; int tempSize = size; if (tempSize == 0) { System.out.print("[]"); } else { System.out.print("["); while (current != null) { if (current == tail) { System.out.print(current.data); break; } else { System.out.print(current.data + "-->"); } current = current.next; } System.out.println("]"); } } public boolean isEmpty() { return size == 0; } private static class Node { E data; Node next; Node(E data) { this.data = data; } }}
public static void main(String[] args) { DoubleLinkList doubleLinkList = new DoubleLinkList (); doubleLinkList.addFirst(22); //添加节点 doubleLinkList.addFirst(44); doubleLinkList.addLast(66); doubleLinkList.addLast(88); doubleLinkList.addFirst(101); doubleLinkList.displayList(); //打印链表结构 doubleLinkList.delete(44); //删除某个节点 doubleLinkList.displayList(); doubleLinkList.deleteLast(); //删除尾节点 doubleLinkList.displayList(); doubleLinkList.deleteFirst(); //删除头结点 doubleLinkList.displayList(); System.out.println(doubleLinkList.find(66)); //查询某个节点} 输出结果：[101-->44-->22-->66-->88][101-->22-->66-->88][101-->22-->66][22-->66]66
链表的效率：
表头插入和删除的速度很快，时间复杂度O(1)
平均下来，定点插入、删除、查询都需要搜索链表中一半的节点，需要O(N)次比较，相比而言，数组执行这些操作也需要O(N)次比较，但是
链表不需要移动数据，只需要改变前后引用，而数组只能整体复制，效率会好很多
链表的另一个优点体现在内存使用上，需要多少内存就使用多少内存，而数组一开始的内存空间都是确定的
有序链表：
对于某些应用来说，在链表中保持数据的有序很很有用的。有序链表中，数据都是按照关键值有序排列的。
在大多数使用有序数组的场景也可以使用有序链表，在插入速度方面有很大优势
有序链表和一般单向链表只是添加方法有区别，其余方法都是相同的
代码示例：
public class SortedLinkList { private int size; //链表长度大小 private Node head; //头结点 public SortedLinkList() { size = 0; head = null; } //添加元素 public void add(int data) { Node newNode = new Node(data); Node previoue = null; Node current = head; while (current != null && data > current.data) { previoue = current; current = current.next; } if (previoue == null) { head = newNode; head.next = current; } else { previoue.next = newNode; newNode.next = current; } size++; } //删除头结点 public int deleteFirst() { final int data = head.data; head = head.next; size--; return data; } //查询某个元素是否存在 public int find(int object) { Node current = head; int tempSize = size; while (tempSize > 0) { if (object == current.data) { return current.data; } else { current = current.next; } tempSize--; } return -1; } //删除链表中某个元素 public boolean delete(int object) { Node current = head; Node previous = head; while (object != current.data) { if (current.next == null) { return false; } else { previous = current; current = current.next; } } if (current == head) { head = current.next; } else { previous.next = current.next; } size--; return true; } //遍历打印链表 public void displayList() { Node current = head; int tempSize = size; if (tempSize == 0) { System.out.print("[]"); } else { System.out.print("["); while (current != null) { if (current.next == null) { System.out.print(current.data);; } else { System.out.print(current.data + "-->");; } current = current.next; } System.out.println("]"); } } public boolean isEmpty() { return size == 0; } private static class Node{ int data; Node next; Node(int data) { this.data = data; } }} public static void main(String[] args) { SortedLinkList sortedLinkList = new SortedLinkList(); sortedLinkList.add(5); //添加节点 sortedLinkList.add(1); sortedLinkList.add(8); sortedLinkList.add(2); sortedLinkList.add(101); sortedLinkList.displayList(); //打印链表结构 sortedLinkList.delete(8); //删除某个节点 sortedLinkList.displayList(); sortedLinkList.deleteFirst(); //删除头结点 sortedLinkList.displayList(); System.out.println(sortedLinkList.find(101)); //查询某个节点} 输出结果：[1-->2-->5-->8-->101][1-->2-->5-->101][2-->5-->101]101
双向链表：
双向链表就是为了解决单向链表只能单向遍历而效率慢的问题，因为只能current=current.next进行遍历，只能获得下一个节点，而不能
获取上一个节点
在学习LinkedList源码的时候，我们已经详细了解过双向链表了，
图例：
代码示例：
public class DoubleLinkedList{ private int size; //链表长度大小 private Node head; //头结点 private Node tail; //尾结点 public DoubleLinkedList() { size = 0; head = null; tail = null; } //添加元素到head public void addFirst(E data) { Node newNode = new Node(data); if (size == 0) { tail = newNode; } else { head.previous = newNode; newNode.next = head; } head = newNode; size++; } //添加元素到tail public void addLast(E data) { Node newNode = new Node(data); if (size == 0) { head = newNode; } else { tail.next = newNode; newNode.previous = tail; } tail = newNode; size++; } //删除头结点 public E deleteFirst() { if (isEmpty()) { return null; } final E data = (E)head.data; if (head.next == null) { tail = null; } head = head.next; head.previous = null; size--; return data; } //删除尾结点 public E deleteLast() { if (isEmpty()) { return null; } final E data = (E)tail.data; if (head.next == null) { head = null; } tail = tail.previous; tail.next = null; size--; return data; } //查询某个元素是否存在 /*public E find(E object) { if (object == null) { for (Node x = head; x != null; x = x.next) { if (x.data == null) { return x.data; } } } else { for (Node x = head; x != null; x = x.next) { if (object.equals(x.data)) { return x.data; } } } return null; }*/ //查询某个索引下标的数据 public E find(int index) { return (E)node(index).data; } //删除链表中某个元素 public boolean delete(E object) { if (object == null) { for (Node x = head; x != null; x = x.next) { if (x.data == null) { unlink(x); return true; } } } else { for (Node x = head; x != null; x = x.next) { if (object.equals(x.data)) { unlink(x); return true; } } } return false; } E unlink(Node x) { final E element = x.data; final Node next = x.next; final Node prev = x.previous; if (prev == null) { head = next; } else { prev.next = next; x.previous = null; } if (next == null) { tail = prev; } else { next.previous = prev; x.next = null; } x.data = null; size--; return element; } Node node(int index) { if (index < (size >> 1)) { Node x = head; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = tail; for (int i = size - 1; i > index; i--) x = x.previous; return x; } } //遍历打印链表 public void displayList() { Node current = head; int tempSize = size; if (tempSize == 0) { System.out.print("[]"); } else { System.out.print("["); while (current != null) { if (current == tail) { System.out.print(current.data); break; } else { System.out.print(current.data + "-->"); } current = current.next; } System.out.println("]"); } } public boolean isEmpty() { return size == 0; } private static class Node { E data; Node previous; Node next; Node(E data) { this.data = data; } }}
public static void main(String[] args) { DoubleLinkedList doubleLinkList = new DoubleLinkedList (); doubleLinkList.addFirst(22); //添加节点 doubleLinkList.addFirst(44); doubleLinkList.addLast(66); doubleLinkList.addLast(88); doubleLinkList.addFirst(101); doubleLinkList.displayList(); //打印链表结构 doubleLinkList.delete(44); //删除某个节点 doubleLinkList.displayList(); doubleLinkList.deleteLast(); //删除尾节点 doubleLinkList.displayList(); doubleLinkList.deleteFirst(); //删除头结点 doubleLinkList.displayList(); System.out.println(doubleLinkList.find(66)); //查询某个节点 System.out.println(doubleLinkList.find(33)); //查询某个节点} 输出结果：[101-->44-->22-->66-->88][101-->22-->66-->88][101-->22-->66][22-->66]66
拓展1、用链表实现：
public class MyStackByLinkedList{ private SingleLinkList linkList; public MyStackByLinkedList() { linkList = new SingleLinkList(); } public void push(E e) { linkList.addFirst(e); } public E pop(){ E e = (E)linkList.deleteFirst(); return e; }}
拓展2：用双端链表实现队列
public class MyQueueByLinkedList{ private DoubleLinkedList linkedList; public MyQueueByLinkedList() { linkedList = new DoubleLinkedList(); } public void add(E e) { linkedList.addFirst(e); } //移除数据 public E remove(){ return (E)linkedList.deleteFirst(); }}
内容参考：<Java数据结构和算法>