数据结构【Golang实现】(一)——单链表

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

type LinkedList struct {
	headNode *Node // 头指针
}

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

// Length 向链表尾部添加结点
func (l *LinkedList) Length() int {
	currentNode := l.headNode
	if currentNode == nil {
		return 0
	}
	length := 0
	for currentNode != nil {
		length++
		currentNode = currentNode.Next
	}
	return length
}

// AddFromHead 向链表尾部添加结点
func (l *LinkedList) AddFromHead(data any) {
	node := &Node{data, nil}
	if l.IsEmpty() { // 如果链表为空，设置该node为头结点即可
		l.headNode = node
		return
	}
	// 将头指针指向的头结点设置为该节点的next，并将头指针指向该节点
	node.Next = l.headNode
	l.headNode = node
}

// AddFromTail 向链表尾部添加结点
func (l *LinkedList) AddFromTail(data any) {
	node := &Node{data, nil}
	if l.IsEmpty() == true {
		l.headNode = node
		return
	}
	currentNode := l.headNode
	for currentNode.Next != nil { // 直接遍历到最后一个节点
		currentNode = currentNode.Next
	}
	currentNode.Next = node
}

// Insert 向链表中指定位置添加结点，下标0开始
func (l *LinkedList) Insert(position int, data any) {
	if position <= 0 { // 如果位置<=0，就直接在从头部添加
		l.AddFromHead(data)
	} else if position >= l.Length() { // 如果位置>=l.Length()，就直接在从尾部添加
		l.AddFromTail(data)
	} else { // 否则
		node := &Node{data, nil}
		preNode := l.headNode
		count := 0
		for count != position-1 { // 循环退出以后pre刚好在position-1的位置
			preNode = preNode.Next
			count++
		}
		node.Next = preNode.Next
		preNode.Next = node
	}
}

// DeleteHead 删除头部
func (l *LinkedList) DeleteHead() any {
	if l.IsEmpty() {
		fmt.Println("LinkedList is empty")
		return nil
	}
	head := l.headNode
	l.headNode = l.headNode.Next
	return head
}

// DeleteTail 删除尾部节点
func (l *LinkedList) DeleteTail() any {
	if l.IsEmpty() {
		fmt.Println("LinkedList is empty")
		return nil
	}
	currentNode := l.headNode
	for currentNode.Next.Next != nil { //如果下下个节点为nil，说明下个节点是最后一个节点
		currentNode = currentNode.Next
	}
	data := currentNode.Next.Data
	currentNode.Next = nil // 删除最后一个节点
	return data
}

// Remove 删除指定节点
func (l *LinkedList) Remove(data any) {
	if l.IsEmpty() {
		return
	}
	currentNode := l.headNode
	if currentNode.Data == data {
		l.headNode = currentNode.Next
	} else {
		for currentNode.Next != nil { // 遍历到倒数第二个节点
			if currentNode.Next.Data == data { // 用下一个节点去比较（保证尾结点不被漏掉），头结点在上面已经比较过了
				currentNode.Next = currentNode.Next.Next
			} else {
				currentNode = currentNode.Next
			}
		}
	}
}

// Contain 链表中是否包含某个值的节点
func (l *LinkedList) Contain(data any) bool {
	if l.IsEmpty() {
		return false
	}
	currentNode := l.headNode
	if currentNode.Data == data {
		return true
	}
	for currentNode != nil {
		if currentNode.Data == data {
			return true
		}
		currentNode = currentNode.Next
	}
	return false
}

// Traverse 遍历单链表
func (l *LinkedList) Traverse() {
	if l.IsEmpty() {
		fmt.Println("LinkedList is empty")
		return
	}
	currentNode := l.headNode
	for currentNode != nil {
		fmt.Printf("%v -> ", currentNode.Data)
		currentNode = currentNode.Next
	}
}