Personal Blog

数据结构

05-双向链表实现

本节主要介绍以链表为存储形式实现的双向链表和循环双向链表。

Table of Contents

双向链表

在之前链表的章节中提到过，组成双向链表的每个结点由两个指针域构成，两个指针分别指向该结点的直接前驱、直接后继两个元素。

双向链表

与单链表类似，组成链表的每个结点由两个指针域构成，两个指针分别指向该结点的直接前驱、直接后继两个元素。 这里再重申一下双向链表头尾结点的特点（便于和后面的循环双向链表做对比）：

  1. 头结点：
    1. 前驱指针：指向空
    2. 后继指针：指向第一个结点
  2. 尾结点：
    1. 前驱指针：指向倒数第二个结点
    2. 后继指针：指向空

在单链表中，如果知道当前结点，获取下个元素操作的时间复杂度为O(1),获取上一个元素操作的时间复杂度为O(n)。循环链表就解决了该问题， 将这两个操作的时间复杂度都变成了$O(1)$。

循环双向链表

这里再重申一下循环双向链表头尾结点的特点

  1. 头结点：
    1. 前驱指针：指向尾结点
    2. 后继指针：指向直接后继元素
  2. 尾结点：逻辑上的最后一个结点，此时要注意遍历链表时，不能再以指针为空作为停止遍历的依据。
    1. 前驱指针：指向直接前驱元素
    2. 后继指针:指向头结点，形成一个环

由于循环双向链表有前后两个方向的指针，所以遍历、查找元素是否存在等操作，除了像单链表一样通过Next指针进行正向查找外，还可以通过Prior指针进行逆向查找。 特别是当你明确需要查找最后一个索引的结点时，不需要再遍历整个链表，而是直接通过head结点的Prior指针就可以直达,查找尾结点的时间复杂度从$O(n)$降低到$O(1)$。

循环双向链表对线性表的实现

与单链表与循环单链表类似，双向、循环双向链表只是在链表结点中增加了一个Prior的指针域，用于指向该结点的直接前驱。 而且除了插入和删除操作之外，其他操作也没有太大的变动。

类型的定义

表示结点的结构体

type DualLinkedListNode struct {
	Next   *DualLinkedListNode
	Prior  *DualLinkedListNode
	Data   any
	isHead bool
}

表示链表的结构体

type DualLinkedList struct {
	head       *DualLinkedListNode
	length     int
	isCircular bool
}

对线性表接口的实现

同样，这里会对其一一进行实现。

0. NewSingleLinkedList

// 初始化
func NewDualLinkedList(isCircular bool) (l *DualLinkedList) {
	list := new(DualLinkedList)

	header := new(DualLinkedListNode) // Header node is auxiliary node
	header.isHead = true

	list.isCircular = isCircular
	if list.isCircular {
		header.Next = header
		header.Prior = header
	}

	list.head = header

	return list
}

1. ClearList

// 清空线性表中的数据
func (s *DualLinkedList) ClearList() {
	if s.isCircular {
		s.head.Next = s.head
		s.head.Prior = s.head
	}
	s.head.Next = nil
	s.head.Prior = nil
}

2. IsEmpty

// 判断线性表是否为空表
func (s *DualLinkedList) IsEmpty() bool {
	return s.length == 0
}

3. GetLength

// 获取当前线性表中数据的长度
func (s *DualLinkedList) GetLength() int {
	return s.length
}

4. GetElementByIndex

// 获取线性表中位于指定索引的元素
func (s *DualLinkedList) GetElementByIndex(index int) (any, error) {
	if index >= s.length || index < 0 {
		return nil, fmt.Errorf("index out of range")
	}

	curr := s.head
	for i := 0; i <= index; i++ {
		curr = curr.Next
	}

	return curr.Data, nil
}

5. GetElementIndexByValue

// 获取线性表中与指定值相等元素的索引
func (s *DualLinkedList) GetElementIndexByValue(element any) (int, error) {
	var index = 0
	curr := s.head.Next

	for index = 0; index < s.length; index++ {
		if curr.Data == element {
			return index, nil
		}
		curr = curr.Next
	}

	return 0, fmt.Errorf("can't find element %s in list", element)
}

6. GetPriorElement

// 获取线性表中与指定值相等元素的前一个元素
func (s *DualLinkedList) GetPriorElement(element any) (any, error) {
	current := s.head.Next

	for index := 0; index < s.length; index++ {
		if current.Data == element {
			if index == 0 {
				return 0, fmt.Errorf("element %s has been found， but it's already the first element", element)
			}
			return current.Prior.Data, nil
		}

		current = current.Next
	}

	return 0, fmt.Errorf("can't find element %s in data", element)
}

7. GetNextElement

// 获取线性表中与指定值相等元素的后一个元素
func (s *DualLinkedList) GetNextElement(element any) (any, error) {
	current := s.head.Next

	for index := 0; index < s.length; index++ {
		if current.Data == element {
			if current.Next == nil || current.isHead {
				return 0, fmt.Errorf("element %s has been found, but it's already the last element", element)
			} else {
				return current.Next.Data, nil
			}
		}

		current = current.Next
	}

	return 0, fmt.Errorf("can't find element %s in data", element)
}

8. InsertByIndex

// 在线性表中指定索引处插入元素
// InsertByIndex you can insert element into the list, between head and tail, or you will get over range error
func (s *DualLinkedList) InsertByIndex(index int, element any) error {
	if index >= s.length+1 || index < 0 {
		return fmt.Errorf("index is out of range")
	}

	curr := s.head
	var previous *DualLinkedListNode

	for i := 0; i <= index; i++ {
		previous = curr
		curr = curr.Next
	}

	node := &DualLinkedListNode{
		Data: element,
	}

	previous.Next = node
	node.Prior = previous
	node.Next = curr
	if curr != nil {
		curr.Prior = node
	}

	s.length += 1

	return nil
}

9. DeleteByIndex

// 获在线性表中指定索引处删除元素
// DeleteByIndex you can delete element by index, between head and tail, or you will get over range error
func (s *DualLinkedList) DeleteByIndex(index int) (deletedElement any, err error) {
	if index >= s.length || index < 0 {
		return nil, fmt.Errorf("index is out of range")
	}

	curr := s.head
	for i := 0; i <= index; i++ {
		curr = curr.Next
	}

	deletedElement = curr.Data

	curr.Prior.Next = curr.Next
	if curr.Next != nil {
		curr.Next.Prior = curr.Prior
	}

	s.length -= 1

	return deletedElement, nil
}

10. Traverse

// 遍历打印所有元素
func (s *DualLinkedList) Traverse(f func(data any)) {
	current := s.head.Next
	for i := 0; i < s.length; i++ {
		f(current.Data)
		current = current.Next
	}
}

额外算法

头插

// InsertToHead always insert element into the list's head
func (s *DualLinkedList) InsertToHead(element any) error {
	node := &DualLinkedListNode{
		Data: element,
	}

	node.Next = s.head.Next
	s.head.Next = node
	node.Prior = s.head
	if node.Next != nil {
		node.Next.Prior = node
	}

	s.length += 1
	return nil
}

其他同类文章

DATA-STRUCTURE · CHAPTER02
data structure chapter02

Archive