设计链表
题目描述
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中
index号节点的值。如果索引无效，则返回-1。 - addAtHead(val)：在链表的第一个元素之前添加一个值为
val的节点。插入后，新节点将成为链表的第一个节点。 - addAtTail(val)：将值为
val的节点追加到链表的最后一个元素。 - addAtIndex(index,val)：在链表中的
index号节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 - deleteAtIndex(index)：如果索引
index有效，则删除链表中的第index个节点。
示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.AddAtHead(1); linkedList.AddAtTail(3); linkedList.AddAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.Get(1); //返回2 linkedList.DeleteAtIndex(1); //现在链表是1-> 3 linkedList.Get(1); //返回3
思路
题目要求
- 创建一个链表类，类中有构造器和五个方法：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
本题可采用单链表和双链表两种方式
单链表是最简单的一种，它提供了在常数时间内的 addAtHead 操作和在线性时间内的 addAtTail 的操作。
双链表是最常用的一种，因为它提供了在常数时间内的 addAtHead 和 addAtTail 操作，并且优化了插入和删除。
双链表比单链表快得多，测试用例花费的时间比单链表快了两倍。但是它更加复杂，它包含了 size，记录链表元素个数，不计伪头伪尾。
为了使插入和删除时间消耗更少，我使用双链表；为了简化插入和删除，我在头节点前加入一个伪头。
注意
- Go 语言中没有类（Class）的概念，但可以使用结构体（Structs）对属性进行封装，结构体就像是类的一种简化形式
- Go 方法是作用在接收者（Receiver）上的一个函数，接收者是某种类型的变量。因此方法是一种特殊类型的函数。
定义方法的格式如下：
func (recv receiver_type) methodName(parameter_list) (return_value_list) { ... }
- Go语言中没有提供构造函数相关的特殊机制，用户根据自己的需求，将参数使用函数传递到结构体构造参数中即可完成构造函数的任务。
index从0开始- 在添加节点后
size++，删除节点后size--
代码
Go
// MyLinkedList 双链表(类) type MyLinkedList struct { size int dummyHead *Node dummyTail *Node } // Node 节点(结构体) type Node struct { value int pre *Node next *Node } // Constructor 构造方法 func Constructor() MyLinkedList { dummyHead := new(Node) dummyTail := new(Node) dummyHead.next = dummyTail dummyTail.pre = dummyHead return MyLinkedList{0, dummyHead, dummyTail} } // GetNode 获取链表index号节点 func (this *MyLinkedList) GetNode(index int) *Node { p := this.dummyHead.next if index <= (this.size >> 1) { // 从前遍历 for i := 0; i < index; i++ { p = p.next } } else { // 从后遍历 p = this.dummyTail.pre for i := 0; i < this.size-1-index; i++ { p = p.pre } } return p } // Get 获取链表index号节点的数值 func (this *MyLinkedList) Get(index int) int { if index < 0 || index >= this.size { // 索引无效 return -1 } return this.GetNode(index).value } // AddAtHead 在链表的最前面插入一个节点 func (this *MyLinkedList) AddAtHead(val int) { head := new(Node) head.value = val head.pre = this.dummyHead head.next = this.dummyHead.next this.dummyHead.next = head head.next.pre = head this.size++ } // AddAtTail 在链表的最后面插入一个节点 func (this *MyLinkedList) AddAtTail(val int) { tail := new(Node) tail.value = val tail.pre = this.dummyTail.pre tail.next = this.dummyTail this.dummyTail.pre = tail tail.pre.next = tail this.size++ } // AddAtIndex 在链表index号节点前面插入一个节点 func (this *MyLinkedList) AddAtIndex(index int, val int) { if index < 0 { // 在链表的最前面插入一个节点 this.AddAtHead(val) return } if index == this.size { this.AddAtTail(val) return } if index > this.size { return } indexNode := this.GetNode(index) newNode := new(Node) newNode.value = val newNode.pre = indexNode.pre newNode.next = indexNode indexNode.pre = newNode newNode.pre.next = newNode this.size++ } func (this *MyLinkedList) DeleteAtIndex(index int) { if index < 0 || index >= this.size { // 索引无效 return } indexNode := this.GetNode(index) indexNode.pre.next = indexNode.next indexNode.next.pre = indexNode.pre this.size-- }
