chapter_array_and_linkedlist/linked_list/

[giscus[bot]]

chapter_array_and_linkedlist/linked_list/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_array_and_linkedlist/linked_list/

[Blackcat308]

请教k大，在fig.链表定义与存储方式图中，浅蓝色的存储结点指针是占用一块内存地址吗？还是和结点值各占一半呢？谢谢解答。

[krahets]

哈喽，非常好的问题！文中只是一个示意图，只是定性表示，没有定量。如果考虑定量的话，需要分情况：

• 不同类型的结点值占用的空间是不同的，比如 int, long, double, 或者是类的实例等等。
• 指针变量占用的内存空间大小根据所使用的操作系统及编译环境而定，大多为 8 字节或 4 字节。

[whh13345]

请教k大！在看图Fig. 链表定义与存储方式和下面的代码时，感觉有些奇怪，这两个描述的是不是不是一个层面，在java中一切都是对象，那绿色的值的节点存的也是指针吧，那他们一个是内存层面一个是代码层面，不是一个层面的数据结构为什么能直接运用到java的对象中呢？

[krahets]

抱歉，没有太看懂你的问题。可以再组织描述一下吗？

[ZhenhongDu]

k神链表常用操作里，“输出结点在链表中的索引”，代码都是return -1, 是不是应该return index?

[ZhenhongDu]

sorry，我看明白了，其实是我没看清楚，应该没问题, 😅

[KKStudyCoding]

没找到表示返回-1，返回一个负数。如果返回index，已知index最小为0，就算返回为0也表示找到了，在第一个结点中。

[iLoveRatRace]

链表访问节点处的代码的for循环中，先令 head = head.next 再判断 head 是否为空，请问一下先判断head.next 是否为空，若为空则返回 null ；不为空再令 head = head.next 会不会好一点点。

[iLoveRatRace]

删除节点 n0 后的首个节点的代码中ListNode P = n0.next; ListNode n1 = P.next; n0.next = n1; 此处是否可以简化为 n0.next = n0.next.next；

[krahets]

谢谢已统一。

可以这样简化，但为了提升可读性，本书把结点 P 显式地写出来了。

[WenlongDai]

想问一下 链表的插入和删除确实是O(1) 但是查找既然是需要遍历。那应该是O(n)不是么？

[ZZhenF]

是的，只做一次插入和删除操作时间复杂度是O（n），一般来说链表插入删除操作讨论的是大量插入和删除数据

[krahets]

对，补充楼上：如果是先查找元素、再删除元素，那么是 $O(n)$ 。但是这种只是一种特例，链表的 O(1) 插入与删除在其他应用上可以得到体现，比如「双向队列」适合使用链表实现，有指针（变量）始终指向头结点、尾结点，每次插入、删除都是 O(1) 。

[pleomax0730]

刪除結點後，是不是把 P.next 設為 None比較好呢？
我是看Python代碼，目前的代碼的鏈表結果會變成 P也同時指向n1
n0 -> n1
P -> n1

[Reanon]

引用计数就是其他的节点是否有引用它。一个节点没有被任何其他节点引用，那么它就是一个无引用的对象，所以就算 p->next 不为nil，也是会被 gc 的

[zrcoder]

@krahets @Reanon 问得好。 仔细梳理起来是这样的： p 的 next 指针还指向一个节点 x， 试想经过一段时间，x 节点没有被其他任何指针引用了，实际上运行时在gc时应该回收 x，但是，因为我们在删除 p 的时候，忽略了p的next指针指向x，x 就不会被回收 —— 当然需要追溯，gc 要看 p 是否回收，p 回收后会继续回收x，但当前（在删节点这个函数里）我们是不知道 p 是否还被其他节点引用的，健壮的做法就是及时断开p和x的链接。

@Reanon 垃圾回收的方式不止是引用计数，另有标记清除、分代回收等。Go 是标记清除法。

[zrcoder]

可以看看Go标准库 container/list 的实现，比如其删节点函数是这样：

// remove removes e from its list, decrements l.len
func (l *List) remove(e *Element) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
}

这是个双向链表，可以看到把 e 的前驱和后继指针都置为空了，且特意注释了这么做的理由。

[krahets]

