数据结构—链表

大家好，欢迎来到IT知识分享网。

1.链表是什么

链表数一种线性数据结构。它是动态地进行储存分配的一种结构。

什么是线性结构，什么是非线性结构？
线性结构是一个有序数据元素的集合。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构，是一个结点元素可能有多个直接前趋和多个直接后继。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。

2.链表的基本结构

链表由一系列节点组成的集合，节点（Node）由数据域（date）和指针域（next）组成。

date负责储存数据，next储存其直接后续的地址

3.链表的分类

• 单链表（特点：连接方向都是单向的，对链表的访问要通过顺序读取从头部开始）
• 双链表

• 循环链表单向循环链表双向循环链表

4.链表和数组的比较

数组：

优点：查询快（地址是连续的）

缺点：1.增删慢，消耗CPU内存

链表就是 一种可以用多少空间就申请多少空间，并且提高增删速度的线性数据结构，但是它地址不是连续的查询慢。

二、单链表

[1. 认识单链表](#1. 认识单链表)

2.引人头结点的作用

3.链表的基本操作

1. 认识单链表

（1）头结点：第0 个节点（虚拟出来的）称为头结点（head），它没有数据，存放着第一个节点的首地址

（2）首节点：第一个节点称为首节点，它存放着第一个有效的数据

（3）中间节点：首节点和接下来的每一个节点都是同一种结构类型：由数据域（date）和指针域（next）组成

• 数据域（date）存放着实际的数据，如学号（id）、姓名（name）、性别（sex）、年龄（age）、成绩（score）等
• 指针域（next）存放着下一个节点的首地址

（4）尾节点：最后一个节点称为尾节点，它存放着最后一个有效的数据

（5）头指针：指向头结点的指针

（6）尾指针：指向尾节点的指针

（7）单链表节点的定义

 public static class Node { //Object类对象可以接收一切数据类型解决了数据统一问题 public Object date; //每个节点的数据 Node next; //每个节点指向下一结点的连接 public Node(Object date) { this.date = date; } } 

2.引人头结点的作用

1. 概念
2. 头结点：虚拟出来的一个节点，不保存数据。头结点的next指针指向首节点。头结点不是链表所必须的。
3. 头指针：指向链表第一个节点的指针。头指针是链表所必须的
4. 注：头指针始终指向链表的第一个节点。 对于引入头结点的链表：头指针指向头结点；对于没有引入头结点的链表：头指针指向首节点。
5. 为什么要引入头结点

（1）对链表的删除、插入操作时，第一个节点的操作更方便

如果没有头结点，头指针指向链表的首节点，在首节点前插入一个新的节点时，头指针要相应地指向新插入的节点。把首节点删除时，头结点的指向也要更新。

如果没有头结点，那我们在对首节点进行操作时，要一直维护着头结点指向的更新。

如果引入了头结点，头指针始终指向头结点。头结点的next指针始终指向首节点

​ （2）统一空表和非空表的处理

引入头指针后，头指针指向头结点，无论链表是否为空，头指针均不为空。

3.链表的基本操作

（1）增加节点

在链表后增加节点

思路：

• 产生一个新的节点 newNode
• 对链表进行遍历操作，找到当前链表的最后一个节点 last
• 当前链表的最后一个节点的下一个节点 = 新的节点 last.next = newNode

public Object add(Object obj){ //产生一个新的节点 Node newNode = new Node(obj); //如果没有任何节点存在（第一个节点） if (size == 0){ head = newNode; last = newNode; }else { //如果不是第一个节点 last.next = newNode; last = newNode; } size++; return obj; } 

（2）插入结点

思路：

在指定位置插入新节点 nodeIndex ，新节点的前一个结点 current

• 遍历到需要插入新节点 nodeIndex 的位置
• 当找到该位置时，新插入的结点下一结点 = 前一个结点的下一结点 nodeIndex.next = current.next
• 前一个结点的下一结点 = 新插入的结点 current.next = nodeIndex

 public void addIndex(int index,double n){ Node current = head; while (current != null){ if (current.date.equals(index)){ //产生一个新节点 Node nodeIndex = new Node(n); nodeIndex.next = current.next; current.next = nodeIndex; size++; } current = current.next; } } 

（3）删除结点

思路：

• 定义一个需要删除的结点 deleteNode
• 找到需要删除的结点的前一个结点 previous
• 前一个结点 的下一个节点 = 需要删除的结点 的下一个节点 previous.next = deleteNode.next

 public boolean delete(Object value){ //链表为空 if (size == 0){ return false; } Node deleteNode = head; //要删除的结点 Node previous = head; //要删除的结点前一个结点 //没找到要删除的结点 while(deleteNode.date!= value){ if(deleteNode.next == null){ return false; }else{ previous = deleteNode; deleteNode = deleteNode.next; } } //如果要删除的是首节点 if (deleteNode.date == head.date){ head = head.next; size--; }else { //如果要删除的是首节点之后的结点 previous.next = deleteNode.next; size--; } return true; } 

（4）查找结点

思路：

• 因为头结点不能动，定义一个当前节点 current，从头结点开始遍历
• 找到该节点返回 current ，找不到返回 null

 public Node find(Object obj){ Node current = head; int tempSize = size; while (tempSize > 0){ if (obj.equals(current.date)){ return current; }else { current = current.next; } tempSize--; } return null; } 

（5）修改结点

思路：

修改指定节点的数据

• 遍历到需要修改的结点
• 将节点数据进行替换

 public void update(int map , int n){ if (size == 0){ System.out.println("链表为空"); return; } Node current = head; for (int i = 1; i < map; i++) { if (current.next == null){ System.out.println("该节点不存在"); break; } current = current.next; if (i == map -1){ current.date = n; } } } 

5.设计链表：源代码（含测试用例）

public class LinkedList { private int size; //链表节点的个数 private Node head; //头结点 private Node last; //当前链表的最后一个节点 public LinkedList(){ size = 0; head = null; } //链表的每个节点类 public static class Node { //Object类对象可以接收一切数据类型解决了数据统一问题 public Object date; //每个节点的数据 Node next; //每个节点指向下一结点的引用 public Node(Object date) { this.date = date; } } //在链表后添加元素 public Object add(Object obj){ //产生一个新的节点 Node newNode = new Node(obj); //如果没有任何节点存在（第一个节点） if (size == 0){ head = newNode; last = newNode; }else { //如果不是第一个节点 last.next = newNode; last = newNode; } size++; return obj; } //插入结点 public void addIndex(int index,double n){ Node current = head; while (current != null){ if (current.date.equals(index)){ //产生一个新节点 Node nodeIndex = new Node(n); nodeIndex.next = current.next; current.next = nodeIndex; size++; } current = current.next; } } //删除（指定元素删除节点） public boolean delete(Object value){ //链表为空 if (size == 0){ return false; } Node deleteNode = head; //要删除的结点 Node previous = head; //要删除的结点前一个结点 //没找到要删除的结点 while(deleteNode.date!= value){ if(deleteNode.next == null){ return false; }else{ previous = deleteNode; deleteNode = deleteNode.next; } } //如果要删除的是首节点 if (deleteNode.date == head.date){ head = head.next; size--; }else { //如果要删除的是首节点之后的结点 previous.next = deleteNode.next; size--; } return true; } //查找指定元素的结点 public Node find(Object obj){ Node current = head; int tempSize = size; while (tempSize > 0){ if (obj.equals(current.date)){ return current; }else { current = current.next; } tempSize--; } return null; } //修改 public void update(int map , int n){ if (size == 0){ System.out.println("链表为空"); return; } Node current = head; for (int i = 1; i < map; i++) { if (current.next == null){ System.out.println("该节点不存在"); break; } current = current.next; if (i == map -1){ current.date = n; } } } //显示节点信息 public void display(){ if (size > 0){ Node node = head; int tempSize = size; while (tempSize > 0){ System.out.print(node.date+" "); node = node.next; tempSize--; } }else { System.out.println("链表为空"); } System.out.println(); } } 

测试用例

import javax.xml.soap.Node; public class Application { public static void main(String[] args) { LinkedList list = new LinkedList(); System.out.println("在链表后添加节点:" ); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.add(8); list.add(9); list.add(10); list.display(); System.out.println("删除第四个节点:" ); list.delete(4); list.display(); System.out.println("查找数据是3的结点:" ); LinkedList.Node nodefind = list.find(3); System.out.println(nodefind.date); System.out.println("在第三节点后面增加一个节点:" ); list.addIndex(3,4); list.display(); System.out.println("把第四个节点的4.0该成0:"); list.update(4,0); list.display(); } } 

运行结果

三、双链表

1.认识双链表

2.双链表结点结构的定义

3.双链表的基本操作

1.认识双链表

双链表的每个数据节点中都有两个指针，分别前驱指针域和后继指针域。

2.双链表结点结构的定义

双向链表中每个节点包含两个节点的指针引用，和一个数据域

 public static class Node{ private Object date; private Node next; //指向下一结点的引用 private Node prev; //指向前一结点的引用 public Node(Object date){ this.date = date; } } 

3.双链表的基本操作

插入结点图解

代码实现

package DLinkendList; public class LinkedList { public static class Node{ private Object date; private Node next; //指向下一结点的引用 private Node prev; //指向前一结点的引用 public Node(Object date){ this.date = date; } } private Node head; //头结点 private Node tail; //尾节点 private Node curr; //临时结点，用作指针节点 private int size; //链表节点数 public void LinkedList(){ head = new Node(null); tail = head; size = 0; } //判断链表是否为空 public boolean isEmpty(){ return size == 0; } //在链表尾部添加节点 public void add(Object obj){ if (isEmpty()){ //链表为空，添加第一个新节点 head = new Node(obj); tail = head; size++; }else { curr = new Node(obj); curr.prev = tail; tail.next = curr; //将新结点与原来的尾部结点连接 tail = curr; //curr变成最后一个节点 size++; } } //插入结点 public void addIndex(int index,int value){ curr = head; while (curr != null){ if (curr.date.equals(index)){ Node nodeIndex = new Node(value); nodeIndex.prev = curr; nodeIndex.next = curr.next; curr.next = nodeIndex; if (nodeIndex.next == null){ tail = nodeIndex; } size++; } curr = curr.next; } } //删除指定元素的结点 public boolean delete(Object value){ curr = head; //链表为空 if (size == 0){ return false; } //没找到要删除的结点 while(curr.date!= value){ if(curr.next == null){ return false; }else{ curr.prev = curr; curr = curr.next; } } //如果要删除的是首节点 if (curr.date == head.date){ head = head.next; size--; }else { //如果要删除的是首节点之后的结点 curr.prev.next = curr.next; size--; } return true; } //打印链表 public void display(){ curr = head; for (int i = 0; i < size; i++) { System.out.print(curr.date + " "); curr = curr.next; } System.out.println(); } } 

测试链表

public class Application { public static void main(String[] args) { LinkedList list = new LinkedList(); System.out.println("在链表后添加节点:" ); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.add(8); list.add(9); list.add(10); list.display(); System.out.println("在5后面加一个6:" ); list.addIndex(5,6); list.display(); System.out.println("删除元素6" ); list.delet(6); list.display(); } } 

运行结果

四、双指针

1.双端链表的实现

2.环形链表

3.判断链表中是否有环

4.相交链表

5.删除倒数第N个节点

对于单链表，如果我们想在尾部添加一个节点，就必须从首节点开始遍历到尾节点，

然后在尾结点后面插入一个节点。为了方便操作，可以在设计链表的时候多一个对尾结点的引用。

双指针和双链表的区别

1.双端链表的实现

package DoublePointLinkedList; public class LinkedList { private Node head; //头结点 private Node tail; //尾节点 private int size ; //节点个数 private static class Node{ private Object date; private Node next; public Node(Object date){ this.date = date; } } public LinkedList(){ head = null; tail = null; size = 0; } //增加节点(表尾) public void addTail(Object obj){ Node newNode = new Node(obj); if (size == 0){ head = newNode; tail = newNode; size++; }else { tail.next = newNode; tail = newNode; size++; } } //增加节点(表头) public void addHead(Object obj){ Node node = new Node(obj); if (size == 0){ head = node; tail = node; size++; }else { node.next = head; head = node; size++; } } //删除首结点 public boolean deleteHead(){ if (size == 0){ return false; } if (head.next == null){ head = null; tail = null; }else { head = head.next; } size--; return true; } //显示链表 public void display(){ Node node = head; for (int i = 0; i < size; i++) { System.out.print(node.date + " "); node = node.next; } System.out.println(); } } 

双端链表测试

package DoublePointLinkedList; public class Application { public static void main(String[] args) { LinkedList list = new LinkedList(); System.out.println("在表尾添加节点:"); list.addTail(1); list.addTail(2); list.addTail(3); list.addTail(4); list.addTail(5); list.addTail(6); list.addTail(7); list.display(); System.out.println("在表头添加一个节点数据为0:"); list.addHead(0); list.display(); System.out.println("删除第一个结点:"); list.deleteHead(); list.display(); } } 

运行结果

2.环形链表

（1）环形链表就是循环链表的意思。循环链表没有专门的头结点，链表尾结点的指针域不指向null，而是指向链表的其他结点

（2）循环链表的实现

创建一个节点类Node

package CircularLinkendList; public class Node { private int data; private Node next; public Node(int data){ this.data = data; } public int getData() { return data; } public Node getNext() { return next; } public void setData(int data) { this.data = data; } public void setNext(Node next) { this.next = next; } } 

写一个循环链表添加节点的方法

思路：

（1）链表为空的时候，插入第一个节点

那插入的这个节点是第一个节点也是最后一个节点

也就是这个节点的next指向自己的地址

（2）插入第二个节点

实例化一个辅助指针 currentNode ，让这个辅助指针指向第一个节点的地址

让辅助指针 currentNode 的 next 指向新的节点 newNode （currentNode.next = newNode）

（3）把链表“环”起来

再实例化一个辅助指针 first ，这个辅助指针也指向第一个节点的地址

让新节点 newNode 的next指向第一个节点，也就是指向first（newNode.next = first）

思路清晰之后上代码

创建一个链表类

package CircularLinkendList; public class LinkendList { private Node first = null; private Node currentNone = null; public void add(int value){ for (int i = 1; i <= value; i++) { Node newNode = new Node(i); if (first == null){ first = newNode; first.setNext(first); currentNone = first; }else { currentNone.setNext(newNode); newNode.setNext(first); currentNone = currentNone.getNext(); } } } //显示链表 public void display(){ Node node = first; if (node == null){ System.out.println("链表为空"); return; }do { System.out.print(node.getData() + " "); node = node.getNext(); }while (node != first); System.out.println(); } } 

测试

package CircularLinkendList; public class Application { public static void main(String[] args) { LinkendList list = new LinkendList(); list.add(5); list.display(); } } 

运行结果

3.判断链表中是否有环

详解参见https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/

问题描述
给定一个链表，判断链表中是否有环

如果存在环，则返回true， 否则返回 false

为了给定链表中的环，用整数 pos 来表示；链表尾连接到链表中的位置（索引从0 开始），如果 pos 是 -1 ，则在该链表中没有环（ pos 是为了标识链表的实际情况）。

示例1：

输入：head = [3 , 2 , 0 , 4] , pos = 1; 输出：ture 解释：链表中有一个环，其尾部连接到第二个节点 

示例2：

输入：head = [1 , 2] , pos = 0; 输出：ture 解释：链表中有一个环，其尾部连接到第一个节点 

示例3：

输入：head = [1] , pos = -1; 输出：false 解释：链表中没有环 

代码实现

 public boolean hasLoop(Node node){ //定义一个快指针一个慢指针 Node slow = node; Node fast = node.next; while (fast != null){ if (slow.data == fast.data){ //当两个指针重逢时，则存在环，否则不存在 return true; } slow = slow.next; //每次迭代慢指针走一步 fast = fast.next.next; //快指针走二步 if (fast == null){ return false; } } return true; //只有一个元素也存在环 } 

测试

public class Application { public static void main(String[] args) { LinkendList list = new LinkendList(); Node node1 = new Node(3); Node node2 = new Node(2); Node node3 = new Node(0); Node node4 = new Node(4); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node2;//构造一个带环的链表（和 pos = 1 差不多意思） System.out.println(list.hasLoop(node2)); } } 

运行结果

4.相交链表

问题描述

给两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 

示例2：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。 

思路：

下面我们来分析示例1：

1. 指针 NodeA 指向链表 ListA ，指针 Node 指向链表 ListA ， 依次往后遍历

2. NodeA 遍历到 ListA 的末尾，则 NodeA = headB 继续遍历
   
3. NodeB 遍历到 ListB 的末尾，则 NodeB = headA 继续遍历

4. 此时两链表的长度差就没有了
5. 继续往下遍历就能得到结果了

代码来源https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/

 public LinkedList check(LinkedList headA, LinkedList headB) { if (headA == null || headB == null) return null; LinkedList nodeA = headA; LinkedList nodeB = headB; while (nodeA != nodeB) { nodeA = nodeA == null ? headB : nodeA.next; nodeB = nodeB == null ? headA : nodeB.next; } return nodeA; } 

5.删除倒数第N个节点

问题描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 

示例1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 

示例2：

输入：head = [1], n = 1 输出：[] 输入：head = [1,2], n = 1 输出：[1] 

思路：

• 设前指针 start ，后指针 end ，两个指针都指向 head

• 移动 start ，使start 和 end 相距 n
• start 和 end 同时先前移动，直到 start 指向 null，此时 end 的位置恰好是倒数第 n 个节点的前一个结点
• end 的 next 指向 下一个节点的 next的 next （end.next = end.next.next）

代码实现

public class deleteNLinkedList { public ListNode removeNthFromEnd(ListNode head,int n){ ListNode pre = new ListNode(0); //pre:虚拟指针 pre.next = head; ListNode start = pre; ListNode end = pre; while (n != 0){ // start 先走 n 步 start = start.next; n--; } while (start.next != null){ //start 和 end 相距 n 时一起移动 start = start.next; end = end.next; } end.next = end.next.next; //删除第倒数第 n 个节点 return pre.next; } } 

五、经典问题—反转链表

问题描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 

示例

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 

思路

将当前节点的 \textit{next}next 指针改为指向前一个节点

代码实现

public class LinkendList { public Node reverse(Node head){ Node prev = null;​ Node curr = head;​ while (curr != null){ Node tempNode = curr.next; curr.next = prev; prev = curr; curr = tempNode; } return prev; } } 

运行结果