设计链表

今天发了几个小时就看了这么一道题目，深深感受到了链表中的临界思维的恶心之处，和一些我以前有一些误区的地方和之前没学习到的知识点，记录一下，狗屎

题目

---

你可以选择使用单链表或者双链表，设计并实现自己的链表。我使用的是单链表

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

结构体构成

---

这是一个层次化的写法，SingleNode代表了节点，MyLinkList代表了链表的整体

要注意在MyLinkList中里面的数据是链表的数据，跟节点没有半毛线关系，唯一有点关系的可能就是可以引出节点的dummyHead-虚拟头结点，

dummyHead就是这个链表的入口，Size就是节点的数量

这个Size节点就设置的很好，有了它就不需要每次都循环找出节点的数量。

同时需要明白dummyHead这个东西不算入结点之中，所以叫虚拟头结点，因此它特么没有index

而且头结点，也就是dummyHead.Next 它的索引是0

// 正确的写法
type SingleNode struct {
	Val  int
	Next *SingleNode
}
type MyLinkList struct {
	dummyHead *SingleNode
	Size      int
}

// 我一开始的写法
type MyLinkList struct {
	dummyHead *MyLinkList
	Size int
	Val int 
}

边界（狗屎）

---

首先

要清楚一个事情

如果要查询某个Index下的数据，则节点要遍历到Index节点的本身

可是如果要增加删除某个节点，则节点要遍历到index 节点的前一个结点

因此有了两种写法

// 遍历到index节点的前一个结点
// 如果后来再看的你觉得想不通
// 0123456 789 这样子凑一下就明白 为什么cur取到虚拟头结点而不是头结点，为什么是i<index
cur := this.dummyHead
for i:=0 ; i<index ; i++{
	cur = cur.Next
} // 可以看一下这个一次循环的过程，因为cur:=dummyHead，因此一次操作后 cur指向的是i索引的那个结点
// 后面做增删操作

// 遍历到Index节点 本身
cur := this.dummyHead
for i:=0 ;i<= index;i++{
    cur = cur.Next
}
// 后面做查询操作，一般都直接return了

其次

链表的遍历都是用指针的方式，一开始我搞不清楚啥时候新建一个结构体，啥时候新建一个指针，然后我就发现我特么一会指针一会结构体，类型都搞乱了，然后我抄了一遍正确答案，发现了正确定义方法

// 正确
newCode := &SingleNode{Val:val}
// 错误, 千万别搞，会把自己搞死的
newCode := SingleNode{Val:val}

再其次

index的是否有效的问题

1. index < 0 这个是毋庸置疑的，毕竟索引小于零玩个球球

// index是不能取到 this.Size这个数字的
// index最大能取到 this.Size-1 究其原因就是因为数量和索引的关系，索引第一个为0
// 下面两个等价，答案总是写第一个，我习惯第二个，所以一开始就把我限制了
if index >= this.Size{}
if index > this.Size{}
--------
//还有一种写法
if index > this.Size{}
// 这种写法出现的时候你就要考虑一下节点是否能取到，this.Size这个节点了（本来是空）
// 就像AddAtIndex中是可以在末尾取到的

3. 我发现正确答案是多不喜欢写 this!=nil 别问我为什么，我也不知道，反正我写了

再其次

重申一下名字

MyLinkedList -- 链表
SingleList -- 单个节点
newCode -- 新建的节点
cur -- 一般是复制虚拟头结点的操作
this -- 就是一个对象
Size -- 链表大小
Val-- 节点数据
Index -- 索引

代码呈现

---

type SingleNode struct {
	Val  int
	Next *SingleNode
}
type MyLinkList struct {
	dummyHead *SingleNode
	Size      int
}

// 创建一个链表
// 注意这边的node的类型都是&SingleNode{}，避免了所谓的结构体混淆
func Constructor() MyLinkList {
	return MyLinkList{dummyHead: &SingleNode{}, Size: 0}
}

// 获得第Index个节点的数据
func (this *MyLinkList) Get(index int) int {
	// 这里要判断三个条件， 不存在以及index无效的情况
	if index < 0 || index > this.Size-1 || this == nil {
		return -1
	}
	cur := this.dummyHead
	for i := 0; i <= index; i++ {
		cur = cur.Next
	}
	return cur.Val
}

// 添加头结点
// 直接设置新节点给他接上就行了
func (this *MyLinkList) AddAtHead(val int) {
	newCode := &SingleNode{Val: val}
	newCode.Next = this.dummyHead.Next
	this.dummyHead.Next = newCode
	this.Size++
}

// 添加节点到尾部
func (this *MyLinkList) AddAtTail(val int) {
	newCode := &SingleNode{Val: val}
	cur := this.dummyHead
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = newCode
	this.Size++
}

//添加节点到 Index
func (this *MyLinkList) AddAtIndex(index int, val int) {
	// 如果index=this.Size 则index刚刚好是最后一个节点的后面一个新建节点
	if index > this.Size || index < 0 || this == nil {
		return
	}
	// 正确答案里 index<0时要变成index=0，我非常不理解
	// 正确答案里没有this== nil
	// 我感觉我的答案就是对的
	newCode := &SingleNode{Val: val}
	cur := this.dummyHead
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	newCode = cur.Next.Next
	cur.Next = newCode
	this.Size++
}

// 删除Index中的数据
func (this *MyLinkList) DeleteAtIndex(index int) {
	if index < 0 || index > this.Size-1 || this != nil {
		return
	}
	cur := this.dummyHead
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	cur.Next = cur.Next.Next
	this.Size--
}

---

这道题还可以双向链表做，但是我以及筋疲力尽了，不想写了

双向链表的思路和单向链表的操作是一样的，也没看出多容易

LeeCode设计链表

代码随想录 设计链表