707.设计链表

一、问题描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。

二、方案一：单链表实现

1、思路

设计思路：使用一个单链表结构，其中每个节点包含一个值和一个指向下一个节点的指针。为了方便操作，我们可以在链表前添加一个哑结点（dummy node），这样删除和新增操作时就不需要对头节点进行特殊处理。

2、代码实现

type Node struct {
	Val  int
	Next *Node
}
type MyLinkedList struct {
	size      int
	dummyHead *Node
}

func Constructor() MyLinkedList {
	// 初始化哑结点
	return MyLinkedList{size: 0, dummyHead: &Node{}}
}
func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	// 从哑结点开始遍历
	cur := this.dummyHead.Next
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
	this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
	this.AddAtIndex(this.size, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index > this.size {
		return
	}
	if index < 0 {
		index = 0
	}
	this.size++
	// 找到要插入位置的前一个节点
	pred := this.dummyHead
	for i := 0; i < index; i++ {
		pred = pred.Next
	}
	// 插入新节点
	toAdd := &Node{Val: val}
	toAdd.Next = pred.Next
	pred.Next = toAdd
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	this.size--
	// 找到要删除节点的前一个节点
	pred := this.dummyHead
	for i := 0; i < index; i++ {
		pred = pred.Next
	}
	pred.Next = pred.Next.Next
}

3、复杂度分析

• 时间复杂度：get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 都是 O(1) 到 O(n)，取决于 index 的位置。
• 空间复杂度：O(1)，除了存储链表本身的节点外，我们不需要额外的空间。

三、方案二：双链表实现

1、思路

设计思路：使用一个双链表结构，其中每个节点包含一个值、指向前一个节点的指针和指向下一个节点的指针。同样，为了方便操作，我们可以在链表前添加一个哑结点。

2、代码实现

type MyLinkedList struct {
	dummyHead *Node
	size      int
}

type Node struct {
	Val  int
	Prev *Node
	Next *Node
}

func Constructor() MyLinkedList {
	dummyHead := &Node{}
	return MyLinkedList{dummyHead, 0}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	curl := this.dummyHead
	for i := 0; i <= index; i++ {
		curl = curl.Next
	}

	return curl.Val
}

func (this *MyLinkedList) AddAtHead(val int) {
	this.AddAtIndex(0, val)
}

func (this *MyLinkedList) AddAtTail(val int) {
	this.AddAtIndex(this.size, val)
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 || index > this.size {
		return
	}
	this.size++
	prev := this.dummyHead
	for i := 0; i < index; i++ {
		prev = prev.Next
	}
	// 插入新节点
	node := &Node{Val: val}

	node.Prev = prev
	node.Next = prev.Next

	prev.Next = node
	if node.Next != nil {
		node.Next.Prev = node
	}
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	this.size--
	prev := this.dummyHead
	for i := 0; i < index; i++ {
		prev = prev.Next
	}
	prev.Next = prev.Next.Next
	if prev.Next != nil {
		prev.Next.Prev = prev
	}
}

3、复杂度分析

• 时间复杂度：get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 都是 O(1) 到 O(n)，取决于 index 的位置。
• 空间复杂度：O(1)，除了存储链表本身的节点外，我们不需要额外的空间。

四、总结

方案	类型	时间复杂度	空间复杂度	优点	缺点
方案一	单链表	O(1) 到 O(n)	O(1)	实现简单，空间效率高	无法双向遍历
方案二	双链表	O(1) 到 O(n)	O(1)	可以双向遍历	实现复杂

两种方案都有效地实现了链表的基本操作，但双链表提供了更灵活的遍历方式，代价是更高的实现复杂性。根据具体需求选择合适的方案。