数据结构【Golang实现】(四)——双向循环链表

0. 定义节点

type DLNode struct {Data       anyPrev, Next *DLNode
}// DoublyLoopLinkedList 双向循环链表
type DoublyLoopLinkedList struct {headNode *DLNode
}

1. IsEmpty()

// IsEmpty 判断链表是否为空
func (l *DoublyLoopLinkedList) IsEmpty() bool {if l.headNode == nil {return true}return false
}

2. Length()

// Length 获取链表长度
func (l *DoublyLoopLinkedList) Length() int {if l.IsEmpty() {return 0}currentNode := l.headNodecount := 1for currentNode.Next != l.headNode {count++currentNode = currentNode.Next}return count
}

3. AddFromHead()

// AddFromHead 从双向循环链表头部增加节点
func (l *DoublyLoopLinkedList) AddFromHead(data any) {node := &DLNode{Data: data}if l.IsEmpty() {l.headNode = nodereturn}currentNode := l.headNodefor currentNode.Next != l.headNode { // 遍历到尾结点currentNode = currentNode.Next}currentNode.Next = nodel.headNode.Prev = nodenode.Prev = currentNodenode.Next = l.headNodel.headNode = node
}

4. AddFromTail()

// AddFromTail  从双向循环链表尾部增加节点
func (l *DoublyLoopLinkedList) AddFromTail(data any) {node := &DLNode{Data: data}if l.IsEmpty() {l.headNode = nodereturn}currentNode := l.headNodefor currentNode != l.headNode { // 遍历到尾结点currentNode = currentNode.Next}currentNode.Next = nodel.headNode.Prev = nodenode.Prev = currentNodenode.Next = l.headNode
}

5. Insert()

// Insert  从双向循环链表指定位置增加节点 下标从0开始
func (l *DoublyLoopLinkedList) Insert(position int, data any) {if position <= 0 {l.AddFromHead(data)return} else if position >= l.Length()-1 {l.AddFromTail(data)return} else {node := &DLNode{Data: data}count := 0currentNode := l.headNodefor count != position {count++currentNode = currentNode.Next}node.Next = currentNodenode.Prev = currentNode.PrevcurrentNode.Prev.Next = nodecurrentNode.Prev = node}
}

6. DeleteHead()

// DeleteHead 删除链表头结点
func (l *DoublyLoopLinkedList) DeleteHead() {if l.IsEmpty() {fmt.Println("Doubly Linked List is Empty")return}currentNode := l.headNodeif currentNode.Next == l.headNode { // 只有一个节点的情况l.headNode = nilreturn} else {for currentNode.Next != l.headNode { // 遍历到倒数第一个节点currentNode = currentNode.Next}currentNode.Next = l.headNode.Nextl.headNode.Next.Prev = currentNodel.headNode = l.headNode.Next}
}

7. DeleteTail()

// DeleteTail 删除链表尾结点
func (l *DoublyLoopLinkedList) DeleteTail() {if l.IsEmpty() {fmt.Println("Doubly Linked List is Empty")return}currentNode := l.headNodeif currentNode.Next == l.headNode { // 只有一个节点的情况l.headNode = nilreturn} else {for currentNode.Next != l.headNode {currentNode = currentNode.Next}currentNode.Prev.Next = l.headNodel.headNode.Prev = currentNode.Prev}
}

8. Remove()

// Remove 删除链表指定位置结点
func (l *DoublyLoopLinkedList) Remove(position int) {if position <= 0 {l.DeleteHead()return} else if position >= l.Length()-1 {l.DeleteTail()return} else {count := 0currentNode := l.headNodefor count != position {count++currentNode = currentNode.Next}currentNode.Prev.Next = currentNode.NextcurrentNode.Next.Prev = currentNode.Prev}
}

9. RemoveByValue()

// RemoveByValue 删除链表指定值的节点
func (l *DoublyLoopLinkedList) RemoveByValue(data any) {if l.IsEmpty() {fmt.Println("Doubly Linked List is Empty")return}currentNode := l.headNodeif currentNode.Data == data { // 比较头结点l.DeleteHead()return}for currentNode.Next != l.headNode { // 这里是跳过了头结点的if currentNode.Next.Data == data {currentNode.Next.Prev.Next = currentNode.Next.NextcurrentNode.Next.Next.Prev = currentNode.Next.Prevreturn} else {currentNode = currentNode.Next}}
}

10. Contain()

// Contain 查询双向循环链表是否包含某个节点
func (l *DoublyLoopLinkedList) Contain(data any) bool {if l.IsEmpty() {return false}currentNode := l.headNodefor currentNode.Next != l.headNode {if currentNode.Data == data {return true} else {currentNode = currentNode.Next}}if currentNode.Data == data {return true}return false
}

11. Traverse()

// Traverse 遍历双向循环链表
func (l *DoublyLoopLinkedList) Traverse() {if l.IsEmpty() {fmt.Println("Doubly Linked List is Empty")return}currentNode := l.headNodefor currentNode.Next != l.headNode {fmt.Printf("%v -> ", currentNode.Data)currentNode = currentNode.Next}fmt.Printf("%v\n", currentNode.Data)
}