LinkedList详解

1. 链表的基础概念

1.1 为什么需要链表

在上个章节中我们熟悉了ArrayList​的使用，了解到ArrayList​底层使用数组来存储元素，是一段连续的内存空间，当在ArrayList​任意位置插入或删除元素时，就需要将后续所有元素向前或往后移动，时间复杂度为O(n)​，效率比较低，因此不适合做任意位置删除或插入比较多的场景。并且空间利用率比较低，需要预留好空间给新增元素。

而链表的设计初衷，就是为了解决数组固定长度，增删效率低，空间浪费的问题，链表是一种动态的线性数据结构，无需连续内存，增删操作只需要修改指针，效率更高。

1.2 什么是链表

链表是由一组节点组成的线性表，节点之间通过指针串联，而非依赖连续内存地址。这就使得链表在逻辑上连续，物理上无序。可以想象成链表就是一串珍珠手链，每颗珍珠（节点）都有一个珠眼（指针域），由线（内存地址）串联在一起，构成完整的项链（链表）。​

链表的每个节点都是一个对象，包含两个值：数据域和指针域，指针域里面存放的是下一个节点的内存地址或上一个节点的内存地址。是链表串联的关键。根据节点的特点我们又能将链表分为多类：

• 根据链表的头节点是否会改变可分为带头链表和无头链表，带头是指头节点地址永远不变，与头节点里面是否存放数据无关
• 根据链表的节点之间是单向还是双向分为单向链表和双向链表
• 根据链表是否循环，也就是尾节点是否指向头节点，分为循环链表和非循环链表

这三种状态组合在一起就产生了 8 种链表，我们主要学习的是无头单向非循环链表和无头双向非循环链表。

​

​

2. 单向链表

2.1 手动实现单链表

单向链表是指链表的每个节点包含两部分：数据域val​和指针域，指针域里面存放的是下一个节点的内存地址next​。头节点我们称之为head​，除了环形链表外，尾节点的指针域为null​。接下来让我们手动创建一个单向链表MySingleList​，数据域存放的是整形int​，包含以下方法：

public interface IList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
//清除链表
public void clear();
//打印链表
public void display();
}

• 创建节点ListNode​

链表是由节点组成，我们首先要创建节点类，包含数据域val​和指针域next​，那么这个节点类是作为一个单独类创建还是作为MySingleList​的内部类创建呢？在使用链表的时候我们是接触不到节点的，换言之节点是链表的底层实现细节，对外不需要暴露，所以可以将之封装起来。再言之，内部类天然具备访问外部类成员的优势，节点类可以直接操作链表的私有成员，链表也可以直接操作节点的成员。再进一步将之设为静态内部类可以独立实例化，不依赖外部类的实例化。所以我们将ListNode​创建为私有静态内部类。

public class MySingleList implements IList {

private static class LinkNode {
// 数据域
public int val;

// 指针域，指向下一个节点对象
public LinkNode next;

// 构造方法
public LinkNode (int val) {
this.val = val;
}
// 无参构造方法
public LinkNode () {}
}

// 头指针
public LinkNode head;

@Override
public void addFirst(int data) {

}

@Override
public void addLast(int data) {

}

@Override
public void addIndex(int index, int data) {

}

@Override
public boolean contains(int key) {
return false;
}

@Override
public void remove(int key) {

}

@Override
public void removeAllKey(int key) {

}

@Override
public int size() {
return 0;
}

@Override
public void clear() {

}

@Override
public void display() {

}
}

• 实现size()​方法

我们可以通过遍历链表获取链表的长度，但是链表没有下标，我们该怎么遍历呢？我们回顾链表的性质：由一组节点组成，每个节点的指针域next​存放了下一个节点的内存地址，并且最后一个节点的指针域为null​，那我们就可以由当前节点的next​得到下一个节点，一直往下拿并计数，直到节点的next​为null​