@zrcoder 我们应该明确一下问题，讨论的是节点 p 的内存回收是否会受到 p.next 的影响。假设是一个逻辑清晰的链表，那么 p.next 的值不会影响到节点 p 的内存回收。

如果想要讨论 p.next 是否会影响后继节点的内存回收，这是另一个问题。你提到“我们是不知道 P 是否还被其他节点引用”，那可能性有两种：

第一种情况：程序中仍然长时间存在对 P 的引用，那么这将可能导致 A 不能被垃圾收集器回收，因为它们在理论上仍然是可达的。这种情况下，P.next = null 有助于防止内存泄漏。

第二种情况：给定的不是一个单链表。这种情况下，需要 case by case 地考虑。

假设有两个节点都指向 P ，那么实际上有两条链表，并且是“相交链表”，它俩拥有共同的尾部。记这两条链表为 A 和 B ，任务是从链表 A 中删除节点 P 。

如果我们执行了 P.next = null ，会导致节点 P 从链表 B 中也被删除了，而这并不是我们想要的结果。 也就是说，在这个案例中，我们不应该执行 P.next = null ，因为我们不希望在对链表 A 的操作中影响到链表 B 。

从工程角度看，由于庞大项目的复杂性，P.next = null 有助于防止内存泄漏，并且可以加速内存回收。从数据结构角度看，在一条单链表中 P.next = null 不是必须的；而在相交链表或图等复杂数据结构中，需要 case by case 地看，以达到我们想要的结果。只要程序逻辑正确，节点对象都可以被正常回收。

[zrcoder]

@krahets 赞，说得非常清楚。

[akppx]

Fig. 在链表中插入与删除结点示意图中，插入操作示例 节点P的插入顺序错了，应该是
1、P.next = n1
2、n0.next = P

[akppx]

代码是对的，先把 n0.next 保存起来了。按照链表的特性，修改了 n0.next 后就找不到 n1 了，所以示意图这样的表示顺序就不对了吧。

[krahets]

明白了。示意图里的 n1 是一个变量，即代码里的 n1 哈。第一步代表已知（即已暂存） n0 和 n1

[akppx]

哦哦，明白。但我还是觉得示意图有问题，应该先连 P 和 n1 之间的这根线，然后再断开 n0 和 n1 之间的线，最后再连接 n0 和 P ，觉得现在的这个容易造成误解。

[krahets]

谢谢建议！

[sample214]

想问一下github里，主函数里面为什么没有链表的定义，只有链表初始化？谢谢

[krahets]

Hi 链表结点的定义可以在 codes/java/include/ListNode.java 中找到，本项目将公共模块统一设计为 module

[HNUIsak]

在链表插入操作中，请问一下可以写成这段代码吗：

void Insert(ListNode* n0, ListNode* p)
{
    p->next = n0->next;
    n0->next = p;
}

[krahets]

没问题，实际上一般就是这么写～本文把 P 显式地写出来，便于理解。

[HNUIsak]

嗯嗯感谢您的解答！！

[ZhenhongDu]

k神请教一个问题，python里的链表的定义比较好理解，定义了一个ListNode类，这个类有两个属性，一个是存储的值，另一个是指向下一个数据的地址。

class ListNode:
    def __init__(self, x):
        self.val = x      # 结点值
        self.next = None  # 指向下一结点的指针（引用）

但是c++的这个结构体的定义看着我有点迷糊。
如果定义一个结构体指针，我的理解应该是 struct ListNode *next;, 为什么LeetCode上和k神的实现都没有struct关键字呢？

