日常开发中，数组和集合使用的很多，而数组的无序插入和删除效率都是偏低的，这点在学习ArrayList源码的时候就知道了，因为需要把要
插入索引后面的所以元素全部后移一位。
而本文会详细讲解链表，可以解决数组的部分问题，相比数组的大小不可更改，链表更加灵活，在学习LinkedList源码对链表有了一个大致的
了解。
ArrayList和LinkedList源码请参考：
Java集合(四)--基于JDK1.8的ArrayList源码解读
本文我们会学习：单链表、双端链表、有序链表、双向链表和有迭代器的链表，并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述
栈和队列，如何用链表代替数组来实现栈和队列。
链节点：
在链表中，每个元素都被包含在链节点Link中。一个链节点是某个类的对象，这个类可以叫做Link。每个Link对象都包含对下一个Link引用的
字段（通常叫next）。但是链表本身有个字段指向对第一个Link的引用。
代码示例：
1public class Link { 2 private Object data; 3 private Link next; 4}
单链表：
单链表的机构比较简单，每个Node包含data和next(指向下个Node)，最后一个Node的next指向null
图例：
代码实现：
1public class SingleLinkList<E> { 2 private int size; //链表长度大小 3 private Node head; //头结点 4 5 public SingleLinkList() { 6 size = 0; 7 head = null; 8 } 9 10 //添加元素到head 11 public void addFirst(E data) { 12 Node newNode = new Node(data); 13 if (size == 0) { 14 head = newNode; 15 } else { 16 newNode.next = head; 17 head = newNode; 18 } 19 size++; 20 } 21 22 //删除头结点 23 public E deleteFirst() { 24 final E data = (E)head.data; 25 head = head.next; 26 size--; 27 return data; 28 } 29 30 //查询某个元素是否存在 31 public E find(E object) { 32 Node current = head; 33 int tempSize = size; 34 while (tempSize > 0) { 35 if (object == current.data) { 36 return (E)current.data; 37 } else { 38 current = current.next; 39 } 40 tempSize--; 41 } 42 return null; 43 } 44 45 //删除链表中某个元素 46 public boolean delete(E object) { 47 if (null != object) { 48 Node current = head; 49 Node previous = head; 50 while (!object.equals(current.data)) { 51 if (current.next == null) { 52 return false; 53 } else { 54 previous = current; 55 current = current.next; 56 } 57 } 58 if (current == head) { 59 head = current.next; 60 } else { 61 previous.next = current.next; 62 } 63 size--; 64 } 65 return true; 66 67 } 68 69 //遍历打印链表 70 public void displayList() { 71 Node current = head; 72 int tempSize = size; 73 if (tempSize == 0) { 74 System.out.print("[]"); 75 } else { 76 System.out.print("["); 77 while (current != null) { 78 if (current.next == null) { 79 System.out.print(current.data);; 80 } else { 81 System.out.print(current.data + "-->");; 82 } 83 current = current.next; 84 } 85 System.out.println("]"); 86 } 87 } 88 89 public boolean isEmpty() { 90 return size == 0; 91 } 92 93 private static class Node<E>{ 94 E data; 95 Node<E> next; 96 Node(E data) { 97 this.data = data; 98 } 99 } 100} 101 102public static void main(String[] args) { SingleLinkList<Integer> singleList = new SingleLinkList<Integer>(); 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)); //查询某个节点} 103 104打印结果： 105[88-->66-->44-->22] 106[88-->66-->22] 10766
双端链表：
双端链表和单向链表很相似，但是增加了一个新特性：就是对最后一个节点的引用，最后一个节点定义为tail
PS：双端链表不是双向链表，只能单向遍历，只是可以在双端添加/删除数据
图例：
代码实现：
1public class DoubleLinkList<E> { 2 private int size; //链表长度大小 3 private Node head; //头结点 4 private Node tail; //尾结点 5 6 public DoubleLinkList() { 7 size = 0; 8 head = null; 9 tail = null; 10 } 11 12 //添加元素到head 13 public void addFirst(E data) { 14 Node newNode = new Node(data); 15 if (size == 0) { 16 head = newNode; 17 tail = newNode; 18 } else { 19 newNode.next = head; 20 head = newNode; 21 } 22 size++; 23 } 24 25 //添加元素到tail 26 public void addLast(E data) { 27 Node newNode = new Node(data); 28 if (size == 0) { 29 head = newNode; 30 tail = newNode; 31 } else { 32 tail.next = newNode; 33 tail = newNode; 34 } 35 size++; 36 } 37 38 //删除头结点 39 public E deleteFirst() { 40 if (isEmpty()) { 41 return null; 42 } 43 final E data = (E)head.data; 44 if (head.next == null) { 45 tail = null; 46 } 47 head = head.next; 48 size--; 49 return data; 50 } 51 52 //删除尾结点 53 public E deleteLast() { 54 if (isEmpty()) { 55 return null; 56 } 57 final E data = (E)tail.data; 58 if (head.next == null) { 59 head = null; 60 } 61 int tempSize = size; 62 Node current = head; 63 Node previous = head; 64 while (tempSize > 0) { 65 if (current.next == null) { 66 previous.next = null; 67 break; 68 } 69 previous = current; 70 current = current.next; 71 tempSize--; 72 } 73 tail = previous; 74 size--; 75 return data; 76 } 77 78 //查询某个元素是否存在 79 public E find(E object) { 80 Node current = head; 81 int tempSize = size; 82 while (tempSize > 0) { 83 if (object == current.data) { 84 return (E)current.data; 85 } else { 86 current = current.next; 87 } 88 tempSize--; 89 } 90 return null; 91 } 92 93 //删除链表中某个元素 94 public boolean delete(E object) { 95 if (null != object) { 96 Node current = head; 97 Node previous = head; 98 while (!object.equals(current.data)) { 99 if (current.next == null) { 100 return false; 101 } else { 102 previous = current; 103 current = current.next; 104 } 105 } 106 if (current == head) { 107 head = current.next; 108 }else { 109 previous.next = current.next; 110 } 111 size--; 112 } 113 return true; 114 115 } 116 117 //遍历打印链表 118 public void displayList() { 119 Node current = head; 120 int tempSize = size; 121 if (tempSize == 0) { 122 System.out.print("[]"); 123 } else { 124 System.out.print("["); 125 while (current != null) { 126 if (current == tail) { 127 System.out.print(current.data); 128 break; 129 } else { 130 System.out.print(current.data + "-->"); 131 } 132 current = current.next; 133 } 134 System.out.println("]"); 135 } 136 } 137 138 public boolean isEmpty() { 139 return size == 0; 140 } 141 142 private static class Node<E>{ 143 E data; 144 Node<E> next; 145 Node(E data) { 146 this.data = data; 147 } 148 } 149} 150 151public static void main(String[] args) { 152 DoubleLinkList<Integer> doubleLinkList = new DoubleLinkList<Integer>(); 153 doubleLinkList.addFirst(22); //添加节点 154 doubleLinkList.addFirst(44); 155 doubleLinkList.addLast(66); 156 doubleLinkList.addLast(88); 157 doubleLinkList.addFirst(101); 158 doubleLinkList.displayList(); //打印链表结构 159 doubleLinkList.delete(44); //删除某个节点 160 doubleLinkList.displayList(); 161 doubleLinkList.deleteLast(); //删除尾节点 162 doubleLinkList.displayList(); 163 doubleLinkList.deleteFirst(); //删除头结点 164 doubleLinkList.displayList(); 165 System.out.println(doubleLinkList.find(66)); //查询某个节点 166} 167 168输出结果： 169[101-->44-->22-->66-->88] 170[101-->22-->66-->88] 171[101-->22-->66] 172[22-->66] 17366
链表的效率：
表头插入和删除的速度很快，时间复杂度O(1)
平均下来，定点插入、删除、查询都需要搜索链表中一半的节点，需要O(N)次比较，相比而言，数组执行这些操作也需要O(N)次比较，但是
链表不需要移动数据，只需要改变前后引用，而数组只能整体复制，效率会好很多
链表的另一个优点体现在内存使用上，需要多少内存就使用多少内存，而数组一开始的内存空间都是确定的
有序链表：
对于某些应用来说，在链表中保持数据的有序很很有用的。有序链表中，数据都是按照关键值有序排列的。
在大多数使用有序数组的场景也可以使用有序链表，在插入速度方面有很大优势
有序链表和一般单向链表只是添加方法有区别，其余方法都是相同的
代码示例：
1public class SortedLinkList { 2 private int size; //链表长度大小 3 private Node head; //头结点 4 5 public SortedLinkList() { 6 size = 0; 7 head = null; 8 } 9 10 //添加元素 11 public void add(int data) { 12 Node newNode = new Node(data); 13 Node previoue = null; 14 Node current = head; 15 while (current != null && data > current.data) { 16 previoue = current; 17 current = current.next; 18 } 19 if (previoue == null) { 20 head = newNode; 21 head.next = current; 22 } else { 23 previoue.next = newNode; 24 newNode.next = current; 25 } 26 size++; 27 } 28 29 //删除头结点 30 public int deleteFirst() { 31 final int data = head.data; 32 head = head.next; 33 size--; 34 return data; 35 } 36 37 //查询某个元素是否存在 38 public int find(int object) { 39 Node current = head; 40 int tempSize = size; 41 while (tempSize > 0) { 42 if (object == current.data) { 43 return current.data; 44 } else { 45 current = current.next; 46 } 47 tempSize--; 48 } 49 return -1; 50 } 51 52 //删除链表中某个元素 53 public boolean delete(int object) { 54 Node current = head; 55 Node previous = head; 56 while (object != current.data) { 57 if (current.next == null) { 58 return false; 59 } else { 60 previous = current; 61 current = current.next; 62 } 63 } 64 if (current == head) { 65 head = current.next; 66 } else { 67 previous.next = current.next; 68 } 69 size--; 70 return true; 71 72 } 73 74 //遍历打印链表 75 public void displayList() { 76 Node current = head; 77 int tempSize = size; 78 if (tempSize == 0) { 79 System.out.print("[]"); 80 } else { 81 System.out.print("["); 82 while (current != null) { 83 if (current.next == null) { 84 System.out.print(current.data);; 85 } else { 86 System.out.print(current.data + "-->");; 87 } 88 current = current.next; 89 } 90 System.out.println("]"); 91 } 92 } 93 94 public boolean isEmpty() { 95 return size == 0; 96 } 97 98 private static class Node{ 99 int data; 100 Node next; 101 Node(int data) { 102 this.data = data; 103 } 104 } 105} 106 107public static void main(String[] args) { 108 SortedLinkList sortedLinkList = new SortedLinkList(); 109 sortedLinkList.add(5); //添加节点 110 sortedLinkList.add(1); 111 sortedLinkList.add(8); 112 sortedLinkList.add(2); 113 sortedLinkList.add(101); 114 sortedLinkList.displayList(); //打印链表结构 115 sortedLinkList.delete(8); //删除某个节点 116 sortedLinkList.displayList(); 117 sortedLinkList.deleteFirst(); //删除头结点 118 sortedLinkList.displayList(); 119 System.out.println(sortedLinkList.find(101)); //查询某个节点 120} 121 122输出结果： 123[1-->2-->5-->8-->101] 124[1-->2-->5-->101] 125[2-->5-->101] 126101
双向链表：
双向链表就是为了解决单向链表只能单向遍历而效率慢的问题，因为只能current=current.next进行遍历，只能获得下一个节点，而不能
获取上一个节点
在学习LinkedList源码的时候，我们已经详细了解过双向链表了，Java集合(五)--LinkedList源码解读
图例：
代码示例：
1public class DoubleLinkedList<E> { 2 private int size; //链表长度大小 3 private Node head; //头结点 4 private Node tail; //尾结点 5 6 public DoubleLinkedList() { 7 size = 0; 8 head = null; 9 tail = null; 10 } 11 12 //添加元素到head 13 public void addFirst(E data) { 14 Node newNode = new Node(data); 15 if (size == 0) { 16 tail = newNode; 17 } else { 18 head.previous = newNode; 19 newNode.next = head; 20 } 21 head = newNode; 22 size++; 23 } 24 25 //添加元素到tail 26 public void addLast(E data) { 27 Node newNode = new Node(data); 28 if (size == 0) { 29 head = newNode; 30 } else { 31 tail.next = newNode; 32 newNode.previous = tail; 33 } 34 tail = newNode; 35 size++; 36 } 37 38 //删除头结点 39 public E deleteFirst() { 40 if (isEmpty()) { 41 return null; 42 } 43 final E data = (E)head.data; 44 if (head.next == null) { 45 tail = null; 46 } 47 head = head.next; 48 head.previous = null; 49 size--; 50 return data; 51 } 52 53 //删除尾结点 54 public E deleteLast() { 55 if (isEmpty()) { 56 return null; 57 } 58 final E data = (E)tail.data; 59 if (head.next == null) { 60 head = null; 61 } 62 tail = tail.previous; 63 tail.next = null; 64 size--; 65 return data; 66 } 67 68 //查询某个元素是否存在 69 /*public E find(E object) { 70 if (object == null) { 71 for (Node<E> x = head; x != null; x = x.next) { 72 if (x.data == null) { 73 return x.data; 74 } 75 } 76 } else { 77 for (Node<E> x = head; x != null; x = x.next) { 78 if (object.equals(x.data)) { 79 return x.data; 80 } 81 } 82 } 83 return null; 84 }*/ 85 86 //查询某个索引下标的数据 87 public E find(int index) { 88 return (E)node(index).data; 89 } 90 91 //删除链表中某个元素 92 public boolean delete(E object) { 93 if (object == null) { 94 for (Node<E> x = head; x != null; x = x.next) { 95 if (x.data == null) { 96 unlink(x); 97 return true; 98 } 99 } 100 } else { 101 for (Node<E> x = head; x != null; x = x.next) { 102 if (object.equals(x.data)) { 103 unlink(x); 104 return true; 105 } 106 } 107 } 108 return false; 109 110 } 111 112 E unlink(Node<E> x) { 113 final E element = x.data; 114 final Node<E> next = x.next; 115 final Node<E> prev = x.previous; 116 117 if (prev == null) { 118 head = next; 119 } else { 120 prev.next = next; 121 x.previous = null; 122 } 123 124 if (next == null) { 125 tail = prev; 126 } else { 127 next.previous = prev; 128 x.next = null; 129 } 130 131 x.data = null; 132 size--; 133 return element; 134 } 135 136 Node node(int index) { 137 if (index < (size >> 1)) { 138 Node x = head; 139 for (int i = 0; i < index; i++) 140 x = x.next; 141 return x; 142 } else { 143 Node<E> x = tail; 144 for (int i = size - 1; i > index; i--) 145 x = x.previous; 146 return x; 147 } 148 } 149 150 //遍历打印链表 151 public void displayList() { 152 Node current = head; 153 int tempSize = size; 154 if (tempSize == 0) { 155 System.out.print("[]"); 156 } else { 157 System.out.print("["); 158 while (current != null) { 159 if (current == tail) { 160 System.out.print(current.data); 161 break; 162 } else { 163 System.out.print(current.data + "-->"); 164 } 165 current = current.next; 166 } 167 System.out.println("]"); 168 } 169 } 170 171 public boolean isEmpty() { 172 return size == 0; 173 } 174 175 private static class Node<E>{ 176 E data; 177 Node<E> previous; 178 Node<E> next; 179 Node(E data) { 180 this.data = data; 181 } 182 } 183} 184 185public static void main(String[] args) { 186 DoubleLinkedList<Integer> doubleLinkList = new DoubleLinkedList<Integer>(); 187 doubleLinkList.addFirst(22); //添加节点 188 doubleLinkList.addFirst(44); 189 doubleLinkList.addLast(66); 190 doubleLinkList.addLast(88); 191 doubleLinkList.addFirst(101); 192 doubleLinkList.displayList(); //打印链表结构 193 doubleLinkList.delete(44); //删除某个节点 194 doubleLinkList.displayList(); 195 doubleLinkList.deleteLast(); //删除尾节点 196 doubleLinkList.displayList(); 197 doubleLinkList.deleteFirst(); //删除头结点 198 doubleLinkList.displayList(); 199 System.out.println(doubleLinkList.find(66)); //查询某个节点 200 System.out.println(doubleLinkList.find(33)); //查询某个节点 201} 202 203输出结果： 204[101-->44-->22-->66-->88] 205[101-->22-->66-->88] 206[101-->22-->66] 207[22-->66] 20866
拓展1、用链表实现：
1public class MyStackByLinkedList<E> { 2 private SingleLinkList linkList; 3 4 public MyStackByLinkedList() { 5 linkList = new SingleLinkList(); 6 } 7 8 public void push(E e) { 9 linkList.addFirst(e); 10 } 11 12 public E pop(){ 13 E e = (E)linkList.deleteFirst(); 14 return e; 15 } 16 17}
拓展2：用双端链表实现队列
1public class MyQueueByLinkedList<E> { 2 private DoubleLinkedList linkedList; 3 4 public MyQueueByLinkedList() { 5 linkedList = new DoubleLinkedList(); 6 } 7 8 public void add(E e) { 9 linkedList.addFirst(e); 10 } 11 12 //移除数据 13 public E remove(){ 14 return (E)linkedList.deleteFirst(); 15 } 16 17}
内容参考：<Java数据结构和算法>