单向链表（Singly Linked List）

单向链表（Singly Linked List）是由一些列节点组成的线性数据结构。每个节点包含数据和指向下一个节点的指针。与数组不同，链表的元素在内存中并不需要连续存储，每个节点中保存了下一个节点的指针。

单向链表的结构

节点的结构

一个单向链表的节点由两部分内容组成。

• 数据部分：存储实际的数据。
• 指针部分：存储指向下一个节点的指针。

// 单向链表节点
type ListNode struct {
	Val  any        // 节点中的数据
	Next *ListNode  // 指向下一个节点的指针
}

链表的尾部节点的指针部分通常为nil，表示节点的结束。

链表的结构

// 单向链表
type SinglyLinkedList struct {
	Head *ListNode  // 链表的头节点
}

// 创建一个单向链表
func NewSinglyLinkedList() *SinglyLinkedList {
	return &SinglyLinkedList{}
}

定义一个链表时，通常需要定义一个头节点，头节点不存储实际的数据，仅作为链表的入口。

单向链表的操作

插入

可以在链表的头部、尾部或者指定位置插入节点。

在头部插入

// 在链表的头部添加节点
func (s *SinglyLinkedList) AddAtHead(val any) {
	// 实例化一个节点
	node := &SinglyListNode{Val: val}
	// 如果链表为空，则将新节点设置为头节点
	if s.Head == nil {
		s.Head = node
		return
	}
	// 如果链表不为空，则将新节点的Next指针指向当前头节点，然后将新节点设置为头节点
	node.Next = s.Head
	s.Head = node
}

我们只需要将新的节点插入到头部，并更新头指针。这个操作不需要遍历链表，因此时间复杂度为O(1)。

在尾部插入

// 在链表的尾部添加节点
func (s *SinglyLinkedList) AddAtTail(val any) {
	// 实例化一个节点
	node := &SinglyListNode{Val: val}
	// 如果链表为空，则将新节点设置为头节点
	if s.Head == nil {
		s.Head = node
		return
	}
	// 如果链表不为空，则找到最后一个节点，然后将新节点设置为最后一个节点的Next指针
	current := s.Head
	for current.Next != nil {
		current = current.Next
	}
	current.Next = node
}

为了插入到尾部，我们必须遍历整个链表找到链表的尾节点，假设链表的长度为n，我们需要查找n次，因此在尾部插入节点的时间复杂度为O(n)。

在指定位置插入

// 在链表的指定位置添加节点
func (s *SinglyLinkedList) AddAtIndex(index int, val any) error {
	// 如果index为0，则将新节点设置为头节点
	if index == 0 {
		s.AddAtHead(val)
		return nil
	}
	// 实例化一个节点
	node := &SinglyListNode{Val: val}
	// 找到第index-1个节点
	current := s.Head
	for index > 1 {
		// 如果当前节点为空，则说明index超出了链表的长度，返回错误
		if current == nil {
			return errors.New("index out of range")
		}
		current = current.Next
		index--
	}
	// 将新节点的Next指针指向当前节点的Next指针，然后将当前节点的Next指针指向新节点
	if current != nil {
		node.Next = current.Next
		current.Next = node
	}
	return nil
}

在指定位置插入节点需要遍历到指定位置的前一个节点，假设链表的长度为n，我们需要查找n次，因此在指定位置插入节点的时间复杂度为O(n)。

删除

在头部删除

// 删除链表的头节点
func (s *SinglyLinkedList) DeleteAtHead() {
	// 如果链表头节点不为空，则将头节点指向头节点的Next节点
	if s.Head != nil {
		s.Head = s.Head.Next
	}
}

删除头节点只需要更新头指针，因此时间复杂度为O(1)。

在尾部删除

// 删除链表的尾节点
func (s *SinglyLinkedList) DeleteAtTail() {
	// 如果链表为空，则直接返回
	if s.Head == nil {
		return
	}
	// 如果链表只有一个节点，则将头节点设置为nil
	if s.Head.Next == nil {
		s.Head = nil
		return
	}
	// 找到倒数第二个节点
	current := s.Head
	for current.Next.Next != nil {
		current = current.Next
	}
	// 然后将倒数第二个节点的Next指针设置为nil
	current.Next = nil
}

为了删除尾节点，我们必须遍历到链表的倒数第二个节点，假设链表的长度为n，我们需要查找n-1次，因此在尾部删除节点的时间复杂度为O(n)。

在指定位置删除

