双向链表(Doubly Linked List)

什么是双向链表？

双向链表（Doubly Linked List）是一种链表数据结构，其中每个节点不仅包含指向下一个节点的指针，还包含指向上一个节点的指针。与单向链表不同，双向链表可以在常数时间内从任意节点开始向前向后遍历，因此可以更加灵活的操作链表。

双向链表的结构

每个节点包含三个部分：

• 数据部分：存储节点的数据
• 前驱节点：存储指向前一个节点的指针
• 后继节点：存储指向下一个节点的指针

每个双向链表包含两个指针：

• 头指针：指向链表头部的指针
• 尾指针：指向链表尾部的指针

为了方便统计链表的长度，我们还可以在双向链表的结构中添加一个计数器，用于记录链表中的节点数量。

• 头指针：指向链表头部的指针
• 尾指针：指向链表尾部的指针
• 计数器：记录链表中的节点数量

双向链表的操作

• 插入操作

  • 在头部插入节点
  • 在尾部插入节点
  • 在指定位置插入节点

• 删除操作

  • 删除头部节点
  • 删除尾部节点
  • 删除指定位置节点
  • 删除指定值节点

• 遍历操作

  • 从头部遍历到尾部
  • 从尾部遍历到头部

• 查找操作

  • 查找指定值的节点
  • 查找指定位置的节点

• 反转操作

  • 反转整个链表
  • 反转指定范围的链表

• 长度操作

  • 获取链表的长度

双向链表的实现

双向链表的定义

// 双链表节点结构体
type Node struct {
	Val  int   // 节点的值
	Prev *Node // 指向前一个节点的指针
	Next *Node // 指向下一个节点的指针
}

// 双链表结构体
type DoublyLinkedList struct {
	Head *Node // 指向头节点的指针
	Tail *Node // 指向尾节点的指针
}

// NewDoublyLinkedList 创建一个双链表
func NewDoublyLinkedList() *DoublyLinkedList {
	return &DoublyLinkedList{}
}

双向链表的插入操作

在头部插入节点

// AddNodeAtHead 在链表头部添加节点
func (d *DoublyLinkedList) AddNodeAtHead(val int) {
	// 创建节点
	node := &Node{Val: val}
	// 如果头节点为空
	// 则表示当前链表为空
	// 将新节点设置为头节点和尾节点
	if d.Head == nil {
		d.Head = node
		d.Tail = node
	} else {
		// 头节点不为空
		// 则将新节点的Next指针指向当前头节点
		// 并将当前头节点的Prev指针指向新节点
		// 将新节点设置为头节点
		node.Next = d.Head
		d.Head.Prev = node
		d.Head = node
	}
}

时间复杂度：O(1)

在尾部插入节点

// AddNodeAtTail 在链表尾部添加节点
func (d *DoublyLinkedList) AddNodeAtTail(val int) {
	// 创建节点
	node := &Node{Val: val}
	// 如果头节点为空
	// 则表示当前链表为空
	// 将新节点设置为头节点和尾节点
	if d.Head == nil {
		d.Head = node
		d.Tail = node
	} else {
		// 头节点不为空
		// 则将新节点的Prev指针指向当前尾节点
		// 并将当前尾节点的Next指针指向新节点
		// 将新节点设置为尾节点
		node.Prev = d.Tail
		d.Tail.Next = node
		d.Tail = node
	}
}

时间复杂度：O(1)

在指定位置插入节点

// AddNodeAtIndex 在指定位置添加节点
func (d *DoublyLinkedList) AddNodeAtIndex(index int, val int) {
	// 索引必须大于等于0
	if index < 0 {
		return
	}
	// 索引等于0时，表示在头部添加节点
	if index == 0 {
		d.AddNodeAtHead(val)
		return
	}

	// 创建节点
	node := &Node{Val: val}

	// 遍历链表找到指定位置
	current := d.Head
	currentIndex := 0
	for current != nil {
		if currentIndex == index {
			node.Next = current      // 将新节点的Next指针指向当前节点
			node.Prev = current.Prev // 将新节点的Prev指针指向当前节点的Prev节点
			current.Prev.Next = node // 将当前节点的Prev节点的Next指针指向新节点
			current.Prev = node      // 将当前节点的Prev指针指向新节点
			break
		}
		current = current.Next
		currentIndex++
	}
}

时间复杂度：O(n)

双向链表的删除操作

删除头部节点

// DeleteNodeAtHead 删除链表头部的节点
func (d *DoublyLinkedList) DeleteNodeAtHead() {
	// 如果头节点为空
	// 则表示当前链表为空
	// 直接返回
	if d.Head == nil {
		return
	}

	// 如果头节点和尾节点相同
	// 则表示当前链表只有一个节点
	// 将头节点和尾节点都设置为nil
	if d.Head == d.Tail {
		d.Head = nil
		d.Tail = nil
	} else {
		// 头节点和尾节点不同
		// 则将头节点的Next节点的Prev指针设置为nil
		// 并将头节点指向头节点的Next节点
		d.Head.Next.Prev = nil
		d.Head = d.Head.Next
	}
}

