数据结构与算法 - Linked list

2022-07-19

全文 ≈ 1.8k字 | 预计阅读时长 8分钟

链表是一种不需要连续空间存储的线性数据结构，通过指针把数据节点链接起来。数据节点的逻辑顺序取决于链表指针链接的先后顺序，同时，链表也有：单链表、双链表、循环链表等多类。

定义

链表是由一系列节点组成，除此之外链表还有几个基本概念：

数据节点

一般由两块组成：数据域、指针域。
首元节点

链表的第一个数据节点。
头节点

非必要节点，放在第一个数据节点前。一般用于存储链表的信息（比如说链表长度等）和保证数据节点操作的统一性。
头指针

指向第一个节点的指针，如果有头节点则指向头节点，否则指向首元节点。

单链表

最简单的一种链表，只支持一个遍历方向：链头 -> 链尾。两部分组成：当前节点的数据、指向后置节点的指针（尾节点指针指向nil）。

例子：

type Node struct {
	V    string
	Next *Node
}

func main() {
	// 头节点
	head := &Node{
		V: "head node",
	}

	// 节点1
	node := &Node{
		V: "node1",
	}
	head.Next = node

	// 节点2
	node2 := &Node{
		V: "node2",
	}
	node.Next = node2

	// 节点3
	node3 := &Node{
		V: "node3",
	}
	node2.Next = node3

	// 头指针 -> 头节点
	linkedList := head
	for linkedList.Next != nil {
		// 打印下一个节点值（这块就体现出头节点的好处，首元节点和其他数据节点的操作一致）
		fmt.Println(linkedList.Next.V)
		linkedList = linkedList.Next
	}
}

以上是单链表的简单实现，其中添加节点的操作也被称为：尾插法，封装一下：

type Node struct {
	V    string
	Next *Node
}

type List struct {
	Head *Node
}

func main() {
	list := &List{}
	n1 := &Node{V: "node1"}
	n2 := &Node{V: "node2"}
	n3 := &Node{V: "node3"}
	list.Append(n1)
	list.Append(n2)
	list.Append(n3)
	list.Traverse() // 输出结果：node1->node2->node3->nil
}

// 尾插法
func (l *List) Append(node *Node) {
	if l.Head == nil {
		l.Head = node
	} else {
		now := l.Head
		for now.Next != nil {
			now = now.Next
		}
		now.Next = node
	}
}

// 遍历
func (l *List) Traverse() {
	now := l.Head
	for now != nil {
		if now.Next == nil {
			print(now.V, "->", "nil")
		} else {
			print(now.V, "->")
		}
		now = now.Next
	}
}

如果有数据节点想要插队，怎么办？头插法，思路就是：把头节点作为新增节点的后置节点，新增节点作为新的头节点。

func (l *List) Insert(node *Node) {
	if l.Head == nil {
		l.Head = node
	} else {
		node.Next = l.Head
		l.Head = node
	}
}

还想把链表反转，数据节点逆序呢？有很多种方式，比如：利用双指针迭代、递归等等

迭代，思路和头插法一致。

func (l *List) Reverse() {
	if l.Head == nil {
		return
	}
	// 声明一个头节点
	var head *Node
	// 开始遍历链表，
	// 第一次，head：node1 -> nil
	// 第一次，now：node2 -> node3 -> nil
	// 第二次，head：node2 -> node1 -> nil
	// 第二次，now：node3 -> nil
	// 第三次，head：node3 -> node2 -> node1 -> nil
	// 第三次，now：nil
	now := l.Head
	for now != nil {
		// 记录当前节点的后置节点
		next := now.Next
		// 当前节点的后置节点变为头节点，当前节点变为新的头节点。这个操作和插入节点的逻辑一致，把头节点作为当前节点的后置节点，当前节点作为新的头节点。
		if head == nil {
			now.Next = nil
		} else {
			now.Next = head
		}
		head = now
		// 指针后移
		now = next

		// 语法糖版本
		// now, now.Next, head = now.Next, head, now // 语法糖版本，拆解如下
		// now = now.Next
		// now.Next = head
		// head = now

		// printNode(head)
		// printNode(now)
	}
	l.Head = head
}

