概要
之前我们分别学习了解了动态数组、栈、队列，其实他们的底层都是依托静态数组来实现的、只是通过我们定义的 resize 方法来动态扩容解决固定容量的问题，那么我们即将学习的链表，它其实是一种真正的动态数据结构。
介绍
链表是一种最简单的动态数据结构，它能够辅助组成其它的数据结构，链表中的元素可存储在内存中的任何地方（不需要连续的内存，这一点和我们的数组具有很大的区别，数组需要连续的内存），链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串接在一起。
存储链表的数据的我们一般称为节点（Node），节点一般分为两部分，一部分存储我们真正的数据，而另外一部分存储的是下一个节点的引用地址。
class Node{
private E e; // 存储的真正元素
private Node next; // 存储下一个 node 的引用地址 (指向下一个 node)
}
比如现在我们将元素 A、B、C 三个节点添加到链表中，示意图如下：
从图中节点 A 到节点 B 之间的箭头代表，节点 A 指向了节点 B（NodeA.next = NodeB），因为在实际业务中我们的链表长度不可能是无穷无尽的，基本上都是有限个节点，通常定义链表中的最后一个元素它的 next 存储的是 NULL（空），换句话说，如果在链表中，一个节点的 next 是空（NULL）的话，那么它一定是最后一个节点（对应我们图中的 C 节点）。
根据我们上面介绍的链表基本结构，下面我们用代码定义一下链表的基本骨架（这里我们引入了一个虚拟的头结点，下面我们会作说明）
public class LinkedList<E> {
/**
* 虚拟的头结点
*/
private Node dummyHead;
/**
* 链表中节点的个数
*/
private int size;
public LinkedList() {
// 创建一个虚拟的头结点
dummyHead = new Node();
}
// 节点定义
private class Node {
// 存储节点的元素
public E e;
// 存储下一个节点的地址
public Node next;
public Node() {
}
public Node(E e) {
this.e = e;
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return “Node{” +
“e=” + e +
“, next=” + next +
‘}’;
}
}
}
后面我们对链表的添加节点、删除节点以及查询节点，代码实现都会基于这个基本骨架
向链表中添加节点
思路分析：
一般我们向链表中添加节点，基本思路：找到添加节点位置的前一个节点 preNode，然后再改变链表的地址引用；由于链表的第一个节点也就是头结点没有前节点，此时我们为了操作方便，为链表新增了不存储任何元素的一个虚拟的头结点 dummyHead（不是必须的，对用户来讲是不可见的），其实链表中真正的第一个节点是节点 A（dummyHead.next），这样我们就能保证了，链表中存储元素的节点都有前一个节点。
下面我们来看一下，如果现在有一个节点 D，我们准备把它插入到节点 B 的位置，我们需要做哪些操作
第一步：我们首先要找到节点 B 的前一个节点，也就是节点 A
第二步：将新节点 D 的指向指到节点 B（NodeD.next = NodeA.next），然后再将节点 A 的指向，指到节点 D（NodeA.next = NodeD），这样我们的节点就能串接起来了
代码实现：
/**
* 向链表中指定位置插入节点（学习使用，真正插入不会指定索引）
*
* @param index 索引的位置
* @param e 节点元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException(“ 不是有效的索引 ”);
}
Node prev = dummyHead;
// 找到 index 位置的前一个节点
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 新建一个节点，进行挂接
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
链表的遍历
进行链表遍历，我们需要从链表中真正的第一个元素开始，也就是 dummyHead.next
/**
* 获取链表中 index 位置的元素
*
* @param index 索引的位置
* @return 节点的元素
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException(“ 不是有效的索引 ”);
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
修改链表中元素
/**
* 修改链表中 index 位置节点的元素
*
* @param index 索引的位置
* @param e 节点的元素
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException(“ 不是有效的索引 ”);
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
查找链表中是否包含某元素
/**
* 查找链表中是否包含元素 e
*
* @param e
* @return
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
删除链表中的元素
在链表中删除元素，与在链表中添加元素有点类似
第一步：我们首先找到删除节点位置的前一个节点，我们用 prev 表示，被删除的节点我们用 delNode 表示
第二步：改变链表的引用地址：prev.next = delNode.next（等同于，将节点在链表中删除）
/**
* 删除链表中 index 位置的节点
*
* @param index
*/
public void remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException(“ 不是有效的索引 ”);
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size–;
}
完整版代码 GitHub 仓库地址：Java 版数据结构 - 链表 欢迎大家【关注】和【Star】
至此笔者已经为大家带来了数据结构：静态数组、动态数组、栈、数组队列、循环队列、链表；接下来，笔者还会一一的实现其它常见的数组结构，大家一起加油!
静态数组
动态数组
栈
数组队列
循环队列
链表
循环链表
二分搜索树
优先队列
堆
线段树
字典树
AVL
红黑树
哈希表
….
持续更新中，欢迎大家关注公众号 小白程序之路（whiteontheroad），第一时间获取最新信息！！！
笔者博客地址：http:www.gulj.cn