链表（linked list）是一种物理上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
单向链表的每一个节点包含两部分，一部分是存放数据变量data，另一部分是指向下一个节点的next指针
单向链表
1. private static class Node{
2. int data;
3. Node next;
4. Node(int data){
5. this.data = data;
6. }
7. } 双向链表，它的每一个节点除了拥有data变量和next指针外，还有指向前置节点的prev指针
双向链表
链表的基本操作（CURD）
1.插入节点分为3种情况：
- 1.1 头部插入
头部插入，分为2个步骤：
(1) 把新节点的next指针指向之前的头节点；
(2) 把新节点变为链表的头节点。
- 1.2 中间插入
中间插入，分为2个步骤：
(1) 新节点的next指针，指向插入位置的节点；
(2) 插入位置的前置节点的next指针，指向新节点。
- 1.3 尾部插入
尾部插入最简单，把最后一个节点的next指针指向新插入的节点即可。
2.删除节点分为3种情况：
- 2.1 头部删除
把链表的头节点设为原先头节点的next指针。
- 2.2 中间删除
把要删除的节点的前置节点的next指针，指向要删除元素的下一个节点。
- 2.3 尾部删除
把倒数第2个节点的next指针指向null即可。
1. public class MyLinkedList {
2. //头结点
3. private Node head;
4. //尾结点
5. private Node last;
6. //链表实际长度
7. private int size;
8.
9. public void insert(int index,int data) throws Exception{
10. if(index < 0 || index > size){
11. throw new IndexOutOfBoundsException("索引超出链表实际范围！");
12. }
13.
14. Node nodeNew = new Node(data);
15. if(size == 0){
16. //空链表
17. head = nodeNew;
18. last = nodeNew;
19. }else if(index == 0){
20. //头部插入
21. nodeNew.next = head;
22. head = nodeNew;
23. }else if(size == index){
24. //尾部插入
25. last.next = nodeNew;
26. last = nodeNew;
27. }else{
28. //中间插入
29. Node prevNode = get(index - 1);
30. nodeNew.next = prevNode.next;
31. prevNode.next = nodeNew;
32. }
33. size++;
34. }
public Node remove(int index)throws Exception{
38. if(index < 0 || index > size){
39. throw new IndexOutOfBoundsException("索引超出链表实际范围！");
40. }
41. Node removeNode;
42. if(index == 0){
43. //删除头部节点
44. removeNode = head;
45. head = head.next;
46. }else if(index == size -1){
47. //删除尾部节点
48. removeNode = last;
49. Node prevNode = get(index - 1);
50. prevNode.next = null;
51. last = prevNode;
52. }else{
53. //删除中间节点
54. Node prevNode = get(index - 1);
55. removeNode = prevNode.next;
56. prevNode.next = prevNode.next.next;
57. }
58. size--;
59. return removeNode;
60. }
61.
62. public void print(){
63. Node temp = head;
64. while (temp != null){
65. System.out.println(temp.data);
66. temp = temp.next;
67. }
68. }
69. private Node get(int index) throws Exception{
70. if(index < 0 || index > size){
71. throw new IndexOutOfBoundsException("索引超出链表实际范围！");
72. }
73. Node temp = head;
74. for(int i = 0; i < index;i++){
75. temp = temp.next;
76. }
77. return temp;
78. }
37. public Node remove(int index)throws Exception{
38. if(index < 0 || index > size){
39. throw new IndexOutOfBoundsException("索引超出链表实际范围！");
40. }
41. Node removeNode;
42. if(index == 0){
43. //删除头部节点
44. removeNode = head;
45. head = head.next;
46. }else if(index == size -1){
47. //删除尾部节点
48. removeNode = last;
49. Node prevNode = get(index - 1);
50. prevNode.next = null;
51. last = prevNode;
52. }else{
53. //删除中间节点
54. Node prevNode = get(index - 1);
55. removeNode = prevNode.next;
56. prevNode.next = prevNode.next.next;
57. }
58. size--;
59. return removeNode;
60. }
61.
62. public void print(){
63. Node temp = head;
64. while (temp != null){
65. System.out.println(temp.data);
66. temp = temp.next;
67. }
68. }
69. private Node get(int index) throws Exception{
70. if(index < 0 || index > size){
71. throw new IndexOutOfBoundsException("索引超出链表实际范围！");
72. }
73. Node temp = head;
74. for(int i = 0; i < index;i++){
75. temp = temp.next;
76. }
77. return temp;
78. }
80. private static class Node{
81. int data;
82. Node next;
83. Node(int data){
84. this.data = data;
85. }
86. }
87. } Java中的LinkedList实现（基于Java8）
LinkedList内部实现是双向链表。节点包括实际的元素item，但同时有两个链接，分别指向前一个节点（前驱）和后一个节点（后继）。对比以上我们自己实现的单向链表，只是多了一个前驱节点prev，内部实现类为：
1. private static class Node<E> {
2. E item;
3. Node<E> next;
4. Node<E> prev;
5. Node(Node<E> prev, E element, Node<E> next) {
6. this.item = element;
7. this.next = next;
8. this.prev = prev;
9. }
10. } - add方法
1. public void add(int index, E element) {
2. //校验是否超过索引范围
3. checkPositionIndex(index);
4. if (index == size)
5. //尾部插入
6. linkLast(element);
7. else
8. linkBefore(element, node(index));
9. }
10. //尾部插入
11. void linkLast(E e) {
12. final Node<E> l = last;
13. final Node<E> newNode = new Node<>(l, e, null);
14. last = newNode;
15. if (l == null)
16. first = newNode;
17. else
18. l.next = newNode;
19. size++;
20. modCount++;
21. }
1. //头部插入
2. private void linkFirst(E e) {
3. final Node<E> f = first;
4. final Node<E> newNode = new Node<>(null, e, f);
5. first = newNode;
6. if (f == null)
7. last = newNode;
8. else
9. f.prev = newNode;
10. size++;
11. modCount++;
12. }
13. //中间插入
14. void linkBefore(E e, Node<E> succ) {
15. // assert succ != null;
16. final Node<E> pred = succ.prev;
17. final Node<E> newNode = new Node<>(pred, e, succ);
18. succ.prev = newNode;
19. if (pred == null)
20. first = newNode;
21. else
22. pred.next = newNode;
23. size++;
24. modCount++;
25. }
26. //根据索引查询节点
27. Node<E> node(int index) {
28. //size>>1=size/2，如果索引位置在前半部分（index<(size>>1)），
29. //则从头节点开始查找，否则，从尾节点开始查找。
30. if (index < (size >> 1)) {
31. Node<E> x = first;
32. for (int i = 0; i < index; i++)
33. x = x.next;
34. return x;
35. } else {
36. Node<E> x = last;
37. for (int i = size - 1; i > index; i--)
38. x = x.prev;
39. return x;
40. }
41. } - remove删除方法
1. public E remove(int index) {
2. checkElementIndex(index);
3. return unlink(node(index));
4. }
5. E unlink(Node<E> x) {
6. final E element = x.item;
7. final Node<E> next = x.next;
8. final Node<E> prev = x.prev;
9.
10. if (prev == null) {
11. first = next;
12. } else {
13. prev.next = next;
14. x.prev = null;
15. }
16.
17. if (next == null) {
18. last = prev;
19. } else {
20. next.prev = prev;
21. x.next = null;
22. }
23.
24. x.item = null;
25. size--;
26. modCount++;
27. return element;
28. } LinkedList除了实现了List接口外，还实现了Deque和Queue接口，可以按照队列、栈和双端队列的方式进行操作。
Queue接口
Queue队列接口，先进先出，在尾部添加元素，从头部删除元素，接口定义为：
1. public interface Queue<E> extends Collection<E> {
2. boolean add(E e);
3. boolean offer(E e);
4. E remove();
5. E poll();
6. E element();
7. E peek();
8. } Queue扩展了Collection，主要操作有3个：
(1) 在尾部添加元素（add、offer）；
(2) 查看头部元素（element、peek），返回头部元素，但不改变队列；
(3) 删除头部元素（remove、poll），返回头部元素，并且从队列中删除。
每种操作都有2种形式，区别在于，对于特殊情况的处理不同。特殊情况是队列为空或者队列满的时候。满是指队列有长度限制，而且已经占满了。LinkedList的实现中，队列长度没有限制，但别的Queue实现可能会有。
(1) 队列为空时，element和remove会抛出异常NoSuchElementException，而peek
和poll返回null；
(2) 在队列为满时，add会抛出异常IllegalStateException，而offer只是返回false。
如下图所示：顺序入栈a，b，c，输出结果a，b，c，先进先出
Deque接口
Java中没有单独的栈接口，栈是先进后出，栈相关的方法包含在表示双端队列的Deque接口中：
1. void push(E e);
2. E pop();
3. E peek(); (1) push表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException。
(2) pop表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常NoSuch-ElementException。
(3) peek查看栈头部元素，不修改栈，如果栈为空，返回null。
如下图所示：顺序入栈a，b，c，输出结果c，b，a，先进后出
栈和队列都是在两端进行操作，栈只操作头部，队列两端都操作，但尾部只添加、头部只查看和删除。Deque扩展了Queue，包括了栈的操作方法，此外，它还有如下更为明确的操作两端的方法(已删除继承自Queue接口的方法)：
1. public interface Deque<E> extends Queue<E> {
2. void addFirst(E e);
3. void addLast(E e);
4. boolean offerFirst(E e);
5. boolean offerLast(E e);
6. E removeFirst();
7. E removeLast();
8. E pollFirst();
9. E pollLast();
10. E getFirst();
11. E getLast();
12. E peekFirst();
13. E peekLast();
14. boolean removeFirstOccurrence(Object o);
15. boolean removeLastOccurrence(Object o);
16. } xxxFirst()操作头部，xxxLast()操作尾部。与队列类似，每种操作都有2种形式，区别在于队列为空或者满时处理不同。为空时，getXxx()/removeXxx()会抛出异常，而peekXxx()/pollXxx()会返回null。队列满时，addXxx()会抛出异常，offerXxx()只是返回false。
用法上，LinkedList是一个List，但也实现了Deque接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList内部是一个双向链表，并维护了长度、头节点和尾节点，它有如下特点。
(1) 按需分配空间，不需要预先分配很多空间。
(2) 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
(3) 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)。
(4) 在两端添加、删除元素的效率很高，为O(1)。
(5) 在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)。
Stack类
Java中一个类Stack，它也实现了栈的一些方法，eg：push/pop/peek等，但它没有实现Deque接口，它是Vector的子类，它增加的这些方法是通过synchronized实现了线程安全。
1. public class Stack<E> extends Vector<E> {
2.
3. public Stack() {}
4.
5. public E push(E item) {}
6.
7. public synchronized E pop() {}
8.
9. public synchronized E peek() {}
10.
11. public boolean empty() {}
12.
13. public synchronized int search(Object o) {}
14.
15. private static final long serialVersionUID = 1224463164541339165L;
16. }