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

// LNode 定义节点
type LNode struct {
	Data any
	Next *LNode
}

// LoopLinkedList 链表
type LoopLinkedList struct {
	headNode *LNode // 头指针
}

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

// Length 获取循环链表的长度（与单链表的获取长度区别在于循环的终止条件）
func (l *LoopLinkedList) Length() int {
	if l.headNode == nil {
		return 0
	}
	currentNode := l.headNode
	count := 1
	for currentNode.Next != l.headNode {
		count++
		currentNode = currentNode.Next
	}
	return count
}

// AddFromHead 向循环链头部添加结点
func (l *LoopLinkedList) AddFromHead(data any) {
	node := &LNode{Data: data}
	if l.IsEmpty() { // 循环链表为空
		l.headNode = node
		l.headNode.Next = l.headNode //单链表没有这一步
	} else {
		currentNode := l.headNode
		for currentNode.Next != l.headNode { // 需要遍历到最后一个节点 用于将尾部连接新头部
			currentNode = currentNode.Next
		}

		currentNode.Next = node
		node.Next = l.headNode
		l.headNode = node
	}
}

// AddFromTail 向循环链表的尾部添加结点
func (l *LoopLinkedList) AddFromTail(data any) {
	node := &LNode{Data: data}
	if l.IsEmpty() {
		node.Next = l.headNode
		l.headNode.Next = node
	} else {
		currentNode := l.headNode
		for currentNode.Next != l.headNode { // 需要遍历到最后一个节点
			currentNode = currentNode.Next
		}
		node.Next = l.headNode
		currentNode.Next = node
	}
}

// Insert 向循环链表的指定位置添加结点（跟单链表是一样的） 下标0开始
func (l *LoopLinkedList) Insert(position int, data any) {
   if position <= 0 {
      l.AddFromHead(data)
   } else if position >= l.Length() {
      l.AddFromTail(data)
   } else {
      count := 0
      currentNode := l.headNode
      node := &LNode{Data: data}
      for count != position-1 {
         currentNode = currentNode.Next
         count++
      }
      node.Next = currentNode.Next
      currentNode.Next = node
   }
}

// DeleteHead 删除循环链表的头结点
func (l *LoopLinkedList) DeleteHead() {
	if l.IsEmpty() {
		fmt.Println("Loop Linked List is Empty")
		return
	}
	currentNode := l.headNode
	if currentNode.Next == l.headNode { // 只有一个节点的情况
		l.headNode = nil
	} else {
		for currentNode.Next != l.headNode { // 遍历到最后一个节点
			currentNode = currentNode.Next
		}
		currentNode.Next = l.headNode.Next // 尾节点跳过头结点指向第二个节点
		l.headNode = currentNode.Next      // 更新头结点
	}
}

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

// Remove 删除循环链表中指定位置的节点 (需考虑删除的结点是不是第一个或最后一个)
func (l *LoopLinkedList) Remove(position int) {
	if l.IsEmpty() {
		fmt.Println("Loop Linked List is Empty")
		return
	}
	if position <= 0 { // 删除头节点
		l.DeleteHead()
		return
	} else if position >= l.Length()-1 { // 删除尾结点
		l.DeleteTail()
		return
	} else {
		count := 0
		currentNode := l.headNode
		for count != position-1 { // 结束的时候 指在目标节点的前一个
			count++
			currentNode = currentNode.Next
		}
		currentNode.Next = currentNode.Next.Next
	}
}

// RemoveByValue 删除循环链表中指定位置的节点 (需考虑删除的结点是不是第一个或最后一个)
func (l *LoopLinkedList) RemoveByValue(data any) {
	if l.IsEmpty() {
		fmt.Println("Loop 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 = currentNode.Next.Next
			return
		} else {
			currentNode = currentNode.Next
		}
	}
}

// Contain 查找循环链表中指定结点
func (l *LoopLinkedList) Contain(data any) bool {
	if l.IsEmpty() {
		return false
	}
	currentNode := l.headNode
	for currentNode.Next != l.headNode { // 遍历到最后一个节点
		if currentNode.Data == data {
			return true
		}
		currentNode = currentNode.Next
	}
	if currentNode.Data == data { // 不要忘记最后一个节点
		return true
	}
	return false
}

// Traverse 遍历循环链表
func (l *LoopLinkedList) Traverse() {
	if l.IsEmpty() {
		fmt.Println("Loop Linked List is Empty")
		return
	}
	currentNode := l.headNode
	for currentNode.Next != l.headNode {
		fmt.Printf("%v -> ", currentNode.Data)
		currentNode = currentNode.Next
	}
	fmt.Println(currentNode.Data) // 不要忘记尾结点
}