Golang container/list链表与队列实现实践-Golang-PHP中文网

Golang container/list链表与队列实现实践

P粉602998670

发布： 2025-09-22 17:43:01

原创

151人浏览过

container/list提供双向链表，支持O(1)插入删除，可用于实现队列、栈等结构，但查找为O(n)，需注意类型断言和并发安全问题。

golang container/list链表与队列实现实践

Go语言标准库中的

container/list

登录后复制

包提供了一个双向链表的实现，可以灵活地用于构建链表、队列、栈等数据结构。它不是泛型（在Go 1.18之前），但通过

interface{}

登录后复制

实现了通用性。下面介绍其基本用法与常见实践场景。

container/list 基本操作

container/list

登录后复制

的核心是一个双向链表结构，每个节点包含前驱和后继指针。通过

List

登录后复制

类型的实例进行操作。

常用方法包括：

list.Init()：初始化或清空列表
list.PushFront(v)：在头部插入元素
list.PushBack(v)：在尾部插入元素
list.Remove(e)：删除指定元素（传入*Element）
list.Front()：返回第一个元素（*Element）
list.Back()：返回最后一个元素（*Element）
e.Next(), e.Prev()：获取下一个或上一个节点

示例：创建链表并遍历

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
}

登录后复制

使用 list 实现队列（FIFO）

队列遵循“先进先出”原则，可以用

PushBack

登录后复制

入队，

Remove(Front())

登录后复制

出队。

立即学习“go语言免费学习笔记（深入）”；

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

简单封装一个队列结构：

type Queue struct {
    list *list.List
}

func NewQueue() *Queue {
    return &Queue{list: list.New()}
}

func (q *Queue) Enqueue(value interface{}) {
    q.list.PushBack(value)
}

func (q *Queue) Dequeue() interface{} {
    if q.list.Len() == 0 {
        return nil
    }
    front := q.list.Front()
    return q.list.Remove(front)
}

func (q *Queue) Len() int {
    return q.list.Len()
}

func (q *Queue) Front() interface{} {
    if q.list.Len() == 0 {
        return nil
    }
    return q.list.Front().Value
}

登录后复制

使用示例：

q := NewQueue()
q.Enqueue("first")
q.Enqueue("second")
fmt.Println(q.Dequeue()) // 输出 first
fmt.Println(q.Dequeue()) // 输出 second

登录后复制

实现栈（LIFO）

栈是“后进先出”，可以用

PushBack

登录后复制

入栈，

Remove(Back())

登录后复制

出栈。

type Stack struct {
    list *list.List
}

func NewStack() *Stack {
    return &Stack{list: list.New()}
}

func (s *Stack) Push(value interface{}) {
    s.list.PushBack(value)
}

func (s *Stack) Pop() interface{} {
    if s.list.Len() == 0 {
        return nil
    }
    back := s.list.Back()
    return s.list.Remove(back)
}

func (s *Stack) Peek() interface{} {
    if s.list.Len() == 0 {
        return nil
    }
    return s.list.Back().Value
}

登录后复制