// 删除链表的指定位置的节点
func (s *SinglyLinkedList) DeleteAtIndex(index int) error {
	// 如果index为0，则将头节点指向头节点的Next节点
	if index == 0 {
		if s.Head != nil {
			s.Head = s.Head.Next
		}
		return nil
	}
	// 找到第index-1个节点
	current := s.Head
	for index > 1 {
		// 如果当前节点为空，则说明index超出了链表的长度，返回错误
		if current == nil {
			return errors.New("index out of range")
		}
		current = current.Next
		index--
	}
	// 将当前节点的Next指针指向当前节点的Next节点的Next节点
	if current.Next != nil {
		current.Next = current.Next.Next
	}
	return nil
}

在指定位置删除节点需要遍历到指定位置的前一个节点，假设链表的长度为n，我们需要查找n次，因此在指定位置删除节点的时间复杂度为O(n)。

查找

// 查找链表的第index个节点的值
func (s *SinglyLinkedList) Get(index int) (any, error) {
	// 如果index为0，则返回头节点的值
	if index == 0 {
		if s.Head != nil {
			return s.Head.Val, nil
		}
		return nil, errors.New("index out of range")
	}
	// 找到第index个节点
	current := s.Head
	for index > 0 {
		// 如果当前节点为空，则说明index超出了链表的长度，返回错误
		if current == nil {
			return nil, errors.New("index out of range")
		}
		current = current.Next
		index--
	}
	return current.Val, nil
}

查找节点需要遍历到指定位置，假设链表的长度为n，我们需要查找n次，因此在指定位置查找节点的时间复杂度为O(n)。

遍历

// 遍历
func (s *SinglyLinkedList) Traverse() {
	// 将头节点设置为当前节点
	current := s.Head
	// 当前节点不为空，则继续遍历
	for current != nil {
		// 打印当前节点的值
		fmt.Println(current.Val)
		// 将当前节点指向下一个节点
		current = current.Next
	}
}

遍历链表需要遍历整个链表，假设链表的长度为n，我们需要查找n次，因此在指定位置查找节点的时间复杂度为O(n)。

反转

// 反转
func (s *SinglyLinkedList) Reverse() {
	// 将链表的头节点设置为当前节点
	current := s.Head
	// 定义一个变量prev，用于保存当前节点的上一个节点
	var prev *SinglyListNode
	// 如果当前节点不为空，则继续遍历
	for current != nil {
		// 将当前节点的Next赋值给next，用于保存当前节点的下一个节点
		next := current.Next
		// 将当前节点的Next指针指向prev，即将当前节点指向prev
		current.Next = prev
		// 将prev指向当前节点，即将prev指向当前节点的上一个节点
		prev = current
		// 将当前节点指向next，即将当前节点指向当前节点的下一个节点
		current = next
	}
	// 最后将头节点指向prev
	s.Head = prev
}

反转链表需要遍历整个链表，假设链表的长度为n，我们需要查找n次，因此在指定位置查找节点的时间复杂度为O(n)。

链表长度

// 列表的长度
func (s *SinglyLinkedList) Length() int {
	// 将头节点设置为当前节点
	current := s.Head
	// 定义一个变量count，用于保存链表的长度
	count := 0
	// 如果当前节点不为空，则继续遍历
	for current != nil {
		// 将count加1
		count++
		// 将当前节点指向下一个节点
		current = current.Next
	}
	return count
}

遍历链表需要遍历整个链表，假设链表的长度为n，我们需要查找n次，因此在指定位置查找节点的时间复杂度为O(n)。

总结

优缺点

优点：

• 动态内存分配：大小灵活，适合存储不确定数量的元素。
• 高效的插入和删除操作：在已知节点的情况下，插入和删除操作的时间复杂度都是O(1)，尤其是在头部插入和删除的时候。
• 空间开销小：每个节点只存储一个值和一个指针。
• 灵活的内存管理：节点可以动态的创建和删除。

缺点：

• 查询效率低：查找操作时间复杂度为O(n)，无法直接访问中间元素。
• 空间浪费：相对于数组，每个节点都需要额外的指针存储空间。
• 不支持反向遍历：只能从头部向尾部遍历。
• 删除尾部节点困难：删除尾部节点需要遍历整个链表。
• 缺少随机访问：没有内置的索引机制，无法随机访问链表中的元素。

使用场景

• 频繁的插入和删除操作：例如需要频繁进行头部插入和删除的栈
• 内存空间较为紧张的场景：链表通过动态的分配内存避免了大块内存的浪费，适合内存受限的应用。