数据结构之链表
1、线性数据结构，动态数组、栈、队列，底层依托静态数组，靠resize解决固定容量问题。
2、为什么链表很重要？
1）、最基础的动态数据结构，链表。真正得动态数据结构，最简单的一种动态数据结构。更为复杂的有二分搜索树、平衡二叉树、红黑树等等。
2）、链表设计到一个，更深入的理解引用（或者在C++中称为指针）。
3）、链表帮助更深入的理解递归。链表本身有非常清晰的递归结构的，只不过链表本身是一种线性的数据结构，所以可以非常容易的使用循环的方式来对链表进行操作的，但是链表天生是有递归结构性质的，链表可以很好的帮助理解递归机制的数据结构。
3、什么是链表？
将数据存储到一种单独的结构中，这种单独的结构通常被称为节点Node。链表的节点通常有两部分组成，一部分是存储真正的数据E e，另一部分是Node next，next是Node类型的变量，next本身又是一个节点，next这个变量的名称可以看出，它指的是当前这一个节点指向下一个节点。类比火车，每一个节点就是一个车厢，车厢是存储真正的数据，车厢与车厢之间进行连接，以使得数据整合到一起，方便用户进行查询，增加，修改等等操作，数据与数据之间的连接是由next完成的。
4、链表的基本知识，如下所示：
1）、有一个头节点，首先要有一个元素存储的是1，也就是要存放的数据，同时，也要有一个指向下一个节点的next，next是Node类型的引用。1 -> 2）、如果第一个节点指向下一个节点存储的元素是2，对于元素2来说，它有一个next指向下一个节点。1 -> 2 -> 3）、如果第二个节点指向下一个节点存储的元素是3，对于元素3来说，它有一个next指向下一个节点。1 -> 2 -> 3 -> NULL 4）、链表的最后一个节点存储的就是NULL，就是一个空，如果一个节点的next是空的，就说明这个节点是最后一个节点。 5）、链表的优点，是真正的动态，不需要处理固定容量的问题。静态数组需要一下子创建很多空间，同时还需要考虑空间是不是够用或者空间是不是开多了，造成浪费的问题。对于链表来说，需要存储多少数据，就可以生成多少个节点，将他们挂接起来，这就是所谓的动态的意思。 6）、链表的缺点，丧失了随机访问的能力。相比数组，数组可以进行随机访问，给一个索引，数组就可以进行访问，从底层机制上，数组所开辟的空间在内存里面是连续分布的，可以直接寻找这个索引对应的偏移，直接计算出相应的数据所存储的内存地址，直接用O(1)的复杂度就将数据拿出来。但是链表是靠next一层一层连接的，所以在计算机的底层每一个节点所在的内存位置都是不同的，必须靠next一点一点来找到我们要找的元素，这就是链表最大的缺点。 7）、数组最好用于索引有语意的情况，最大的优点是支持快速查询。链表不适合用于索引有语意的情况，最大的优点是动态。
5、链表的封装。
1）、链表是通过节点装载元素，并且节点和节点之间连接起来的一种数据结构。对于链表来说，我们要想访问存在这个链表中的所有节点，相应的，我们必须把链表的头给存储起来。通常链表的头叫做head，所以在链表中应该有一个Node类型的变量head，它指向链表中的第一个节点。
2）、为数组添加元素，开始的思路是在数组的尾部添加元素，对于数组这种结构，在数组尾部添加一个元素是十分方便的，因为对于数组来说，size变量直接指向数组的最后一个元素的下一个位置，也就是下一个待添加元素的位置，所以直接添加就非常容易，size变量在跟踪数组的尾巴。对于链表来说，在链表头部添加元素是十分方便的，对于链表来说，我们设置一个链表的头，Node类型的head变量，在跟踪链表的头部，所以在链表头部添加元素是十分方便的。
3）、链表的添加，在链表头部添加元素，如果想在链表中添加一个元素，先将元素放入到节点里面，此时该节点存放了该元素，以及Node类型的next。链表添加元素的关键，就是如何将节点挂接到链表中，同时不破坏该链表的结构。node.next = head，即让该节点node的next指向next，就将该节点添加到链表中了，然后将head = node，即将链表的头部前移。
执行node.next = head此句话之后，就变成了如下所示的链表结构。此时存放666元素的节点node成为了新的链表头。
此时，将head进行移动，使node得位置变成head，即指向head = node操作。使head指向存放666元素的node节点。
此时，就完成了，将存储666元素的节点，插入到整个链表头部中。
4）、在链表中间添加新的元素，首先创建出新元素的节点node，如何将新的节点插入到正确的位置呢，那么就必须要找到当我们插入新的元素节点之后这个节点之前的那个节点是谁。相应的，之前的那个节点要prev，prev初始化是和head在一个位置的，我们要找到新的元素的节点之前的那个节点应该是谁，我就直接把之前的那个节点的next指向新的元素的节点，新的元素的节点的next指向它之前的那个节点的之后的这个节点，就完成了这个插入操作了。目标是先找到插入新元素的节点之前的那个节点是谁，如果明确了插入位置索引，可以根据明确的插入位置索引减一就找到了插入新元素的节点之前的那个节点是谁，从零开始遍历，找到明确索引减一的位置设置为prev，那么将node.next = prev.next，即将node的下一个节点指向prev的下一个节点，再将prev.next = node，那么就实现了将新元素节点插入到链表结构中了。关键，找到要添加的节点的前一个节点。注意，如果要添加的新元素节点是头部的话，是没有上一个节点位置的，需要进行特殊处理。
我们的任务是要搜索插入元素666的这个node节点之前的那个节点是谁，显然，插入元素666这个node节点的索引为2，那么插入元素666之前的那个节点的索引就是1。我们开始遍历，从索引为0开始遍历，遍历到索引为1的地方就可以了。
一旦找到这里之后，下面的事情就是开始，首先，我们将node.next指向prev.next。
之后，我们再让prev.next指向node，代码是prev.next = node;
经过这两步操作之后，我们就完成了将元素666这个node节点插入到索引为2的地方。
实现代码，如下所示：
1 package com.linkedlist;
2
3 /**
4 * 链表结构的创建，链表是一种线性的数据结构
5 */
6 public class LinkedList<E> {
7
8 // 链表是由一个一个节点组成
9 private class Node {
10 // 设置公有的，可以让外部类进行修改和设置值
11 public E e;// 成员变量e存放元素
12 public Node next;// 成员变量next指向下一个节点，指向Node的一个引用
13
14 /**
15 * 含参构造函数
16 *
17 * @param e
18 * @param next
19 */
20 public Node(E e, Node next) {
21 this.e = e;
22 this.next = next;
23 }
24
25 /**
26 * 无参构造函数
27 */
28 public Node() {
29 this(null, null);
30 }
31
32 /**
33 * 如果用户只传了e，那么可以调用含参构造函数，将next指定为null
34 *
35 * @param e
36 */
37 public Node(E e) {
38 this(e, null);
39 }
40
41 /**
42 * @return
43 */
44 @Override
45 public String toString() {
46 return "Node{" +
47 "e=" + e.toString() +
48 ", next=" + next +
49 '}';
50 }
51 }
52
53
54 private Node head;// Node类型的变量head
55 private int size;// 链表要存储一个一个元素，肯定有大小，记录链表有多少元素
56
57 /**
58 * 无参的构造函数
59 */
60 public LinkedList() {
61 head = null;// 初始化一个链表，head为空，一个元素都没有
62 size = 0;// 大小size为0
63 }
64
65 /**
66 * 获取链表的大小，获取链表中的元素个数
67 *
68 * @return
69 */
70 public int getSize() {
71 return size;
72 }
73
74 /**
75 * 判断返回链表是否为空
76 *
77 * @return
78 */
79 public boolean isEmpty() {
80 return size == 0;
81 }
82
83 /**
84 * 在链表头部添加新的元素e
85 *
86 * @param e
87 */
88 public void addFirst(E e) {
89 // // 创建一个新的节点，然后将元素传入进去即将元素写入到节点上面。
90 // Node node = new Node(e);
91 // // 将新的节点的下一个节点指向head头部节点。
92 // node.next = head;
93 // // 然后将node这个新的节点指向head节点。
94 // head = node;
95
96 // 上面三行代码，可以使用下面一行代码书写。
97 // 首先，创建一个Node节点，将元素e传入第一个参数，将这个元素直接指向链表的head即参数二。
98 // 然后，将这个Node赋值给head头部节点。
99 head = new Node(e, head);
100
101 // 维护size的长度，让size自增
102 size++;
103 }
104
105 /**
106 * 在链表的index(0-based)索引位置添加新的元素e
107 *
108 * @param index
109 * @param e
110 */
111 public void add(int index, E e) {
112 // 如果指定的索引位置不符合要求，抛出异常
113 // 切记，index是可以取到size，在链表的尾部添加一个元素
114 if (index < 0 || index > size) {
115 throw new IllegalArgumentException("Add failed. Illegal index.");
116 }
117
118 // 如果要在链表头部添加元素，特殊处理一下
119 if (index == 0) {
120 this.addFirst(e);
121 } else {
122 // 如果不是在链表的头部添加元素
123
124 // 创建一个Node节点prev，初始化的时候指向head，prev从head头节点开始。
125 Node prev = head;
126 // 注意，我们要找的位置是index这个位置的前一个位置相应的节点，找到index这个索引的前一个索引的位置。
127 for (int i = 0; i < index - 1; i++) {
128 // 将当前prev存储的节点的下一个节点放入到prev变量中。每次做的操作都是，将当前prev存储的这个节点的next下一个节点放进prev这个节点变量中。prev这个节点在链表中一直向前移动。直到移动到index-1这个位置。
129 prev = prev.next;
130 }
131
132 // // 此时，移动到了index-1这个位置，找到了待插入节点的前一个节点。此时我们找到了待插入节点的前一个节点的位置。
133 // // 创建新元素的节点，创建一个节点，将元素放入到该节点中。
134 // Node node = new Node(e);
135 // // 将新元素的节点的下一个节点指向待插入节点的前一个节点的下一个节点的位置。
136 // node.next = prev.next;
137 // // 将待插入节点的前一个节点的下一个节点指向新元素的节点。此时将新元素节点挂在链表中了。
138 // prev.next = node;
139
140 // 一行代码，牛逼的替换上面的三行代码
141 // 首先，创建新元素e的Node节点，这个节点指向待插入节点的前一个节点的下一个节点的位置prev.next。
142 // 然后将新元素节点，指向待插入元素的节点的前一个节点，即待插入元素的前一个节点指向待插入元素的节点。
143 prev.next = new Node(e, prev.next);
144
145 // 维护size大小
146 size++;
147 }
148 }
149
150 /**
151 * 在链表末尾添加新的元素e
152 *
153 * @param e
154 */
155 public void addLast(E e) {
156 // 在size位置添加新的元素
157 add(size, e);
158 }
159
160 public static void main(String[] args) {
161
162
163 }
164
165 }6、为链表设立虚拟头节点，解决链表头节点特殊化处理问题。
上面是为链表添加元素，添加元素的时候遇到的一个问题，在向链表的任意一个位置添加元素的时候，在链表头添加元素和在链表的其他位置添加元素，逻辑上存在差别。那么，为什么在链表头部添加元素比较特殊呢，这是因为在为链表添加新元素节点的时候，要找到待添加元素节点的位置的相应之前的那一个节点，但是对于链表头来说，它没用前一个节点，所以，在逻辑上就会特殊一些。不过，在链表的具体实现中，有一个非常常用的技巧，可以把对链表头这种特殊操作与其他的操作统一起来，这个想法也非常简单，链表头不是没用之前一个节点吗，那么就创建一个链表头之前的节点，为链表设立虚拟头节点，这个虚拟头节点不存储任意元素，所以设置为null空，将这个空节点称为链表真正的head，称为dummyHead（虚拟头节点），此时来说，链表的第一个元素就是dummyHead的下一个节点（next）所对应的节点的元素，而不是dummyHead节点所对应的节点的元素。dummyHead这个节点的元素是根本不存在的，对于用户来讲也是根本没用意义的，这只是为了编写逻辑方便，dummyHead就是第一个节点的前一个节点的。 类比循环队列，浪费一个空间。
如何将存储666元素的node节点放入到索引为2的地方。即这里面的节点4。使用虚拟头节点的关键是找到index这个索引位置的元素之前的那个节点。因为prev的位置是用dummyHead位置开始遍历的。
执行for循环，当i=0的时候，执行prev = prev.next;此时prev的位置在索引为0的地方。
执行for循环，当i=1的时候，执行prev = prev.next;此时prev的位置在索引为1的地方。
此时执行创建一个node节点，然后将元素666存储到节点node中，Node node = new Node(e);然后将node.next = prev.next;
然后再执行prev.next = node;然后维护size的大小。
此时，就完成了将存储666元素的节点node插入到链表中了。
代码案例，如下所示：
1 package com.company.linkedlist;
2
3 /**
4 * 链表结构的创建，链表是一种线性的数据结构
5 *
6 * @ProjectName: dataConstruct
7 * @Package: com.company.linkedlist
8 * @ClassName: LinkedList
9 * @Author: biehl
10 * @Description: ${description}
11 * @Date: 2020/3/2 14:42
12 * @Version: 1.0
13 */
14 public class LinkedList<E> {
15
16
17 // 链表是由一个一个节点组成
18 private class Node {
19 // 设置公有的，可以让外部类进行修改和设置值
20 public E e;// 成员变量e存放元素
21 public Node next;// 成员变量next指向下一个节点，指向Node的一个引用
22
23 /**
24 * 含参构造函数
25 *
26 * @param e
27 * @param next
28 */
29 public Node(E e, Node next) {
30 this.e = e;
31 this.next = next;
32 }
33
34 /**
35 * 无参构造函数
36 */
37 public Node() {
38 this(null, null);
39 }
40
41 /**
42 * 如果用户只传了e，那么可以调用含参构造函数，将next指定为null
43 *
44 * @param e
45 */
46 public Node(E e) {
47 this(e, null);
48 }
49
50 /**
51 * @return
52 */
53 @Override
54 public String toString() {
55 return "Node{" +
56 "e=" + e.toString() +
57 ", next=" + next +
58 '}';
59 }
60 }
61
62
63 private Node dummyHead;// Node类型的变量dummyHead，虚拟头节点
64 private int size;// 链表要存储一个一个元素，肯定有大小，记录链表有多少元素
65
66 /**
67 * 无参的构造函数
68 */
69 public LinkedList() {
70 // 虚拟头节点的元素是null空，初始化的时候next的值也为null空。
71 dummyHead = new Node(null, null);// 初始化一个链表，虚拟头节点dummyHead是一个节点。
72 // 链表大小是0，此时对于一个空的链表来说，是存在一个节点的，虚拟头节点。
73 size = 0;// 大小size为0
74 }
75
76 /**
77 * 获取链表的大小，获取链表中的元素个数
78 *
79 * @return
80 */
81 public int getSize() {
82 return size;
83 }
84
85 /**
86 * 判断返回链表是否为空
87 *
88 * @return
89 */
90 public boolean isEmpty() {
91 return size == 0;
92 }
93
94 /**
95 * 在链表头部添加新的元素e
96 *
97 * @param e
98 */
99 public void addFirst(E e) {
100 // // 创建一个新的节点，然后将元素传入进去即将元素写入到节点上面。
101 // Node node = new Node(e);
102 // // 将新的节点的下一个节点指向head头部节点。
103 // node.next = head;
104 // // 然后将node这个新的节点指向head节点。
105 // head = node;
106
107 // 上面三行代码，可以使用下面一行代码书写。
108 // 首先，创建一个Node节点，将元素e传入第一个参数，将这个元素直接指向链表的head即参数二。
109 // 然后，将这个Node赋值给head头部节点。
110 // head = new Node(e, head);
111 //
112 // // 维护size的长度，让size自增
113 // size++;
114
115 // 复用add方法，在0的索引位置，添加一个元素。
116 add(0, e);
117 }
118
119 /**
120 * 在链表的index(0-based)索引位置添加新的元素e
121 * <p>
122 * 要将元素e插入到索引index这个位置，就需要找到当我们插入新元素节点之后这个节点之前的那个节点是谁。
123 * <p>
124 * 如何将新的节点插入到正确的位置呢？
125 * 那么就必须要找到当我们插入新的元素节点之后这个节点之前的那个节点是谁。
126 * 相应的，之前的那个节点要prev，prev初始化是和head在一个位置的，
127 * 我们要找到新的元素的节点之前的那个节点应该是谁，
128 * 我就直接把之前的那个节点的next指向新的元素的节点，
129 * 新的元素的节点的next指向它之前的那个节点的之后的这个节点，
130 * 就完成了这个插入操作了。
131 *
132 * @param index
133 * @param e
134 */
135 public void add(int index, E e) {
136 // 如果指定的索引位置不符合要求，抛出异常
137 // 切记，index是可以取到size，在链表的尾部添加一个元素
138 if (index < 0 || index > size) {
139 throw new IllegalArgumentException("Add failed. Illegal index.");
140 }
141
142
143 // prev初始化位置和dummyHead位置一样，循环的目的是搜索插入新元素节点之前的那个节点是谁。
144
145 // 创建一个Node节点prev，初始化的时候指向dummyHead虚拟头节点。
146 // 注意，dummyHead节点在开始的时候指向的是0这个索引位置的元素它之前的那个节点。
147 Node prev = dummyHead;
148
149 // 注意，我们要找的位置是index这个索引位置的元素它前一个位置相应的节点。
150
151 // 考虑，如何在索引2的位置插入一个元素。
152 // 0 1 2 3，这个是在index-1的位置新增节点。
153 // 虚拟头节点 0 1 2 3，这个是在index的位置新增节点。
154 // 循环的目的是搜索插入新元素节点之前的那个节点是谁。
155 for (int i = 0; i < index; i++) {
156 // 将当前prev存储的节点的下一个节点放入到prev变量中。
157 // 从0开始遍历，将prev的下一个节点prev.next指向prev，即prev向后移动，
158 // 直到找到待插入节点的前一个节点的位置。此时，执行循环外的代码了。
159 prev = prev.next;
160 }
161
162 // // 此时，移动到了index-1这个位置，找到了待插入节点的前一个节点
163 // // 创建新元素的节点
164 // Node node = new Node(e);
165 // // 将新元素的节点的下一个节点指向待插入节点的前一个节点的下一个节点的位置。
166 // node.next = prev.next;
167 // // 将待插入节点的前一个节点的下一个节点指向新元素的节点。此时将新元素节点挂在链表中了。
168 // prev.next = node;
169
170 // 一行代码，牛逼的替换上面的三行代码
171 // 首先，创建新元素e的Node节点，这个节点指向待插入节点的前一个节点的下一个节点的位置prev.next。
172 // 然后将新元素节点，指向待插入元素的节点的前一个节点，即待插入元素的前一个节点指向待插入元素的节点。
173 // new Node(e prev.next)，创建节点，元素是e，指向prev.next，然后将prev.next指向创建的节点。
174 prev.next = new Node(e, prev.next);
175
176 // 维护size大小
177 size++;
178
179 }
180
181 /**
182 * 在链表末尾添加新的元素e
183 *
184 * @param e
185 */
186 public void addLast(E e) {
187 // 在size位置添加新的元素
188 add(size, e);
189 }
190 }7、链表元素的删除操作，使用有dummyHead虚拟头节点的链表。现在需要删除索引为2位置的元素。
执行for (int i = 0; i < index; i++)循环，当i=0的时候，执行prev = prev.next;此时prev的位置在索引为0的节点上。
执行for (int i = 0; i < index; i++)循环，当i=1的时候，执行prev = prev.next;此时prev的位置在索引为1的节点上。
执行for (int i = 0; i < index; i++)循环，当i=2的时候，2不小于索引index=2，所以循环结束。即此时，找到待删除那个元素节点的前一个节点元素。
找到待删除元素节点之前的那个元素节点之后,prev.next就是待删除元素的节点，待删除元素的节点称为delNode。此时执行prev.next = delNode.next，换句话说，此时链表变成了这样的。
此时，索引为1的prev节点直接指向了索引为3的节点，也就是说索引为1的prev节点直接跳过了它原本的next节点，指向了它原本next节点的next节点，也就是我们delNode这个节点的next节点，这样操作完以后，就将索引为2的节点跳过去了，从某种意义上来讲，其实就等同于把索引为2的节点从链表中删除了，当然，这里为了方便jvm能够回收这个空间， 我们还应该手动让索引为2的这个节点位置的next和链表脱离出去，即让delNode这个节点的next指向NULL空即可。
具体代码，如下所示：
1 package com.linkedlist;
2
3 /**
4 * @ProjectName: dataConstruct
5 * @Package: com.linkedlist
6 * @ClassName: LinkedList
7 * @Author: biehl
8 * @Description: ${description}
9 * @Date: 2020/3/14 11:51
10 * @Version: 1.0
11 */
12 public class LinkedList<E> {
13
14 // 链表是由一个一个节点组成
15 private class Node {
16 // 设置公有的，可以让外部类进行修改和设置值
17 public E e;// 成员变量e存放元素
18 public Node next;// 成员变量next指向下一个节点，指向Node的一个引用
19
20 /**
21 * 含参构造函数
22 *
23 * @param e
24 * @param next
25 */
26 public Node(E e, Node next) {
27 this.e = e;
28 this.next = next;
29 }
30
31 /**
32 * 无参构造函数
33 */
34 public Node() {
35 this(null, null);
36 }
37
38 /**
39 * 如果用户只传了e，那么可以调用含参构造函数，将next指定为null
40 *
41 * @param e
42 */
43 public Node(E e) {
44 this(e, null);
45 }
46
47 /**
48 * @return
49 */
50 // @Override
51 // public String toString() {
52 // return "Node{" +
53 // "e=" + e.toString() +
54 // ", next=" + next +
55 // '}';
56 // }
57 }
58
59
60 private Node dummyHead;// Node类型的变量dummyHead，虚拟头节点
61 private int size;// 链表要存储一个一个元素，肯定有大小，记录链表有多少元素
62
63 /**
64 * 无参的构造函数
65 */
66 public LinkedList() {
67 // 虚拟头节点的元素是null空，初始化的时候next的值也为null空。
68 dummyHead = new Node(null, null);// 初始化一个链表，虚拟头节点dummyHead是一个节点。
69 // 链表大小是0，此时对于一个空的链表来说，是存在一个节点的，虚拟头节点。
70 size = 0;// 大小size为0
71 }
72
73 /**
74 * 获取链表的大小，获取链表中的元素个数
75 *
76 * @return
77 */
78 public int getSize() {
79 return size;
80 }
81
82 /**
83 * 判断返回链表是否为空
84 *
85 * @return
86 */
87 public boolean isEmpty() {
88 return size == 0;
89 }
90
91 /**
92 * 在链表头部添加新的元素e
93 *
94 * @param e
95 */
96 public void addFirst(E e) {
97 // // 创建一个新的节点，然后将元素传入进去即将元素写入到节点上面。
98 // Node node = new Node(e);
99 // // 将新的节点的下一个节点指向head头部节点。
100 // node.next = head;
101 // // 然后将node这个新的节点指向head节点。
102 // head = node;
103
104 // 上面三行代码，可以使用下面一行代码书写。
105 // 首先，创建一个Node节点，将元素e传入第一个参数，将这个元素直接指向链表的head即参数二。
106 // 然后，将这个Node赋值给head头部节点。
107 // head = new Node(e, head);
108 //
109 // // 维护size的长度，让size自增
110 // size++;
111
112 // 复用add方法，在0的索引位置，添加一个元素。
113 add(0, e);
114 }
115
116 /**
117 * 在链表的index(0-based)索引位置添加新的元素e
118 * <p>
119 * 要将元素e插入到索引index这个位置，就需要找到当我们插入新元素节点之后这个节点之前的那个节点是谁。
120 * <p>
121 * 如何将新的节点插入到正确的位置呢？
122 * 那么就必须要找到当我们插入新的元素节点之后这个节点之前的那个节点是谁。
123 * 相应的，之前的那个节点要prev，prev初始化是和head在一个位置的，
124 * 我们要找到新的元素的节点之前的那个节点应该是谁，
125 * 我就直接把之前的那个节点的next指向新的元素的节点，
126 * 新的元素的节点的next指向它之前的那个节点的之后的这个节点，
127 * 就完成了这个插入操作了。
128 *
129 * @param index
130 * @param e
131 */
132 public void add(int index, E e) {
133 // 如果指定的索引位置不符合要求，抛出异常
134 // 切记，index是可以取到size，在链表的尾部添加一个元素
135 if (index < 0 || index > size) {
136 throw new IllegalArgumentException("Add failed. Illegal index.");
137 }
138
139
140 // prev初始化位置和dummyHead位置一样，循环的目的是搜索插入新元素节点之前的那个节点是谁。
141
142 // 创建一个Node节点prev，初始化的时候指向dummyHead虚拟头节点。
143 // 注意，dummyHead节点在开始的时候指向的是0这个索引位置的元素它之前的那个节点。
144 Node prev = dummyHead;
145
146 // 注意，我们要找的位置是index这个索引位置的元素它前一个位置相应的节点。
147
148 // 考虑，如何在索引2的位置插入一个元素。
149 // 案例一、0 1 2 3，这个是在index-1的位置新增节点。
150 // 案例二、虚拟头节点 0 1 2 3，这个是在index的位置新增节点。
151 // 循环的目的是搜索插入新元素节点之前的那个节点是谁。
152 for (int i = 0; i < index; i++) {
153 // 将当前prev存储的节点的下一个节点放入到prev变量中。
154 // 从0开始遍历，将prev的下一个节点prev.next指向prev，即prev向后移动，
155 // 直到找到待插入节点的前一个节点的位置。此时，执行循环外的代码了。
156 prev = prev.next;
157 }
158
159 // // 此时，移动到了index-1这个位置，找到了待插入节点的前一个节点
160 // // 创建新元素的节点
161 // Node node = new Node(e);
162 // // 将新元素的节点的下一个节点指向待插入节点的前一个节点的下一个节点的位置。
163 // node.next = prev.next;
164 // // 将待插入节点的前一个节点的下一个节点指向新元素的节点。此时将新元素节点挂在链表中了。
165 // prev.next = node;
166
167 // 一行代码，牛逼的替换上面的三行代码
168 // 首先，创建新元素e的Node节点，这个节点指向待插入节点的前一个节点的下一个节点的位置prev.next。
169 // 然后将新元素节点，指向待插入元素的节点的前一个节点，即待插入元素的前一个节点指向待插入元素的节点。
170 // new Node(e prev.next)，创建节点，元素是e，指向prev.next，然后将prev.next指向创建的节点。
171 prev.next = new Node(e, prev.next);
172
173 // 维护size大小
174 size++;
175 }
176
177 /**
178 * 在链表末尾添加新的元素e
179 *
180 * @param e
181 */
182 public void addLast(E e) {
183 // 在size位置添加新的元素
184 add(size, e);
185 }
186
187
188 /**
189 * 获取链表的第index个位置的元素
190 * <p>
191 * 查询和修改都是获取到该索引位置的元素，这里就不画图了，画图造成博客打开太慢了，
192 * 类比上面的添加操作，根据for循环一步一步走，肯定可以理解的。
193 *
194 * @param index
195 * @return
196 */
197 public E get(int index) {
198 // 如果索引小于零，或者大于等于size的时候，就抛出异常
199 if (index < 0 || index >= size) {
200 throw new IllegalArgumentException("Get failed. Illegal index.");
201 }
202
203 // 遍历链表是需要遍历链表的每一个元素
204 // 从索引为零的地方开始遍历，即从虚拟头节点的下一个节点位置开始遍历的
205 Node current = dummyHead.next;
206 // 循环遍历，循环遍历的过程执行index次，获取到index索引位置的元素
207 for (int i = 0; i < index; i++) {
208 // 每次循环将获取到的下一个节点的元素替换上一次循环遍历的元素内容，
209 // 最后获得是最终index索引位置的元素。
210 current = current.next;
211 }
212 // 最终获取到的current.e就是我们想要获取到的元素
213 return current.e;
214 }
215
216 /**
217 * 获取到链表的第一个元素
218 *
219 * @return
220 */
221 public E getFirst() {
222 return get(0);
223 }
224
225 /**
226 * 获取到最后一个节点的元素
227 *
228 * @return
229 */
230 public E getLast() {
231 return get(size - 1);
232 }
233
234 /**
235 * 修改链表的第index个位置的元素为e
236 *
237 * @param index 元素index
238 * @param e 将新元素替换index索引位置的元素
239 */
240 public void set(int index, E e) {
241 // 如果索引小于零，或者大于等于size的时候，就抛出异常
242 if (index < 0 || index >= size) {
243 throw new IllegalArgumentException("Update failed. Illegal index.");
244 }
245
246 // 从索引为零的地方开始遍历，即从虚拟头节点的下一个节点位置开始遍历的
247 Node current = dummyHead.next;
248 // 循环遍历，此次遍历是找到index位置的元素
249 for (int i = 0; i < index; i++) {
250 current = current.next;
251 }
252
253 // 此时，找到了index索引位置的元素.
254 // 然后将新的元素替换之前index索引位置的元素即可。
255 current.e = e;
256 }
257
258 /**
259 * 查找链表中是否有元素e
260 *
261 * @param e
262 * @return
263 */
264 public boolean contains(E e) {
265 Node current = dummyHead.next;
266 // 循环遍历，从索引为0开始到链表长度size
267 // for (int i = 0; i < size - 1; i++) {
268 // // 每次循环，将下一个节点的元素替换上一个节点的元素
269 // current = current.next;
270 // // 如果该元素和参数元素相等，就返回true，否则返回false
271 // if (current.e == e) {
272 // return true;
273 // }
274 // }
275
276 // 使用while循环，当第一个元素的内容不为空的时候，就进行判断
277 while (current != null) {
278 // 如果该元素和参数元素相等，就返回true，否则返回false
279 if (current.e.equals(e)) {
280 return true;
281 }
282 current = current.next;
283 }
284 return false;
285 }
286
287 @Override
288 public String toString() {
289 StringBuilder stringBuilder = new StringBuilder();
290 // 使用while循环进行循环
291 // Node current = dummyHead.next;
292 // while (current != null) {
293 // stringBuilder.append(current + "->");
294 // current = current.next;
295 // }
296
297 // 使用for循环进行链表的循环
298 for (Node current = dummyHead.next; current != null; current = current.next) {
299 stringBuilder.append(current.e + "->");
300 }
301 stringBuilder.append("NULL");
302 return stringBuilder.toString();
303 }
304
305
306 /**
307 * 从链表中删除索引index位置的元素，返回删除的元素
308 *
309 * @param index
310 * @return
311 */
312 public E remove(int index) {
313 // 如果索引小于零，或者大于等于size的时候，就抛出异常
314 if (index < 0 || index >= size) {
315 throw new IllegalArgumentException("Update failed. Illegal index.");
316 }
317
318 // prev初始化位置和dummyHead位置一样，循环的目的是搜索插入新元素节点之前的那个节点是谁。
319 // 创建一个Node节点prev，初始化的时候指向dummyHead虚拟头节点。
320 // 注意，dummyHead节点在开始的时候指向的是0这个索引位置的元素它之前的那个节点。
321 Node prev = dummyHead;
322 // 循环遍历，找到待删除元素节点的前一个节点位置
323 for (int i = 0; i < index; i++) {
324 // 案例，删除索引为2节点的元素。
325 // i =0的时候，prev循环走到了索引为0的位置，prev的起始位置是dummyHead的位置
326 // i =1的时候，prev循环走到了索引为1的位置。
327 // i =2的时候，2不小于2，循环结束。
328 prev = prev.next;
329 }
330
331 // 循环结束，prev保存的就是待删除元素节点的前一个节点元素。
332
333 // 保存待删除元素
334 Node resultNode = prev.next;
335
336 // 将待删除元素节点的前一个节点的next指向待删除元素节点的next节点位置上。
337 prev.next = resultNode.next;
338
339 // 将待删除元素节点置空，方便垃圾回收。将此节点和链表脱离关系。
340 resultNode.next = null;
341 // 维护size的大小
342 size--;
343 return resultNode.e;
344 }
345
346 /**
347 * 从链表中删除第一个元素，返回删除的元素
348 *
349 * @return
350 */
351 public E removeFirst() {
352 return remove(0);
353 }
354
355 /**
356 * 删除链表中最后一个元素，返回删除的元素
357 *
358 * @return
359 */
360 public E removeLast() {
361 return remove(size - 1);
362 }
363
364 // 从链表中删除元素e
365 public void removeElement(E e) {
366
367 Node prev = dummyHead;
368 while (prev.next != null) {
369 if (prev.next.e.equals(e))
370 break;
371 prev = prev.next;
372 }
373
374 if (prev.next != null) {
375 Node delNode = prev.next;
376 prev.next = delNode.next;
377 delNode.next = null;
378 size--;
379 }
380 }
381
382 public static void main(String[] args) {
383 LinkedList<Integer> linkedList = new LinkedList<Integer>();
384 // 链表元素的添加
385 for (int i = 0; i < 5; i++) {
386 // linkedList.add(i, i * i);
387 linkedList.addFirst(i);
388 System.out.println("链表元素的添加: " + linkedList.toString());
389 }
390
391 System.out.println();
392 // 链表的查询
393 for (int i = 0; i < linkedList.size; i++) {
394 System.out.println("链表的查询: " + linkedList.get(i));
395 }
396
397 System.out.println();
398 // 链表的修改
399 linkedList.set(3, 111);
400 System.out.println(linkedList.toString());
401
402 // 链表元素的删除
403 linkedList.remove(1);
404 System.out.println(linkedList.toString());
405
406 // 链表元素的删除
407 linkedList.removeElement(2);
408 System.out.println(linkedList.toString());
409 }
410 }