public int size() {
// 计数器
int len = 0;
// 将头节点 head 给cur，防止丢失head
LinkNode cur = head;
while (cur != null) {
len++;
// cur最终为空，超出链表
cur = cur.next;
}
return len;
}

• 实现display()​方法

打印链表的每一个值，类似于size()​方法，用遍历方式得到每一个节点的数据域val​

public void display() {
LinkNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}

• 实现addFirst(int data)​方法

在链表的头部插入一个元素，首先创建一个节点node​，数据域存放data​，然后与链表建立连接：node​的next​域指向head​，最后将node​设置为头节点。

public void addFirst(int data) {
LinkNode node = new LinkNode(data);
node.next = head;
head = node;
}

• 实现addLast(int data)​方法

在链表的尾部插入元素，先创建好要插入的节点node​，然后让链表的最后一个节点指向node​，要拿到最后一个节点可以通过遍历链表实现。在正常情况下以上思路没有问题，但是当链表为空时，也就是head == null​时不适用，会出现空指针异常，所以这种情况要单独拎出来直接将node​设置为头节点

public void addLast(int data) {
LinkNode node = new LinkNode(data);
if (head == null) {
head = node;
return;
}
LinkNode cur = head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}

• 实现addIndex(int index, int data)​方法

在指定索引处插入元素。首先判断idex的合法性，如果越界就报错。然后创建好需要插入的节点node​，接着判断索引index​位置，如果index == 0​直接使用头插法调用addFirst()​，如果是在尾部就用尾插法调用addLast()​方法，在中间的话我们就需要把node​节点的next​指向index​位置的节点，将index-1​处的节点的next​指向node​。问题就出在我们要得到index-1​处的节点，因为我们是单向链表，只能得到下一个节点，不能得到上一个节点，所以我们在遍历时只能遍历到index-1​处

public void addIndex(int index, int data) {
int len = size();
if (index > len || index < 0) {
System.out.println("插入位置不合法");
}

LinkNode node = new LinkNode(data);
if (index == 0) {
addFirst(data);
}
if (index == len) {
addLast(data);
}
LinkNode cur = head;
while (index-1 != 0) {
cur = cur.next;
index–;
}
node.next = cur.next;
cur.next = node
}

• 实现contains(int key)​方法

先判断链表是否为空，如果为空直接返回false，不为空则遍历链表，判断每一个值是否为key

public boolean contains(int key) {
if (head == null) {
return false;
}
LinkNode cur = head;
while (cur != null) {
if (key == cur.val) {
return true;
}
cur = cur.next;
}
return false;
}

• 实现remove(int key)​方法

要删除链表中的key​，我们就需要遍历链表。由于我们删除key​节点后需要上一个节点与下一个节点建立链接，但是在单向链表中无法拿到上一个节点，所以我们就不能遍历到key​节点，而是用cur.next​表示当前节点。删除key​节点可以使用cur.next = cur.next.next​的方式。但是这种方式检测不到头节点是否为key，所以检测头节点需要单独处理

public void remove(int key) {
// 如果链表为空不需要删除
if (head == null) {
return;
}
// 删除头节点
if (key == head.val) {
head = head.next;
return;
}
// 删除其余节点
LinkNode cur = head;
while (cur.next != null) {
if (key == cur.next.val) {
cur.next = cur.next.next;
return;
}
cur = cur.next;
}
}

• 实现removeAllKey(int key)​方法

使用双指针，一个走在前面，一个走在后面。如果cur.val​是需要删除的key​，那么就让cur​后移，prev​不动，如果不是则都往后移。

public void removeAllKey(int key) {
if (head == null) {
return;
}
LinkNode prev = head;
LinkNode cur = head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
// 最后判断头节点，如果先判断的话新产生的头节点无法校验
if (key == head.val) {
head = head.next;
}
}

2.2 单向链表的简单应用

​

​