func printNode(node *Node) {
	if node == nil {
		print("nil")
	}
	now := node
	for now != nil {
		if now.Next == nil {
			print(now.V, "->", "nil")
		} else {
			print(now.V, "->")
		}
		now = now.Next
	}
	print("\n")
}

删除操作:

func (l *List) Delete(node *Node) {
	if l.Head == nil {
		return
	}
	// 如果是尾节点，则需要找出删除节点的前置节点
	if node.Next == nil {
		prev := l.Head
		for prev.Next != node {
			prev = prev.Next
		}
		prev.Next = nil
	} else {
		// 如果不是尾节点，把删除节点的后置节点数据直接覆盖删除节点。
		*node = *node.Next
	}
	return
}

单链表的实现比较简单，可以很轻松的查询到指定节点的后置节点，但如果想要查询前置节点则需要遍历一遍才可以，所以这就需要双链表了

双链表

双链表通俗的讲，就是每个数据节点既可以找到它前一个节点也找的到它后一个节点。三部分组成：前值节点的指针，节点数据，后置节点的指针（尾节点指针指向nil）。

直接上代码:

type Node struct {
	V    string
	Prev *Node
	Next *Node
}

type List struct {
	Head *Node
	Tail *Node
}

func main() {
	list := &List{}
	n1 := &Node{V: "node1"}
	n2 := &Node{V: "node2"}
	n3 := &Node{V: "node3"}
	list.Append(n1)
	list.Append(n2)
	list.Append(n3)
	list.Traverse() // 输出结果：node1<->node2<->node3->nil
}

func (l *List) Append(node *Node) {
	if l.Head == nil {
		l.Head = node
		l.Tail = node
	} else {
		// 尾节点
		prev := l.Tail
		// 尾节点设为当前节点的前置节点
		node.Prev = prev
		// 当前节点设为尾节点的后置节点
		prev.Next = node
		// 当前节点变为尾节点
		l.Tail = node
	}
}

func (l *List) Delete(node *Node) {
	if l.Head == nil {
		return
	}
	// 删除节点的前置节点
	prev := node.Prev
	// 删除节点的后置节点设为前置节点的后置节点
	prev.Next = node.Next
	// 删除节点的前置节点设为后置节点的前置节点
	node.Next.Prev = node.Prev
}

func (l *List) Traverse() {
	now := l.Head
	for now != nil {
		if now.Next == nil {
			print(now.V, "->", "nil")
		} else {
			print(now.V, "<->")
		}
		now = now.Next
	}
}

双链表较单链表的不同比较明显，双链表可以很轻松的查找到指定节点的前置和后置节点，遍历方向也可以是从头到尾或者从尾到头。同时，双链表节点操作比较复杂，占用空间也更大。

循环链表

顾名思义，循环链表是一个环状的链表。循环链表又分为：单向循环链表、双向循环链表，实现上就是把尾节点和头节点进行链接。

单向循环链表：

type Node struct {
	V    string
	Next *Node
}

type List struct {
	Head *Node
}

func main() {
	list := &List{}
	n1 := &Node{V: "node1"}
	n2 := &Node{V: "node2"}
	n3 := &Node{V: "node3"}
	list.Append(n1)
	list.Append(n2)
	list.Append(n3)
	list.Traverse() // 输出结果：node1->node2->node3->node1
}

func (l *List) Append(node *Node) {
	if l.Head == nil {
		l.Head = node
		node.Next = l.Head
	} else {
		now := l.Head
		for now.Next != l.Head {
			now = now.Next
		}
		now.Next = node
		node.Next = l.Head
	}
}

func (l *List) Traverse() {
	now := l.Head
	for {
		if now.Next == l.Head {
			print(now.V, "->", l.Head.V)
			break
		} else {
			print(now.V, "->")
		}
		now = now.Next
	}
}

使用场景

链表是最基础且很常用的一种数据结构，可以解决很多算法问题，也可以用于构建其他的数据结构。比如说解决约瑟夫环问题和实现堆栈、队列等。