/* 链表结点结构体 */
struct ListNode {
    int val;         // 结点值
    ListNode *next;  // 指向下一结点的指针（引用）
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

[ZhenhongDu]

我明白了，感谢chatgpt! 原因是struct中的成员默认的访问权限是public的。在结构体中，可以直接访问结构体内部的成员变量，包括指针类型的成员变量，所以定义的时候可以省略struct关键字。而class的定义里，成员变量的默认的访问权限是private; 希望可以帮助同样有疑惑的同学。

[krahets]

Hi 不好意思昨天这条消息漏回了…… 你说的对，在 C++ 的 class 里成员变量默认 private ，如果用 class 写成这样就可以

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

看你的问题，感觉你想问的不是 private 和 public 的区别，而是要不要加 struct ？那是不用加的，因为那是在初始化一个变量。

另外，在 c++/c/go 中，我们一般使用 struct 结构体来声明实体类。

[JocyeI]

K神，vx或qq群吗

[krahets]

@Walhalla-Summary 有的，加我 WeChat krahets-jyd

[yizhiteamo]

好清晰的说明，要是当时学数构有这边书就好了。(•̀ω•́ 」∠)

[JocyeI]

经典，膜拜的第n遍，每次阅读都有不一样的收获，对于我这种似懂非懂算法的小白来说。非常nice的开源项目~

[krahets]

谢谢鼓励！如果可以的话加我微信 krahets-jyd ，想请你谈谈阅读感受、提提意见！

[CuiKing1270]

看这个之前自己也买了本书，最终发现还是作者讲得好啊。让我从原理明白了数据结构的魅力

[F9rozen]

可以添加一些链表的常见应用

单向链表

单向链表是一种常见的链表结构，每个节点包含一个指向下一个节点的指针。

1. 资源管理：单向链表可以用来管理资源，例如内存分配中的空闲块链表，通过将空闲的内存块连接成一个链表，可以方便地进行分配和释放。
2. 队列实现：单向链表可以用于实现队列（FIFO）的数据结构，通过在链表的尾部添加元素，并在链表的头部移除元素，可以实现高效的入队和出队操作。
3. 图的表示：在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。单向链表可以用于表示有向图或无向图中顶点的邻居关系。
4. 任务调度：在任务调度系统中，可以使用单向链表来管理待执行的任务列表，通过将任务连接成一个链表，可以按照特定的顺序进行调度和执行。
5. 多级反馈队列调度算法：多级反馈队列调度算法中，任务被分成多个优先级队列，并按照一定规则进行调度。每个队列可以使用单向链表来管理任务，实现按优先级进行任务调度。
6. 符号表和字典实现：在符号表和字典的实现中，可以使用单向链表来存储键值对。每个节点包含一个键和一个值，并通过指针连接成一个链表，实现高效的查找、插入和删除操作。

环形链表

首尾相接的链表结构，

1. 约瑟夫问题（Josephus Problem）：在约瑟夫问题中，有n个人围成一个环形，每次从指定位置开始计数，并按照固定规则将当前位置的人移出环形，直到最后只剩下一个人。环形链表可以用来模拟和解决这个问题。
2. 循环队列（Circular Queue）：循环队列是一种特殊的队列数据结构，当队列的尾部达到数组的末尾时，可以绕回数组的开头，形成一个循环。环形链表可以用来实现循环队列，提供高效的队列操作。
3. 循环链表遍历：使用环形链表可以实现循环遍历，即从任意节点开始遍历整个链表，而不会出现遍历到尾节点后的终止条件。
4. 环形缓冲区（Circular Buffer）：环形缓冲区是一种常见的数据结构，用于在固定大小的缓冲区中循环存储数据。环形链表可以用来实现环形缓冲区，实现高效的数据读写操作。
5. 快慢指针算法（Floyd's Cycle Detection Algorithm）：快慢指针算法是一种使用两个指针在环形链表中寻找环的算法。该算法可以应用于检测环形链表中是否存在环以及找到环的起始节点等问题。

双向链表

双向链表是一种链表结构，每个节点都包含指向前一个节点和后一个节点的指针。

1. LRU缓存（Least Recently Used Cache）：LRU缓存是一种常见的缓存替换策略，其中最近最少使用的数据被淘汰。双向链表可以用来实现LRU缓存，每次访问数据时，将其移到链表的头部，这样尾部的节点就是最近最少使用的数据，可以方便地淘汰。
2. 双向队列（Deque）：双向队列是一种具有队列和栈的特性的数据结构，可以在队列的头部和尾部进行插入和删除操作。双向链表可以用来实现双向队列，提供高效的插入和删除操作。
3. 图的表示：在图的表示中，每个顶点通常包含一个指向其邻居顶点的链表。双向链表可以用于表示有向图或无向图中顶点的邻居关系，每个顶点可以同时保存指向前一个邻居和后一个邻居的指针。
4. 浏览器历史记录：在浏览器中，双向链表可以用来实现浏览器的历史记录功能。每次访问一个新的页面，将其添加到链表的尾部，可以方便地实现前进和后退功能。
5. 文本编辑器的撤销和重做操作：在文本编辑器中，双向链表可以用来实现撤销和重做操作。每次编辑操作都可以将编辑内容添加到链表的尾部，可以通过向前或向后遍历链表来实现撤销和重做操作。
6. 音乐播放器的播放列表：在音乐播放器中，双向链表可以用来实现播放列表，每个节点表示一个音乐文件，可以方便地在当前歌曲的前后插入或删除歌曲。

[SihanMA]

牛啊, 结合应用感觉理解更深刻了

[longsizhuo]

谢谢大佬

[riiyn]

大佬，请教一下，删除链表元素P的时候，N0指向N1就可以了，但是P还是指向的N1，那P最终是被GC回收了吗

[krahets]

是的，由于已经没有任何变量引用 P ，因此 P 会被 GC 回收

[lzhlrcoding]

def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
n1 = n0.next
P.next = n1
n0.next = P
在插入节点中，n1 = n0.next这句应该是多余的吧，写这句没有必要啊。请大佬指点指点。

[qiuxiran]

n1=n0.next代码的含义是把n0下一节点的值赋值给n1节点，显然，n0下一节点为P

[zhuiguang49]

不要这一句也可以的

P.next = n0.next
n0.next = P

[cyone123]

不是多余的。你估计是没搞清楚，这个函数的功能是在任意节点后插入，不只是在第一个节点后插入。

[kadashu]

我看书的时候也有这个疑问，直接改写成以下两行，也是等价的

def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
    P.next = n0.next
    n0.next = P

[DreamboatQ]

其实不是多余的。其实在这个函数中，只有n0和p可以用。就是说如果不说明n1=n0.next，那么下一行p.next=n1中，p.next就找不到n1这个值，也就不能实现p指向n1的操作了，所以要先申明链表中的关系，再来进行添加或删除的操作。

[TheFayyrr]

/* 链表节点结构体 */
struct ListNode {
int val; // 节点值
ListNode *next; // 指向下一节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
这个构造函数是怎么理解的？看不明白求教大佬

[halfpoundJ]

可以理解为它把两部操作写在一起了
ListNode(int x) {
val = x;
next = nullptr;
}

[TheFayyrr]

谢谢 明白了 构造函数 是定义了一个指针变量？，他的值是val括号里的x,指向是next中括号里的值？

[null1024-ws]

x, nullptr是用来分别初始化val, next的：将传入的x赋值给val，把成员变量 next 初始化为 nullptr。用的时候可以这样：ListNode node(10); 这里的10 会作为参数传入赋值给val，你可以进行打印操作：std::cout << "val: " << node.val << std::endl;

[TheFayyrr]

非常感谢，虽然这本书 都说好，我是能看明白原理，但是，一点都不会写代码，唉 上愁

[ZhongGuanbin]

来信获悉，感谢您的支持！耑此奉复 钟冠彬This is an automatic reply, confirming that your e-mail was received.Thank you

[iLoveRatRace]

感谢来信，你的邮件已经收到。

[ginitaimeiyty]

int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) { 
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

int find(ListNode *head,int target){
	for(int i=0;;i++){
		if(head->next==nullptr||head==nullptr){
			return -1;
			break;
		}
		else if(head->val==target)
		{	
			return i;
			break;
		}
		head=head->next;
	}
}

我有一个问题：就是这两段代码都能实现相同的功能，而且时间复杂度都是O（n），假如考试的时候刚好考到这个算法，那这两段代码谁得的分最高？还是说都是满分？

[Kruogu]

下面for循环不像人写的，，，这用法太妖娆了，正常人不会这么写

[ginitaimeiyty]

哈哈哈哈哈我是正常人，我写程序就是这样容易把自己都绕迷糊

[SlotSun]

我个人经验，类似栈、队列、链表这类结果导向且无法初始确定长度的算法建议用while
有边界限制的用for

[TheFayyrr]

class ListNode:
"""链表节点类"""
def init(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向下一节点的引用，
请问一下，后面两行,包括括号里为什么要冒号呢“：”，我不太理解
要是我自己写，可能会写： self.val=val
self.next =listnode,

[null1024-ws]

补充一下Python的基本语法吧

[TheFayyrr]

OK 谢谢大佬再一次回复我幼稚的问题

[Carmi-mi]

我在做题的时候遇到了一个问题：为什么同一个测试用例，在运行的时候能通过，而提交的时候却显示解答错误？感觉不像是时间/空间方面的限制。（题目是leetcode的https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=selected-coding-interview）

struct Node* copyRandomList(struct Node* head) {
    struct Node* newNode(int val);

	struct Node *copyhead,*copy,*cur,*dum;
    copy=(struct Node*)malloc(sizeof(struct Node));
    copyhead=copy;
    
    cur=(struct Node*)malloc(sizeof(struct Node));
    dum=cur;
    cur->next=head;
    cur=cur->next;

    while(cur!=NULL){ 
        copy->next=newNode(cur->val);
        copy=copy->next;
        cur=cur->next;
    }
    copy->next=NULL;
        
    copy=copyhead->next;
    cur=dum->next;

    while(cur!=NULL){
        if(cur->random == NULL)copy->random=NULL;
        else copy->random=copyhead->next+(cur->random - dum->next);
        cur=cur->next;
        copy=copy->next;
    }

    return copyhead->next;
}

struct Node* newNode(int val){
    struct Node *copy;
    copy=(struct Node*)malloc(sizeof(struct Node));
    copy->val=val;
    return copy;
}

[ZhongGuanbin]

来信获悉，感谢您的支持！耑此奉复 钟冠彬This is an automatic reply, confirming that your e-mail was received.Thank you

[iLoveRatRace]

感谢来信，你的邮件已经收到。

[SuperZhangRui]

时间有限， 简单写一个。。。。。。

package com.rui;

import java.util.LinkedList;

//自己实现一个单向链表 含头节点
public class MyLinkedList {
private int length; // 链表的长度

private NodeData<E> head;

// 初始化
public MyLinkedList() {
	this.head = new NodeData();
	this.length = 0;
}
// 插入节点(支持- 按照索引插入节点  简单写一下 )
// 尾插
public void insertTail(E value) {
	NodeData data = new NodeData(value);
	NodeData node = this.head;
	while (node.next != null) {
		node = node.next;
	}
	node.next = data;
	this.length++;
}
// 指定索引插入
public void insertAtIndex(int index, E value) {
	if(index <0 || index >this.length) {
		throw new RuntimeException("链表索引越界了");
	}
	NodeData node = this.head;
	for(int i = 0;i < index;i++) {
		node = node.next;
	}
	NodeData data = new NodeData(value);
	
	NodeData next1 = node.next;
	data.next = next1;
	node.next = data;
	
	this.length++;
}

// 删除节点
// 尾删
public E removeTail() {
	E e = null;
	NodeData<E> node = this.head;
	if(node.next == null) {
		throw new RuntimeException("当前链表为空");
	}
	for(int i=0; i < length-1 ;i++) {
		node = node.next;
	}
	
	NodeData<E> next1 = node.next;
	e = next1.data;
	node.next = null;
	
	this.length--;
	
	return e;
}
// 指定索引删除
public E removeTailAtIndex(int index) {
	E e = null;
	NodeData<E> node = this.head;
	if(index <0 || index > this.length-1) {
		throw new RuntimeException("链表索引越界了");
	}
	for(int i=0; i < index-1 ;i++) {
		node = node.next;
	}
	
	NodeData<E> next1 = node.next;
	e = next1.data;
	node.next = null;
	
	this.length--;
	
	return e;
}

// 访问节点

// 查找节点

// 内部类 
class NodeData<E>{
	// 指向下一个节点的引用
	private NodeData<E> next;
	// 本节点存储的数据
	private E data;
	
	public NodeData(E e) {
		this.data = e;
	}
	public NodeData() {
		this.data = null;
		this.next = null;
	}
}

}

[hanzhe-one]

good

[FRANK55666]

C#的代码能不能写.net framework的版本，初学者学不明白那么高级的东西

[sagiri5]

非常感谢

[Hacker-C]

Java 实现单向链表

1、ListNode 定义：

public class ListNode<T> {
    public T value;
    public ListNode<T> next;

    public ListNode(T value) {
        this.value = value;
    }

    public ListNode(T value, ListNode<T> next) {
        this.value = value;
        this.next = next;
    }
}

2、实现链表

public class MyLinkedList {
    private ListNode<Integer> head = null;
    public MyLinkedList() {
    }

    /**
     * 获取指定位置的元素
     * 
     * @param index
     * @return
     */
    public int get(int index) {
        ListNode<Integer> cur = head;
        for (int i = 0; i < index; i++) {
            if (cur != null) {
                cur = cur.next;
            }
        }
        if (cur == null) return -1;
        return cur.value;
    }

    /**
     * 头插
     * 
     * @param val
     */
    public void addAtHead(int val) {
        if (head == null) {
            head = new ListNode<>(val);
            return;
        }
        ListNode<Integer> newHead = new ListNode<>(val);
        newHead.next = head;
        head = newHead;
    }

    /**
     * 尾加
     * @param val
     */
    public void addAtTail(int val) {
        ListNode<Integer> cur = head;
        while (cur != null && cur.next != null) {
            cur = cur.next;
        }
        if (cur == null) {
            head = new ListNode<>(val);
        } else {
            cur.next = new ListNode<>(val);
        }
    }

    /**
     * 指定位置添加
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        };
        ListNode<Integer> cur = head;
        while (--index > 0) {
            if (cur != null) {
                cur = cur.next;
            }
        }
        if (cur != null) {
            ListNode<Integer> node = new ListNode<>(val);
            ListNode<Integer> temp = cur.next;
            cur.next = node;
            node.next = temp;
        }
    }

    /**
     * 指定索引删除
     * 
     * @param index
     */
    public void deleteAtIndex(int index) {
        ListNode<Integer> pre = new ListNode<>(null);
        ListNode<Integer> cur = head;
        pre.next = head;
        while (index-- > 0 && cur != null) {
            cur = cur.next;
            pre = pre.next;
        }
        if (pre != null && cur != null) {
            pre.next = cur.next;
            if (cur == head) {
                head = pre.next;
            }
        }
    }

    public String toString() {
        List<String> list = new ArrayList<>();
        ListNode<Integer> cur = head;
        while (cur != null) {
            list.add(cur.value.toString());
            cur = cur.next;
        }
        return String.join("->", list);
    }
}

[Limit1996]

C#备忘

namespace _1.Console;

public class CustomLinkedList<T>
{
    private Node<T>? _head;

    public CustomLinkedList(Node<T>? head = null)
    {
        _head = head;
    }

    public void Insert(Node<T> node, Node<T> newNode)
    {
        if (_head == null)
            throw new InvalidOperationException("链表为空，无法插入新节点");
        if (node == null)
            throw new ArgumentNullException(nameof(node));
        if (newNode == null)
            throw new ArgumentNullException(nameof(newNode));
        
        var temp = node.Next;
        node.Next = newNode;
        newNode.Next = temp;
    }

    public void Remove(Node<T> node)
    {
        if (_head == null)
            throw new InvalidOperationException("链表为空");
        if (node == null)
            throw new ArgumentNullException(nameof(node));
        if (node.Next == null)
            throw new InvalidOperationException("无法删除最后一个节点");
        node.Next = node.Next.Next;
    }

    public Node<T>? Get(int index)
    {
        if(_head == null)
            throw new InvalidOperationException("链表为空");
        if (index < 0)
            throw new ArgumentOutOfRangeException(nameof(index), "索引不能小于0");

        var current = _head;
        var i = 0;
        while (current.Next != null)
        {
            if(i == index)
                return current;
            i++;
            current = current.Next;
        }

        return null;
    }

    public int FindIndex(T value)
    {
        if (_head == null)
            throw new InvalidOperationException("链表为空");
        if (value == null)
            throw new ArgumentNullException(nameof(value));
        
        if (_head.Value!.Equals(value)) return 0;
        
        var current = _head;
        var i = 0;
        while (current.Next != null)
        {
            if (current.Value!.Equals(value))
                return i;
            current = current.Next;
            i++;
        }
        return -1;
    }
}