思路：简单的方法就是遍历链表并将值传入数组中，再将数组逆序遍历到新链表中，返回新链表。但如果要求在原链表上进行反转，并且只能遍历一次链表呢？我们可以通过头插法完成，首先定义一个节点cur = head.next​，为什么不是cur = head​呢？因为采用头插法，第一个节点不需要再向前插入。然后将head.next​置为null​，因为当前链表的头节点最终会成为尾节点，尾节点的next​为null​。然后将遍历到的每一个cur​都插入到头部并作为新的头节点cur.next = head​，在此之前为了防止丢失后续节点我们先将后续节点保存curN = cur.next​。之后将cur​作为头节点head​

class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}

ListNode cur = head.next;
head.next = null;
while (cur != null) {
ListNode curN = cur.next;
cur.next = head;
head = cur;
cur = curN;
}
return head;
}
}

​

​

思路：简单的方法是遍历两遍链表，第一遍得到长度size​，第二遍通过size​找到中间节点。但如果要求只能遍历一遍链表呢？我们就需要使用快慢指针法，定义一个满指针slow​，每次走一步，快指针fast​步长为slow​的两倍，每次走两步，当快指针走完了慢指针刚好在中间节点。

class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}

思路：同样如果遍历两遍链表就很简单。所以我们尝试通过遍历一遍链表完成。如果两个指针的距离保持为k-1​，那么当前面一个指针的位置在最后一个节点，那么是不是后面一个指针的位置就在倒数第k​的节点位置呢？换言之，也就是让快指针先走k-1​步，然后再和慢指针一起走，最终快指针到最后一个节点时，慢指针就在倒数第k​个节点。

class Solution {
public int kthToLast(ListNode head, int k) {
if (head == null) {
return -1;
}
ListNode fast = head;
ListNode slow = head;
while(k – 1 != 0) {
fast = fast.next;
k–;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
}

​

​

思路：定义一个新节点newH​作为返回节点，并定义一个cur​作为newH​往后走，循环判断list1.val​与list2.val​的大小，小的接到cur​后面cur.next = min(list1.val, list2.val)​，并且让cur = cur.next​，list1 = list1.next​或list2 = list2.next​,如此循环直到list1​或list2​为空，最后将不为空的接到cur​后面，返回newH.next​

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newH = new ListNode();
ListNode cur = newH;
while (list1 != null && list2 != null) {
if (list1.val > list2.val) {
cur.next = list2;
list2 = list2.next;
cur = cur.next;
} else {
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}
}
if (list1 != null) {
cur.next = list1;
}
if (list2 != null) {
cur.next = list2;
}
return newH.next;
}
}

思路：可以定义两个节点minHead​和maxHead​，遍历原链表，将小于x的节点依次接到minHead后面，大于x的节点依次接到maxHead​后面，最后将maxHead接到minHead​后面，返回minHead​。

public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode minHead = new ListNode(0);
ListNode maxHead = new ListNode(0);

ListNode minCur = minHead;
ListNode maxCur = maxHead;

while (pHead != null) {
if (pHead.val < x) {
minCur.next = pHead;
minCur = minCur.next;
}else {
maxCur.next = pHead;
maxCur = maxCur.next;
}
pHead = pHead.next;
}
maxCur.next = null;
minCur.next = maxHead.next;
return minHead.next;
}
}

思路：额外空间复杂度为O(1)表示需要在原链表上面进行操作，怎么在原链表上判断是否为会问结构呢？我们可以通过快慢指针fast​和slow​找到中间节点，然后通过slow​将中间节点后面的节点全部逆置，这时slow​走到了最后，再通过头节点往后走，slow​往前走，判断slow​和头节点的节点值是否相等，如果相等返回true，不相等返回false，需要注意的是如果节点个数为偶数，需要判断head.next == slow​,如果为true就结束，返回结果。

public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode fast = A;
ListNode slow = A;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

ListNode cur = slow;
while (cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}

