当前位置：首页 > 文章列表 > Golang > Go教程 > Golang链表与队列实现全解析

Golang链表与队列实现全解析

2025-09-29 13:20:28 0浏览收藏

从现在开始，我们要努力学习啦！今天我给大家带来《Golang链表与队列实现详解》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

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())出队。

简单封装一个队列结构：

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
}