提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  前端

当前栏目

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

循环链表数据结构Golang 实现 双向
2023-06-13 09:18:38 时间

0. 定义节点

type DLNode struct {
	Data       any
	Prev, 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.headNode
	count := 1
	for 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 = node
		return
	}
	currentNode := l.headNode
	for currentNode.Next != l.headNode { // 遍历到尾结点
		currentNode = currentNode.Next
	}
	currentNode.Next = node
	l.headNode.Prev = node
	node.Prev = currentNode
	node.Next = l.headNode
	l.headNode = node
}

4. AddFromTail()

// AddFromTail  从双向循环链表尾部增加节点
func (l *DoublyLoopLinkedList) AddFromTail(data any) {
	node := &DLNode{Data: data}
	if l.IsEmpty() {
		l.headNode = node
		return
	}
	currentNode := l.headNode
	for currentNode != l.headNode { // 遍历到尾结点
		currentNode = currentNode.Next
	}
	currentNode.Next = node
	l.headNode.Prev = node
	node.Prev = currentNode
	node.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 := 0
		currentNode := l.headNode
		for count != position {
			count++
			currentNode = currentNode.Next
		}
		node.Next = currentNode
		node.Prev = currentNode.Prev
		currentNode.Prev.Next = node
		currentNode.Prev = node
	}
}

6. DeleteHead()

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

7. DeleteTail()

// DeleteTail 删除链表尾结点
func (l *DoublyLoopLinkedList) DeleteTail() {
	if l.IsEmpty() {
		fmt.Println("Doubly Linked List is Empty")
		return
	}
	currentNode := l.headNode
	if currentNode.Next == l.headNode { // 只有一个节点的情况
		l.headNode = nil
		return
	} else {
		for currentNode.Next != l.headNode {
			currentNode = currentNode.Next
		}
		currentNode.Prev.Next = l.headNode
		l.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 := 0
		currentNode := l.headNode
		for count != position {
			count++
			currentNode = currentNode.Next
		}
		currentNode.Prev.Next = currentNode.Next
		currentNode.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.headNode
	if currentNode.Data == data { // 比较头结点
		l.DeleteHead()
		return
	}
	for currentNode.Next != l.headNode { // 这里是跳过了头结点的
		if currentNode.Next.Data == data {
			currentNode.Next.Prev.Next = currentNode.Next.Next
			currentNode.Next.Next.Prev = currentNode.Next.Prev
			return
		} else {
			currentNode = currentNode.Next
		}
	}
}

10. Contain()

// Contain 查询双向循环链表是否包含某个节点
func (l *DoublyLoopLinkedList) Contain(data any) bool {
	if l.IsEmpty() {
		return false
	}
	currentNode := l.headNode
	for 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.headNode
	for currentNode.Next != l.headNode {
		fmt.Printf("%v -> ", currentNode.Data)
		currentNode = currentNode.Next
	}
	fmt.Printf("%v\n", currentNode.Data)
}

相关文章