时间复杂度：O(1)

删除尾部节点

// DeleteNodeAtTail 删除链表尾部的节点
func (d *DoublyLinkedList) DeleteNodeAtTail() {
	// 如果头节点为空
	// 则表示当前链表为空
	// 直接返回
	if d.Head == nil {
		return
	}

	// 如果头节点和尾节点相同
	// 则表示当前链表只有一个节点
	// 将头节点和尾节点都设置为nil
	if d.Head == d.Tail {
		d.Head = nil
		d.Tail = nil
	} else {
		// 头节点和尾节点不同
		// 则将尾节点的Prev节点的Next指针设置为nil
		// 并将尾节点指向尾节点的Prev节点
		d.Tail.Prev.Next = nil
		d.Tail = d.Tail.Prev
	}
}

时间复杂度：O(1)

删除指定位置节点

// DeleteNodeAtIndex 删除指定位置的节点
func (d *DoublyLinkedList) DeleteNodeAtIndex(index int) {
	// 索引必须大于等于0
	if index < 0 {
		return
	}
	// 索引等于0时，表示删除头节点
	if index == 0 {
		d.DeleteNodeAtHead()
		return
	}

	// 遍历链表找到指定位置
	current := d.Head
	currentIndex := 0
	for current != nil {
		if currentIndex == index {
			current.Prev.Next = current.Next // 将当前节点的Prev节点的Next指针指向当前节点的Next节点
			current.Next.Prev = current.Prev // 将当前节点的Next节点的Prev指针指向当前节点的Prev节点
			break
		}
		current = current.Next
		currentIndex++
	}
}

时间复杂度：O(n)

删除指定值节点

// DeleteNodeByValue 删除指定值节点
func (d *DoublyLinkedList) DeleteNodeByValue(val int) {
	// 遍历链表找到指定值的节点
	current := d.Head
	for current != nil {
		if current.Val == val {
			current.Prev.Next = current.Next // 将当前节点的Prev节点的Next指针指向当前节点的Next节点
			current.Next.Prev = current.Prev // 将当前节点的Next节点的Prev指针指向当前节点的Prev节点
		}
		current = current.Next
	}
}

时间复杂度：O(n)

双向链表的遍历操作

从头部遍历到尾部

// TraverseFromHead 从头部遍历链表
func (d *DoublyLinkedList) TraverseFromHead() {
	current := d.Head
	for current != nil {
		fmt.Println(current.Val)
		current = current.Next
	}
}

时间复杂度：O(n)

从尾部遍历到头部

// TraverseFromTail 从尾部遍历链表
func (d *DoublyLinkedList) TraverseFromTail() {
	current := d.Tail
	for current != nil {
		fmt.Println(current.Val)
		current = current.Prev
	}
}

时间复杂度：O(n)

双向链表的查询操作

查询指定位置节点

// FindNodeByIndex 查询指定位置的节点
func (d *DoublyLinkedList) FindNodeByIndex(index int) *Node {
	// 索引必须大于等于0
	if index < 0 {
		return nil
	}
	// 索引等于0时，表示查询头节点
	if index == 0 {
		return d.Head
	}

	// 遍历链表找到指定位置
	current := d.Head
	currentIndex := 0
	for current != nil {
		if currentIndex == index {
			return current
		}
		current = current.Next
		currentIndex++
	}
	return nil
}

时间复杂度：O(n)

查询指定值节点

// FindNodeByValue 查找指定值的节点
func (d *DoublyLinkedList) FindNodeByValue(val int) []*Node {
	var nodes []*Node
	current := d.Head
	for current != nil {
		if current.Val == val {
			nodes = append(nodes, current)
		}
		current = current.Next
	}
	return nodes
}

时间复杂度：O(n)

双向链表的优缺点

优点

1. 双向链表可以在两个方向上进行遍历，相比于单向链表更加灵活。
2. 双向链表可以在任意位置插入和删除节点，相比于单向链表更加方便。
3. 双向链表可以快速地找到前驱节点和后继节点，相比于单向链表更加高效。

缺点

1. 双向链表需要额外的存储空间来存储前驱指针，相比于单向链表更加占用内存。
2. 双向链表的操作相对复杂，需要更多的代码来实现插入、删除和查找等操作。

双向链表的应用场景

1. 数据库：数据库中的索引结构可以使用双向链表来实现，以便快速地进行插入、删除和查找操作。
2. 文本编辑器：文本编辑器中的撤销和重做功能可以使用双向链表来实现，以便快速地进行撤销和重做操作。
3. 图形界面：图形界面中的窗口管理可以使用双向链表来实现，以便快速地进行窗口的排列和切换操作。