while (A != slow) {
if (A.val != slow.val) {
return false;
}
if (A.next == slow) {
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}

​

​

思路：两个链表如果相交的话在相交后的节点是共用的，长度也相同，那么链表的长度差只会产生在相交之前，如果我们得到了两个链表的长度，只需要让长的先走长度差步数，之后一起走，这样就可以同时到达相交节点，我们也就可以得到这个相交节点。

public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while (curA != null) {
lenA++;
curA = curA.next;
}
while (curB != null) {
lenB++;
curB = curB.next;
}
int len = lenA – lenB;
if (len > 0) {
while (len > 0) {
len–;
headA = headA.next;
}
} else {
int lenAbs = Math.abs(len);
while (lenAbs > 0) {
lenAbs–;
headB = headB.next;
}
}
while (headB != null) {
if (headB == headA) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}

​

​

思路：通过快慢指针判断，让快指针fast​一次走两步，慢指针slow​一次走一步，如果相遇就说明有环，不相遇就是没环。

public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}

​

​

思路：通过快慢指针，快指针fast​一次走两步，慢指针slow​一次走一步，如果有环最终就会相遇。假设头节点到入环点的距离为X​，环的长度为C​，相遇点到入环点的距离为Y​，那么在不套环的情况下fast​走的距离就是X+C+(C-Y)​，slow​走的距离就是X+C-Y​，由于fast走的速度是slow的两倍，所以路程也就是两倍，因此得到X+C+(C-Y)=2(X+C-Y)​，化简得到X=Y​，也就是头节点到入环点的距离等于相遇点到入环点的距离。如果出现套圈的情况，也就是fast​在环中走了很多圈才和slow​相遇，也就是X=(N-1)C+Y​。所以不管哪种情况，此时我们将慢指针拉到头节点位置，快指针在相遇点，两者以相同的速度前进，再次相遇的节点就是入环点。

public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast != null && fast.next != null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}

3. 双向链表

双向链表比单向链表多了一个前驱节点prev​，能够得到当前节点的上一个节点，在Java中LinkedList​的实现就是以双向链表的形式实现的。通过头节点first​和尾节点last​进行维护，支持首尾快速操作。查询时间复杂度为O(n)，需要从头节点或者尾节点遍历，删除增加节点时间复杂度为O(1)，定位到节点后直接增删。

3.1 双向链表的模拟实现

• 实现方法

我们还是以这套接口作为实现

public interface IList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
//清除链表
public void clear();
//打印链表
public void display();
}

• 创建节点类

由于是双向链表，所以由数据域val​和指针域next​指向后一个节点，prev​指向前一个节点。

public class MyLinkedList implements IList{

// 节点类
private static class ListNode {
// 数据域
public int val;

// 指针域，指向下一个节点
public ListNode next;

// 指针域，指向上一个节点
public ListNode prev;

// 构造方法
public ListNode (int val) {
this.val = val;
}

// 无参构造方法
public ListNode() {}
}

// 重写方法
@Override
public void addFirst(int data) {

}

@Override
public void addLast(int data) {

}

@Override
public void addIndex(int index, int data) {

}

@Override
public boolean contains(int key) {
return false;
}

@Override
public void remove(int key) {

}

@Override
public void removeAllKey(int key) {

}

@Override
public int size() {
return 0;
}

@Override
public void clear() {

}

@Override
public void display() {

}

}

• 实现addFirst(int data)​方法

首先创建node​节点，判断原链表是否为空，如果为空，直接将收尾节点都设置为node​，如果不为空将node​的下一个节点设为first​，将firs​t的前驱设置为node​，并将node​作为first​

public void addFirst(int data) {
ListNode node = new ListNode(data);
if (first == null) {
first = last = node;
}else {
node.next = first;
first.prev = node;
first = node;
}
}

• 实现addLast(int data)​方法

创建node​节点作为要插入的节点，如果原链表为空，将node​节点作为收尾节点，如果不为空，则将node​作为last​的后驱，将node​前驱设置为first​，并将last​修改为node​

