1. 前言
在上一篇《顺序表》中，我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素，由于其底层是一段连续的空间，当ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后移动，时间复杂度为O(n)，效率比较低，因此ArrayList 不适合做任意位置插入和删除比较多的场景。因此：Java集合这种又引入了 LinkedList，即链表结构。
2. 链表
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中引用链接次序实现的。
注意：
- 从上图可看出，链表结构正在逻辑上是连续的，但是在物理上（内存）不一定连续。
- 现实中的节点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的额策略来分配的，两次申请的空间可能连续，也可能不连续。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表结构，但是我们重点掌握两种：
- 无头单向非循环链表：结构简单，一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
- 无头双向链表：在Java的集合类中
LinkedList底层实现就是无头双向循环链表
3. 单链表的实现
创建一个链表
public class MySingleList { // 节点 static class ListNode { public int val; // 数值域 - 存放当前节点的值 public ListNode next; // next域 指向下一个节点 public ListNode(int val) { this.val = val; } } // 链表的属性 链表的头节点 public ListNode head; // null public void createList() { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); node1.next = node2; node2.next = node3; node3.next = node4; this.head = node1; } }
画图表示：
3.1 打印链表
- 怎么从第一个节点走到第二个节点？
答：head = head.next - 什么时候算是把节点都遍历完成？
答：head == null
代码实现：
/*** * 打印链表 */ @Override public void display() { ListNode cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next;// 让cur这个节点 可以从一个节点走到下一个节点 } System.out.println(); }
3.2 头插法
在链表的第一个位置插入元素。
思路：
- 插入元素的
next指向head head指向插入元素
代码实现：
/** * 头插法 * @param data */ @Override public void addFirst(int data) { ListNode node = new ListNode(data); // 定义一个节点 node.next = head; head = node; }
3.3 尾插法
在链表的最后个位置插入元素
思路：
- 判断链表中是否有元素。
- 如果没有元素，直接添加头结点即可。
- 如果有元素，将原链表最后一个元素
next指向插入的元素。
代码实现：
/** * 尾插法 * @param data */ @Override public void addLast(int data) { ListNode node = new ListNode(data); // 定义一个节点 if (head == null) { // 链表一个元素都没有 head = node; } else { ListNode cur = head; while (cur.next != null) { cur = cur.next; } cur.next = node; } }
3.4 任意位置插入元素
思路：
- 判断
index是否合法（index < 0 或者 index 大于链表长度），如果不合法则抛出异常。 - 判断
index等于0或者index等于链表长度，则使用头插法或尾插法 cur找到index - 1位置- 插入元素的
next指向cur的next cur的next指向插入的元素
代码实现：
/** * 在index位置 插入data * @param index * @param data */ @Override public void addIndex(int index, int data) throws IndexException{ if (index < 0 || index > size()) { throw new IndexException("index不合法：" + index); } ListNode node = new ListNode(data); // 定义一个节点 if (head == null) { head = node; return; } if (index == 0) { addFirst(data); return; } if (index == size()) { addLast(data); return; } ListNode cur = searchPrevIndex(index); node.next = cur.next; cur.next = node; } /** * 找到index-1的位置 * @param index * @return */ private ListNode searchPrevIndex(int index) { ListNode cur = head; int count = 0; while (count != index - 1) { cur = cur.next; count++; } return cur; }
异常类：
public class IndexException extends RuntimeException{ public IndexException() { } public IndexException(String msg) { super(msg); } }
3.5 查找元素
代码实现：
/*** * 求当前链表 是否存在key * @param key * @return */ @Override public boolean contains(int key) { ListNode cur = head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; }
3.6 链表节点个数
代码实现：
/** * 求当前链表 有多少个节点 * @return */ @Override public int size() { ListNode cur = head; int count = 0; while (cur != null) { count++; cur = cur.next; } return count; }
3.7 删除元素
思路：
- 判断链表是否为空，如果为空直接返回
- 判断删除元素是否为头节点，如果是则
head指向head的next - 定义指针找到要删除节点的前一个节点
- 前一个节点的
next指向删除节点的next
代码实现：
/** * * @param key */ @Override public void remove(int key) { if (head == null) { return; } if (head.val == key) { head = head.next; return; } ListNode cur = findPrevKey(key); if (cur == null) { return;// 链表里要没有删除的数字 } ListNode del = cur.next; cur.next = del.next; } /** * 找到删除节点的前一个节点 * @param key * @return */ private ListNode findPrevKey(int key) { ListNode cur = head; while (cur.next != null) { if (cur.next.val == key) { return cur; } else { cur = cur.next; } } return null; }
3.8 删除链表中指定的所有元素
思路:
- 判断链表是否为空，如果是空直接返回
- 定义指针
cur：可能要删除的节点 - 定义指针
prev：可能要删除的节点的前驱 - 判断
cur的val是不是要删除的元素，如果是prev的next指向cur的next，cur指向cur的next；否则prev指向cur，cur指向cur的next - 判断头节点的
val是否为的元素，如果是头节点指向头节点的neext
代码实现：
/** * 删除链表中所有的key * @param key */ @Override public void removeAllKey(int key) { if (head == null) { return; } ListNode prev = head; // 表示当前可能要删除的节点 ListNode cur = head.next; // 可能要删除节点的前驱 while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if (head.val == key) { head = head.next; } }
3.9 清空链表
当一个对象，没有被引用的时候，就会被回收掉
/** * 清空链表 */ @Override public void clear() { head = null; }
4. 代码
5. OJ题
