概述
使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1)，但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。
链表（LinkedList）是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成，是有序的列表。
链表是以节点的方式来存储，是链式存储，每个节点包含data域，next域（指向下一个节点），链表分为带头节点的链表和没有头节点的链表，根据实际的需求来确定。
按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用另外一个属性描述这个结点的下一个结点。
类名 Node
构造方法 Node(T t,Node next)：创建Node对象
成员变量
T item：存储数据
Node next：指向下一个结点
public static class Node {
public String item;
public Node next;
public Node(String item, Node next) {
this.item = item;
this.next = next;
}
}
单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
API设计
类名：LinkList
构造方法：LinkList()：创建LinkList对象
成员方法：
public void clear()：空置线性表
public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
public int length()：获取线性表中元素的个数
public E get(int i)：读取并返回线性表中的第i个元素的值
public void insert(E e)：往线性表中添加一个元素；
public void insert(int i,E e)：在线性表的第i个元素之前插入值为e的数据元素
public E remove(int i)：删除并返回线性表中第i个数据元素。
public int indexOf(E e)：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
成员内部类：private class Node：结点类
成员变量：
private Node head：记录首结点
private int n：记录链表的长度
代码实现
public class LinkList<E> {
//记录首结点
private Node<E> head;
//记录链表的长度
private int n;
public LinkList() {
// 初始化链表
n = 0;
head = new Node(null, null);
}
//空置线性表
public void clear() {
head.item = null;
head.next = null;
n = 0;
}
//判断线性表是否为空，是返回true，否返回false
public boolean isEmpty() {
return n == 0;
}
//获取线性表中元素的个数
public int length() {
return n;
}
//读取并返回线性表中的第index个元素的值
public E get(int index) {
if (index < 0 || index >= n) {
throw new RuntimeException("下标不合法");
}
//获取第1个元素的结点
Node<E> node = head.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.item;
}
//往线性表中添加一个元素
public void insert(E e) {
// 找到最后一个节点
Node node = head;
// 只要node的下一个节点不为null，说明还有下一个元素
while (node.next != null) {
node = node.next;
}
// 到这里，node就是最后一个节点
// 创建一个新的节点
Node newNode = new Node(e, null);
// 直接将最后一个节点的下一个结点指向新结点
node.next = newNode;
// 链表长度+1
n++;
}
//在线性表的第i个元素之前插入值为e的数据元素
public void insert(int index, E e) {
if (index < 0 || index >= n) {
throw new RuntimeException("位置不合法");
}
// 寻找index之前的节点
// pre是我们要插入元素位置的上一个节点
Node pre = head;
for (int i = 0; i < index; i++) {
// 取出下一个元素赋值给pre
pre = pre.next;
}
// 到这里，插入下标的上一个节点就找到了
// 取出index下一个位置的元素
Node next = pre.next;
// 构建新的Node
Node newNode = new Node(e, next);
pre.next = newNode;
// 长度+1
n++;
}
//删除并返回线性表中第index个数据元素
public E remove(int index) {
if(index < 0 || index >= n) {
throw new RuntimeException("下标位置不合法");
}
// 寻找index之前的元素
Node pre = head;
for (int i = 0; i < index; i++) {
// 取出下一个元素赋值给pre
pre = pre.next;
}
// 到这里就找到了之前的元素
// 获取当前index位置的结点
Node<E> current = pre.next;
// 获取当前index位置的下一个节点
Node<E> next = current.next;
// 前一个节点指向下一个节点
pre.next = next;
// 长度-1
n--;
return current.item;
}
//返回线性表中首次出现的指定的数据元素的位序号，若不存在返回-1
public int indexOf(E e) {
int index = 0;
if (e == null) {
for (LinkList.Node x = head; x != null; x = x.next) {
if (x.item == null)
return index-1;
index++;
}
} else {
for (LinkList.Node x = head; x != null; x = x.next) {
if (e.equals(x.item))
return index-1;
index++;
}
}
return -1;
}
private class Node<E> {
public E item;
public Node<E> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
}
双向链表
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
节点API设计
类名：Node
构造方法：Node(T t,Node pre,Node next)：创建Node对象
成员变量
T item:存储数据
Node next：指向下一个结点
Node pre:指向上一个结点
双向链表API设计
类名：TwoWayLinkList
构造方法：TwoWayLinkList()：创建TowWayLinkList对象
成员方法
public void clear()：置空线性表
public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
public int length():获取线性表中元素的个数
public E get(int index):读取并返回线性表中的第index个元素的值
public void insert(E e)：往线性表中添加一个元素；
public void insert(int i,E e)：在线性表的第i个元素之前插入值为e的数据元素
public E remove(int i)：删除并返回线性表中第i个数据元素。
public int indexOf(E e)：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
public E getFirst()：获取第一个元素
public E getLast()：获取最后一个元素
成员内部类：private class Node：结点类
成员变量
private Node first：记录首结点
private Node last：记录尾结点
private int n：记录链表的长度
代码实现
//双向链表
public class TwoWayLinkList<E> {
//记录首结点
private Node<E> first;
//记录尾结点
private Node<E> last;
//记录链表的长度
private int n;
public TwoWayLinkList() {
first = new Node<>(null,null,null);
last = null;
n = 0;
}
//置空线性表
public void clear(){
last = null;
first.pre = null;
first.item = null;
first.next = null;
n = 0;
}
//判断线性表是否为空，是返回true，否返回false
public boolean isEmpty(){
return n == 0;
}
//获取线性表中元素的个数
public int length() {
return n;
}
//读取并返回线性表中的第index个元素的值
public E get(int index){
if (index < 0 || index >= n) {
throw new RuntimeException("下标不合法");
}
//获取第1个元素的结点
Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.item;
}
//往线性表中添加一个元素
public void insert(E e){
if (last == null) {
//如果last为空说明链表刚被初始化，那么第一个元素，就是last
last = new Node<>(first,e,null);
first.next = last;
} else {
// 说明链表已经有了元素
Node<E> oldLast = this.last;
Node<E> node = new Node<>(oldLast, e, null);
oldLast.next = node;
last = node;
}
//长度+1
n++;
}
//在线性表的第index个元素之前插入值为e的数据元素
public void insert(int index,E e){
if (index < 0 || index >= n) {
throw new RuntimeException("下标不合法");
}
// 获取头结点
Node<E> pre = this.first;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
// 到这里之后，我们就找到了待插入下标位置的前一个元素
Node next = pre.next;
//构建一个新的结点
Node<E> newNode = new Node<>(pre, e, next);
pre.next = newNode;
next.pre = newNode;
// 长度+1
n++;
}
//删除并返回线性表中第index个数据元素
public E remove(int index){
if (index < 0 || index >= n) {
throw new RuntimeException("下标不合法");
}
// 获取头结点
Node pre = first;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
// 到这里，pre就是我们要删除下标位置的前一个节点
// 获取待删除的当前节点
Node current = pre.next;
// 获取待删除节点的下一个节点
Node next = current.next;
pre.next = next;
next.pre = pre;
// 长度-1
n--;
return (E) current.item;
}
//返回线性表中首次出现的指定的数据元素的位序号，若不存在返回-1
public int indexOf(E e) {
int index = 0;
if (e == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index-1;
index++;
}
} else {
for (Node x = first; x != null; x = x.next) {
if (e.equals(x.item))
return index-1;
index++;
}
}
return -1;
}
//获取第一个元素
public E getFirst() {
if (isEmpty()) {
return null;
}
return (E) first.next.item;
}
//获取最后一个元素
public E getLast() {
if (isEmpty()) {
return null;
}
return last.item;
}
private class Node<E> {
//存储数据
E item;
//指向上一个结点
Node pre;
//指向下一个结点
Node next;
Node(Node<E> pre, E element, Node<E> next) {
this.item = element;
this.next = next;
this.pre = pre;
}
}
}
时间复杂度
get(int i)：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)；
insert(int i,E e)：每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)；
remove(int i)：每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)。
相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的， 它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换。
相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。
结论：链表的查询性能比数组（顺序表）低，但是增删比数组高。其实，在我们使用的过程中，链表的使用频率是相当低的，因为只要我们尽可能的避免了顺序表的扩容，并且保证每次插入都是在顺序表最后一位插入，那么顺序表的增删操作性能也比链表要高。
单链表反转
需求：原链表中数据为：1→2→3→4；反转后链表中数据为：4→3→2→1。
思路：将head指针放在链表的最后面，然后改变链表的指针方向。
API设计：
public void reverse()：对整个链表反转
private Node reverse(Node curr)：反转链表中的某个结点curr,并把反转后的curr结点返回
使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点， 直到把最后一个结点反转完毕，整个链表就反转完毕。
代码实现：
//对整个链表反转
public void reverse() {
//空链表，不反转
if (n == 0) {
return;
}
reverse(head.next);
}
//反转链表中的某个结点current,并把反转后的current结点返回
private Node<E> reverse(Node<E> current) {
// 判断一下当前节点是否是最后一个节点
if (current.next == null) {
// 说明当前节点是最后一个节点
// 最后一个节点需要让头节点指向它
head.next = current;
return current;
}
// 如果不是最后一个节点，反转下一个节点
Node next = reverse(current.next);
next.next = current;
// 当前节点的下一个节点设为null
current.next = null;
return current;
}
循环链表
循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结 点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。（循环链表中没有头指针）
//循环链表
public class LoopList {
public static void main(String[] args) {
Node n1 = new Node("1", null);
Node n2 = new Node("2", null);
Node n3 = new Node("3", null);
Node n4 = new Node("4", null);
// 构造循环链表
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n1;
}
private static class Node {
public String item;
public Node next;
public Node(String item, Node next) {
this.item = item;
this.next = next;
}
}
}
约瑟夫环问题
问题描述：传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。
问题转换：
41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
1、编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
2、自退出那个人开始的下一个人再次从1开始报数，以此类推；
3、求出最后退出的那个人的编号。
解题思路：
1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
2.使用计数器count，记录当前报数的值；
3.遍历链表，每循环一次，count++；
4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
//约瑟夫环问题
public class Joseph {
public static void main(String[] args) {
// 构建循环链表
Node first = new Node(1, null);
// 记录前一个节点
Node pre = first;
// 构造一个41节点的循环链表
for (int i = 2; i <= 41; i++) {
// 每一次循环，构建一个Node
Node node = new Node(i, null);
pre.next = node;
// 记录当前节点为上一个节点
pre = node;
if (i == 41) {
// 说明到最后了，让最后一个节点指向第一个节点
pre.next = first;
}
}
// 计数器count
int count = 0;
// 遍历链表，每次循环count++
Node n = first;
// 记录上一个节点
Node back = null;
// 循环链表
while (n != n.next) {
// 报数
count++;
// 判断count是否为3，如果是，删除当前节点
if (count == 3) {
back.next = n.next;
System.out.println("当前死亡的人：" + n.item);
// 计数器清零
count = 0;
// 下一个人继续
n = n.next;
} else {
// 记录上一个节点
back = n;
// 下一个人继续
n = n.next;
}
}
}
private static class Node {
public int item;
public Node next;
public Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以让我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍。
中间值问题
找出链表的中间元素值并返回。利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。
如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。
private static int getMid(Node node) {
// 给一个快指针
Node fast = node;
// 给一个慢指针
Node slow = node;
// 遍历链表，移动指针
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.item;
}
单链表有环问题
单链表有环问题和循环链表是两码事。循环链表是我们为了解决某个问题而给出的解决方案。而单链表有环问题则是我们在使用链表的过程中失误操作锁带来的bug。
使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。
//判断当前链表是否有环
public static boolean isCircle(Node node) {
Node slow = node;
Node fast = node;
// 遍历
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
有环链表入口问题
查找有环链表中环的入口结点。当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。
//获取有环链表的环入口，返回入口值
public static int getEnter(Node node) {
Node slow = node;
Node fast = node;
// 定义一个新指针
Node temp = null;
// 遍历链表
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
// 说明两个指针相遇了，有环，新指针开始移动
temp = node;
continue;
}
if (temp != null) {
// temp不为空，说明新指针已经开始移动了
temp = temp.next;
// 判断一下新指针与慢指针是否相等，如相遇，则是环起点
if (temp == slow) {
return temp.item;
}
}
}
return 0;
}
评论区