链表

单向链表

// Node 表示单向链表中的一个节点。
// 单向链表的特点是：每个节点只知道自己的值，以及“下一个节点是谁”。
type Node struct {
    Value int
    Next  *Node
}

// LinkedList 表示单向链表。
// Head 指向头节点，也就是链表的入口。
type LinkedList struct {
    Head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

// InsertAtHead 头插法。
// 新节点的 Next 先指向原来的头节点，再把 Head 改成新节点。
func (l *LinkedList) InsertAtHead(value int) {
    newNode := &Node{
        Value: value,
        Next:  l.Head,
    }

    l.Head = newNode
}

// InsertAtTail 尾插法。
// 如果链表为空，新节点直接成为头节点。
// 如果不为空，就一路找到最后一个节点，再把它的 Next 指向新节点。
func (l *LinkedList) InsertAtTail(value int) {
    newNode := &Node{
        Value: value,
    }

    if l.Head == nil {
        l.Head = newNode
        return
    }

    current := l.Head
    for current.Next != nil {
        current = current.Next
    }

    current.Next = newNode
}

// Find 查找指定值的节点。
// 找到后返回节点地址；找不到返回 nil。
func (l *LinkedList) Find(value int) *Node {
    current := l.Head
    for current != nil {
        if current.Value == value {
            return current
        }
        current = current.Next
    }

    return nil
}

// Delete 删除第一个匹配指定值的节点。
// 返回 true 表示删除成功，false 表示没找到目标值。
func (l *LinkedList) Delete(value int) bool {
    if l.Head == nil {
        return false
    }

    // 如果头节点就是目标值，直接让 Head 指向下一个节点即可。
    if l.Head.Value == value {
        l.Head = l.Head.Next
        return true
    }

    prev := l.Head
    current := l.Head.Next

    for current != nil {
        if current.Value == value {
            prev.Next = current.Next
            return true
        }

        prev = current
        current = current.Next
    }

    return false
}

// Len 统计链表长度。
// 单向链表不像切片那样直接记录长度，所以要逐个节点遍历统计。
func (l *LinkedList) Len() int {
    count := 0
    current := l.Head

    for current != nil {
        count++
        current = current.Next
    }

    return count
}

// 此方法，性能很低
// ToSlice 把链表数据转成切片，方便打印和观察结果。
func (l *LinkedList) ToSlice() []int {
    result := make([]int, 0)
    current := l.Head

    for current != nil {
        result = append(result, current.Value)
        current = current.Next
    }

    return result
}

双向链表

重要

不再补充方法，可以根据自己的需要来实现

// DoublyNode 表示双向链表中的一个节点。
// 和单向链表不同，双向链表中的每个节点既知道下一个节点，
// 也知道上一个节点，所以可以双向移动。
type DoublyNode struct {
    Value int
    Prev  *DoublyNode
    Next  *DoublyNode
}

// DoublyLinkedList 表示一个双向链表。
// Head 指向头节点，Tail 指向尾节点。
// Length 用来记录链表长度，避免每次都遍历统计。
type DoublyLinkedList struct {
    Head   *DoublyNode
    Tail   *DoublyNode
    Length int
}

环

type Ring struct {
	next, prev *Ring
	Value      any // for use by client; untouched by this library
}

func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next returns the next ring element. r must not be empty.
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev returns the previous ring element. r must not be empty.
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
// in the ring and returns that ring element. r must not be empty.
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}