链表
目录
一、概述
1.链表是什么
链表数一种线性数据结构。它是动态地进行储存分配的一种结构。
什么是线性结构，什么是非线性结构？
线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构，是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。
2.链表的基本结构
链表由一系列节点组成的集合，节点（Node）由数据域（date）和指针域（next）组成。
date负责储存数据，next储存其直接后续的地址
3.链表的分类
-
单链表（特点：连接方向都是单向的，对链表的访问要通过顺序读取从头部开始）
-
双链表
- 循环链表
- 单向循环链表
- 双向循环链表
4.链表和数组的比较
数组：
优点：查询快（地址是连续的）
缺点：1.增删慢，消耗CPU内存
链表就是 一种可以用多少空间就申请多少空间，并且提高增删速度的线性数据结构，但是它地址不是连续的查询慢。
二、单链表
[1. 认识单链表](#1. 认识单链表)
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.引人头结点的作用
-
概念
头结点：虚拟出来的一个节点，不保存数据。头结点的next指针指向首节点。头结点不是链表所必须的。
头指针：指向链表第一个节点的指针。头指针是链表所必须的
注：头指针始终指向链表的第一个节点。 对于引入头结点的链表：头指针指向头结点；对于没有引入头结点的链表：头指针指向首节点。
-
为什么要引入头结点
? （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.双链表结点结构的定义
双向链表中每个节点包含两个节点的指针引用，和一个数据域
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.双端链表的实现
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.判断链表中是否有环
问题描述
给定一个链表，判断链表中是否有环
如果存在环，则返回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：
- 指针 NodeA 指向链表 ListA ，指针 Node 指向链表 ListA ， 依次往后遍历
-
NodeA 遍历到 ListA 的末尾，则 NodeA = headB 继续遍历
-
NodeB 遍历到 ListB 的末尾，则 NodeB = headA 继续遍历
- 此时两链表的长度差就没有了
- 继续往下遍历就能得到结果了
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;
}
}
运行结果
了解单链表https://www.bilibili.com/video/BV16K4y1N7WL
思路https://blog.csdn.net/weixin_43265151/article/details/104659700