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

type DNode struct {
	Data       any
	Prev, Next *DNode
}

// DoublyLinkedList 双向链表
type DoublyLinkedList struct {
	headNode *DNode
}

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

// Length 获取双向链表的长度（跟获取单链表长度一模一样）
func (l *DoublyLinkedList) Length() int {
	if l.IsEmpty() {
		return 0
	}
	count := 0
	currentNode := l.headNode
	for currentNode != nil { // 遍历完整个链表
		count++
		currentNode = currentNode.Next
	} // 结束时 currentNode = nil
	return count
}

// AddFromHead 从双向链表头部开始增加结点
func (l *DoublyLinkedList) AddFromHead(data any) {
	node := &DNode{Data: data}
	if l.IsEmpty() {
		l.headNode = node
		return
	}
	l.headNode.Prev = node
	node.Next = l.headNode
	l.headNode = node
}

// AddFromTail 从双向链表尾部添加结点
func (l *DoublyLinkedList) AddFromTail(data any) {
	node := &DNode{Data: data}
	if l.IsEmpty() {
		l.headNode = node
		return
	}
	currentNode := l.headNode
	for currentNode.Next != nil { // 遍历到倒数第一个节点
		currentNode = currentNode.Next
	}
	currentNode.Next = node
	node.Prev = currentNode
}

// Insert 向双向链表的指定位置插入结点
func (l *DoublyLinkedList) Insert(position int, data any) {
	if position <= 0 {
		l.AddFromHead(data)
		return
	} else if position >= l.Length() {
		l.AddFromTail(data)
		return
	}
	count := 0
	node := &DNode{Data: data}
	currentNode := l.headNode
	for count < position-1 { // 停留在目标节点的前一个节点
		count++
		currentNode = currentNode.Next
	}
	node.Next = currentNode.Next
	node.Prev = currentNode
	currentNode.Next.Prev = node
	currentNode.Next = node
}

// DeleteHead 删除链表头结点
func (l *DoublyLinkedList) DeleteHead() {
	if l.IsEmpty() {
		fmt.Println("Doubly Linked List is Empty")
		return
	}
	if l.headNode.Next == nil && l.headNode.Prev == nil { // 只有一个节点的情况
		l.headNode = nil
		return
	}
	l.headNode.Next.Prev = nil
	l.headNode = l.headNode.Next
}

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

// Remove 删除双向链表中指定位置的结点
func (l *DoublyLinkedList) Remove(position int) {
	if position <= 0 {
		l.DeleteHead()
	} else if position >= l.Length()-1 {
		l.DeleteTail()
	} else {
		count := 0
		currentNode := l.headNode
		for count != position { // 遍历到删除位置的前一个节点
			currentNode = currentNode.Next
			count++
		}
		currentNode.Prev.Next = currentNode.Next
		currentNode.Next.Prev = currentNode.Prev
	}
}

// RemoveByValue 删除双向表中指定值的结点
func (l *DoublyLinkedList) RemoveByValue(data any) {
    if currentNode.Data == data { // 判断头结点
		l.DeleteHead()
		return
	}
	if l.IsEmpty() {
		fmt.Println("Doubly Linked List is Empty")
		return
	}
	currentNode := l.headNode
	for currentNode != nil { // 遍历整个链表
		if currentNode.Data == data {
			currentNode.Prev.Next = currentNode.Next
			if currentNode.Next == nil {
				return
			} else {
				currentNode.Next.Prev = currentNode.Prev
				return
			}
		} else {
			currentNode = currentNode.Next
		}

	}
}

// Contain 查询双向链表中是否包含某一个结点(和单向链表一样)
func (l *DoublyLinkedList) Contain(data any) bool {
	if l.IsEmpty() {
		fmt.Println("Doubly Linked List is Empty")
		return false
	}
	currentNode := l.headNode
	for currentNode != nil {
		if currentNode.Data == data {
			return true
		}
		currentNode = currentNode.Next
	}
	return false
}

// Traverse 遍历双向链表（跟遍历单链表一样）
func (l *DoublyLinkedList) Traverse() {
	if l.IsEmpty() {
		fmt.Println("Doubly Linked List is Empty")
		return
	}
	currentNode := l.headNode
	for currentNode.Next != nil {
		fmt.Printf("%v -> ", currentNode.Data)
		currentNode = currentNode.Next
	}
	fmt.Printf("%v\n", currentNode.Data)
}