Тип list.List

Тип list.List из пакета container/list представляет собой реализацию двусвязного списка. Он хранит элементы в виде узлов типа list.Element, каждый из которых содержит значение, а также ссылки на предыдущий и следующий элементы. Основное преимущество этой структуры — возможность вставки и удаления элементов за константное время O(1) в любом месте списка, если у вас есть ссылка на соответствующий элемент. Однако доступ к элементу по индексу требует линейного времени O(n), так как список не является массивом.

Тип list.List не имеет методов для прямого доступа по индексу, поэтому для перебора всех элементов необходимо использовать методы получения первого и последнего элемента, а затем переходить по ссылкам. Это делает его идеальным для реализации очередей, стеков, кэшей с политикой LRU (least recently used) и других структур данных, где часто выполняются вставки и удаления.

Для создания нового списка используется функция list.New, которая возвращает инициализированный пустой список. Инициализация также может быть выполнена с помощью метода Init, который очищает список и подготавливает его к использованию.

Синтаксис

import "container/list"

// Создание нового списка
l := list.New()

// Добавление элемента в конец
e := l.PushBack(10)

// Вставка элемента перед указанным
l.InsertBefore(5, e)

// Удаление элемента
l.Remove(e)

// Получение длины списка
length := l.Len()

Пример

Давайте создадим новый список, добавим в него несколько элементов и выведем длину и содержимое:

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	l.PushBack("a")
	l.PushBack("b")
	l.PushBack("c")

	fmt.Println("Length:", l.Len())

	// Перебор элементов
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

Результат выполнения кода:

"Length: 3"
"a"
"b"
"c"

Пример

Теперь давайте вставим элемент в середину списка с помощью метода InsertAfter:

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	e1 := l.PushBack("a")
	e2 := l.PushBack("c")

	// Вставляем "b" после первого элемента
	l.InsertAfter("b", e1)

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

Результат выполнения кода:

"a"
"b"
"c"

Пример

Удалим элемент из середины списка, используя метод Remove. Метод возвращает значение удаленного элемента:

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	e1 := l.PushBack("a")
	e2 := l.PushBack("b")
	l.PushBack("c")

	removed := l.Remove(e2)
	fmt.Println("Removed:", removed)

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

Результат выполнения кода:

"Removed: b"
"a"
"c"

Смотрите также

функцию list.New,
которая создает новый двусвязный список
метод PushBack,
который добавляет элемент в конец списка
метод PushFront,
который добавляет элемент в начало списка
метод InsertAfter,
который вставляет элемент после указанного