public void addLast(int data) {
ListNode node = new ListNode(data);
if (first == null) {
first = last = node;
} else {
last.next = node;
node.prev = last;
last = node;
}
}

• 实现addIndex(int index, int data)​方法

首先判断index的合法性，如果index小于0或者大于链表长度，则不合法抛出异常，如果index等于0则为头插法，调用addFirst方法，如果index等于链表长度则为尾插法，调用addLast方法。如果为其他位置则将插入位置节点cur的前驱的next域修改为node，node的next域修改为cur，node的prev域修改为cur.prev，最后将cur的prev域修改为node

public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("索引越界：index=" + index + "，size=" + size());
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = first;
while (index != 0) {
cur = cur.next;
index–;
}

ListNode node = new ListNode(data);
cur.prev.next = node;
node.prev = cur.prev;
node.next = cur;
cur.prev = node;
}

• 实现contains(int key)​方法

遍历链表判断是否包含key​，如果有结束遍历返回true​，如果没有返回false​

public boolean contains(int key) {
ListNode cur = first;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}

• 实现remove(int key)​方法

遍历链表，如果出现了key就删掉，但是在不同位置有所不同，如果头节点为key，则将头节点的下一个节点作为头节点，并进一步判断删除后是否为空链表，如果为空，将last节点也置为空，如果不为空，将头节点的前驱prev置为空。如果尾节点为key，则将尾节点的前驱作为尾节点，并将新的尾节点的后驱next置为空。如果是中间节点为key，将目标节点的前驱节点的next域改为目标节点的后驱节点，并将目标节点的后驱节点的prev域改为目标节点的前驱。改完后结束方法。

public void remove(int key) {
ListNode cur = first;
while (cur != null) {
if (cur.val == key) {
if (cur == first) {
first = first.next;
if (first == null) {
last = null;
}else {
first.prev = null;
}
} else if (cur == last) {
last = last.prev;
last.next = null;
} else {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
return;
}
cur = cur.next;
}
}

• 实现removeAllKey(int key)​方法

与remove(int key) 方法大致相同，不同点在于删除完一个之后要继续删除，也就是不结束方法。

public void removeAllKey(int key) {
ListNode cur = first;
while (cur != null) {
if (cur.val == key) {
if (cur == first) {
first = first.next;
if (first != null) {
first.prev = null;
} else {
last = null;
}
} else if (cur == last) {
last = last.prev;
last.next = null;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
cur = cur.next;
}
}

• 实现size()​方法

遍历链表并计数即可

public int size() {
int len = 0;
ListNode cur = first;
while (cur != null) {
len++;
cur = cur.next;
}
return len;
}

• 实现clear()​方法

遍历链表，将每个节点的每个域都置为空

public void clear() {
ListNode cur = first;
while (cur != null) {
ListNode next = cur.next;
cur.prev = null;
cur.next = null;
cur.val = 0;
cur = next;
}
first = last = null;
}

• 实现display()​方法

遍历链表，并打印每个节点值

public void display() {
ListNode cur = first;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}

4. LinkedList的使用

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。在集合框架中LinkedList实现了List接口和Deque接口。

4.1 LinkedList的构造方法

​LinkedList​ 只有 ​2 个核心构造方法​，设计简洁，满足基础初始化需求：

• 无参构造方法

创建一个空的双向链表（初始时 first​ 和 last​ 均为 null​）

public LinkedList()

• 带集合参数的构造方法

创建一个包含指定集合所有元素的 LinkedList​，元素顺序与集合的迭代顺序一致。

public LinkedList(Collection<? extends E> c)

4.2 LinkedList 的常用方法

4.2.1 添加元素方法

4.2.2 删除元素方法

4.2.3 查询 / 获取元素方法

4.2.4 修改元素方法

4.2.5 判断 / 遍历方法

4.2.6 队列 / 栈特有方法（实现 Deque 接口）

LinkedList 常被用作栈或​队列​，这些方法是其核心优势：