数据结构

03-链表实现

本节主要对链表进行了介绍，分别介绍了单链表、双链表和循环（单、双）链表的形式和特点。然后使用单链表的存储形式来实现线性表。

链表

线性表的链式表示法的底层是使用链表来实现，这里详细说明常见的链表类型以及常见操作。

链表的分类

单链表(线性链表)

通常所说的链表都指单链表或者线性链表，因其组成的节点都是由一个指示方向的指针域构成,从而形成单向链表。

头结点：单链表的第一个节点称为头结点。
头指针：指向头结点的指针称为头指针，单链表的存取等操作都要经过头指针来定位和完成。
尾结点：因为没有更多节点了，所以单链表的最后一个节点的指针域为“空”

双向链表

与单链表类似，组成链表的每个节点由两个指针域构成，两个指针分别指向该节点的直接前驱、直接后继两个元素。

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

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

循环链表

链表中的最后一个节点的指针不再指向空，而是指向了表头节点，形成了一个环。

循环单链表

与单链表类似，但是尾结点不再是空，而是指向头结点，整个链表形成一个环。

头节点：循环单链表的第一个节点称为头结点。
尾结点：最后一个节点的指针域指向头结点，形成一个环

循环双向链表

组成链表的节点由两个指针域构成的链表，两个指针分别指向该节点的直接前驱、直接后继两个元素。

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

链表对线性表的实现

之前提到过，在Go中，使用结构体struct构成每个节点。节点中包含本身信息的信息域和一个指向下一个节点的指针域。这就是上面提到的单链表。

而这是最基本的形态，基于这个结构：
在节点的结构体中，添加一个该节点是否是头指针的标记：
如果是头指针，则不存数据；指针指向链表中的第一个元素
如果不是头指针，就是常见的用于存储数据的链表元素
额外新增一个记录链表其他信息的结构体，记录了头指针的位置、链表的总长度和链表是否为循环链表。

通过上述改动，我们将实现一个即支持单链表，又能支持单项循环链表

类型的定义

表示节点的结构体

type SingleLinkedListNode struct {
    Next   *SingleLinkedListNode
    Data   any
    isHead bool
}

表示链表的结构体

type SingleLinkedList struct {
    head       *SingleLinkedListNode
    length     int
    isCircular bool
}

对线性表接口的实现

前面列出了线性表的基础操作，这里会对其一一进行实现，但是在实现任何一个方法前，我们需要先实现其初始化方法。

0. NewSingleLinkedList

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

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

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

   list.head = header

   return list
}

1. ClearList

// 清空线性表中的数据
func (s *SingleLinkedList) ClearList() {
	header := new(SingleLinkedListNode) // Header node is auxiliary node
	header.isHead = true
	if s.isCircular {
		header.Next = header
	}

	s.head = header
}

2. IsEmpty

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

3. GetLength

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

4. GetElementByIndex

// 获取线性表中位于指定索引的元素
func (s *SingleLinkedList) 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 *SingleLinkedList) GetElementIndexByValue(element any) (int, error) {
	var index = 0
	curr := s.head.Next
	for curr != nil && !curr.isHead {
		if curr.Data == element {
			return index, nil
		}
		curr = curr.Next
		index++
	}

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

6. GetPriorElement

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

	if current != nil && current.Data == element {
		return 0, fmt.Errorf("element %s has been found， but it's already the first element", element)
	}

	for current != nil && !current.isHead {
		if current.Data == element {
			return previous.Data, nil
		}

		previous = current
		current = current.Next
	}

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

7. GetNextElement

// 获取线性表中与指定值相等元素的后一个元素
func (s *SingleLinkedList) GetNextElement(element any) (any, error) {
	current := s.head.Next
	for current != nil && !current.isHead {
		if current.Data == element {
			if current.Next == nil {
				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 *SingleLinkedList) 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 *SingleLinkedListNode
	for i := 0; i <= index; i++ {
		previous = curr
		curr = curr.Next
	}

	node := &SingleLinkedListNode{
		Data: element,
	}

	previous.Next = node
	node.Next = curr

	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 *SingleLinkedList) DeleteByIndex(index int) (deletedElement any, err error) {
	if index > s.length-1 || index < 0 {
		return nil, fmt.Errorf("index is out of range")
	}

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

	deletedElement = curr.Data
	previous.Next = curr.Next

	s.length -= 1

	return deletedElement, nil
}

10. raverse

// 遍历打印所有元素
func (s *SingleLinkedList) Traverse() {
	var index = 0
	fmt.Println("Gonna traverse to print all element:")
	current := s.head.Next
	for current != nil && !current.isHead {
		fmt.Printf("    index: %d, value: %v\n", index, current.Data)
		index++
		current = current.Next
	}
}

其他同类文章

2023-10-19 DATA-STRUCTURE · CHAPTER02
data structure chapter02