共计 4243 个字符，预计需要花费 11 分钟才能阅读完成。
链表是什么？
上几篇文章中，分别介绍了动态数组，栈和队列，其中都是通过 resize 的方法进行动态扩容，从而实现了动态的数据结构，不过这种方法称为伪动态。真正的动态数据结构还要从链表说起，链表是真正的动态数据结构，一个动态数据结构不需要处理固定容量的问题，而且是最简单的动态数据结构，学好链表很重要，对后面复杂的数据结构是一种铺垫。链表见名知意，元素和元素之间就像链子一样拴住，元素也可以成为节点（Node），叫啥都行，反正能理解就好。每一个元素有两部分组成，一部分是元素本身，另一部分是下一个元素的引用。下文将元素本身就叫 e，他的下一个引用就叫做 next。
class Node<E>
{
E e; // 当前元素本身
Node next; // 下一个元素的引用
}
上图表示，第一个元素的 e 是 1，他的 next 是 2。第二个元素的 e 是 2，他的 next 是 3。最后一个元素的 e 是 3，但 next 为 null，因为 3 就是最后一个元素，可以说如果一个元素的 next 为 null，就代表他是最后一个元素。如果我想找到 2，那就通过 1 去找，如果我想找到 3，那不好意思，你也得通过 1 去找，因为 1 和 3 之间没有直接的关联，只能先通过 1 先找到 2，2 里面有存储 3 的地址。这也代表链表没有随机访问的能力，比如数组可以通过索引去找，效率很高。链表想找一个元素只能从头到尾遍历去找，查询效率低。
链表的实现
首先创建了一个 Node 内部类，目的是只给 LinkedList 外部类用，外面的类是不可以操作 Node 对象的，这样做是比较安全的。成员变量分别是 E e 和 Node next，e 用于存储元素本身，next 存储下一个元素的引用。LinkedList 里面维护了两个变量，Node head 和 size，head 用于存储目前链表的头元素，size 用于维护链表里元素的个数。
public class LinkedList<E> {
// 内部维护一个 Node 对象，给外部类（LinkedList）使用
private class Node<E> {
public E e; // 当前 Node 对象的元素值
public Node next; // 当前 Node 对象下一个对象的引用
public Node(E e,Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this.e = e;
this.next = null;
}
public Node() {
this.e = null;
this.next = null;
}
}
// 头元素节点
private Node head;
// 当前链表节点个数
private int size;
public LinkedList() {
head = null;
size = 0;
}
public int getSize() {return size;}
public boolean isEmpty() {return size == 0;}
}添加一个头节点
添加头节点就是要创建一个新 Node 节点，新节点的 e 为 666，新节点的 next 就指向了原来的头节点，改变指向后，要维护一下 head，让新创建的这个节点变成头节点。最后维护一下 size 的个数。
public void addFirst(E e)
{Node node = new Node(e); // 创建一个节点
node.next = head; // 节点的 next 为当前头节点
head = node; // 改变 head 指向，现在头的位置变成了最新的 node
//head = new Node(e,head); 以上三步可简化成这种写法
size++;
}按照索引位置添加元素
现在要把新元素添加到指定位置，比如索引为 2 的位置插入一个新元素。那就要找到索引 2 之前的那个元素，因为新元素插入后，要维护一下指向关系，原来是 1 的 next 为 2，现在 666 的 next 变成了 2，1 的 next 为 666。找到了 1 之后，先把 1 的 next 给 666，让 666 的 next 先指向 2，然后 1 的 next 在指向 666 就好啦。看下面图或者自己画一下就很清楚了。可是怎么能找到索引为 1 的元素呢？遍历！我们可以维护一个变量，用于保存每次 next 的值，可以看到从头元素到 1 的位置只需要一次 next。
public void addByIndex(E e,int index) //index = 2
{if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Because index is illegal.");
if(index == 0)
addFirst(e);
//1. 要想得到某个位置的元素，需要从第一个往后找，因为第一个存储的是第二个的 "联系方式"，第二个存储的是第三个人的 "联系方式"。// 这里循环只是遍历多少次才能拿到索引前的那个元素，里面的 x 变量没有任何使用意义。你也可以写成 x = 1; x < index; 只要是循环次数算对了就行。//0 1 2 3，如果 index = 2，那么待插入元素就是这样 0 1 _ 2 3，那么从头元素开始遍历，拿到索引为 1 的节点，只需要经过一次 next
Node prevNode = head;
for(int x = 0; x < index - 1; x++) {head = prevNode.next;}
//2. 拿到 currentNode 后，维护指向关系
Node node = new Node(e);
node.next = prevNode.next;
prevNode.next = node;
//currentNode.next = new Node(node,currentNode.next);// 简略写法
size++;
}虚拟节点的引入
实现上面的 addByIndex 方法时，需要对 index 为 0 时，做特殊判断处理。那能不能不做特殊判断，改变一种思想，让 addFirst 方法也能复用呢？办法是使用虚拟节点。设计一个 dummyHead，每次在第 0 个位置添加元素时候，都可以通过 dummyHead 找到原来的头元素位置。然后按索引添加的逻辑就可以复用了。
private Node dummyHead;
private int size;
public LinkedList() {dummyHead = new Node(null, null); // 创建虚拟节点
size = 0;
}
// 链表头添加元素
public void addFirst(E e) {addByIndex(e, 0);
}
// 链表尾添加元素
public void addLast(E e) {addByIndex(e, size);
}
public void addByIndex(E e, int index) //3
{if (index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Because index is illegal.");
// 如果 index 为 3，那么从 dummyHead 到索引 2 的位置，一共要三次 next。循环从 0 开始，然后 <3，也就是 0 1 2 一共三次
Node currentNode = dummyHead; // 从头元素开始遍历 dummy 0 1 2 -- 3
for (int x = 0; x < index; x++) {dummyHead = currentNode.next;}
Node node = new Node(e);
node.next = currentNode.next;
currentNode.next = node;
//currentNode.next = new Node(node,currentNode.next);// 简略写法
size++;
}在提供一些基础的方法，比如查询，删除，是否包含某个元素，修改某个元素。只要掌握了遍历链表的思想，其实万变不离其宗。要注意的就是控制好索引的边界。
public E get(int index) {if (index < 0 || index >= size)
throw new IllegalArgumentException("Get filed.Index is not true!");
Node currentNode = dummyHead;
for (int x = 0; x < index; x++) {currentNode = currentNode.next;}
return (E) currentNode.next.e;
}
public E getFirst()
{return get(0);
}
public E getLast()
{return get(size - 1);
}
public void set(E e,int index)
{if (index < 0 || index >= size)
throw new IllegalArgumentException("Get filed.Index is not true!");
Node currentNode = dummyHead;
for(int x = 0; x < index; x++) {currentNode = currentNode.next;}
currentNode.next.e = e;
}
public boolean contains(E e)
{
Node currentNode = dummyHead;
for(int x = 0; x < size; x++)
{
currentNode = currentNode.next;
if(currentNode.e.equals(e))
{return true;}
}
return false;
}
@Override
public String toString() {StringBuffer sb = new StringBuffer();
sb.append("linkedHead[");
Node currentNode = dummyHead;
for(int x = 1; x <= size; x++)
{
currentNode = currentNode.next;
sb.append(currentNode.e + "....");
}
sb.append("]linkedFooter");
return sb.toString();}
删除操作
// 删除链表中的某个元素
public E delete(int index)
{
Node currentNode = dummyHead;
for(int x = 0; x < index; x++) {currentNode = currentNode.next;}
Node delNode = currentNode.next;
currentNode.next = delNode.next;
delNode.next = null;
size--;
return (E) delNode.e;
}
