Go реализует двусвязный список

В этой статье рассказывается, что такое связанный список, каковы общие связанные списки, а затем рассказывается, где можно использовать структуру данных связанного списка, а очередь Redis является базовой реализацией, посредством небольшого примера, демонстрирующего функции очереди Redis. и, наконец, через Go Implement двусвязный список.

содержание

1. Связанный список
- 1.1 Описание
- 1.2 Односвязный список
- 1.3 Круговой связанный список
- 1.4 Двусвязный список
2. Очередь Redis
- 2.1 Описание
- 2.2 Сценарии применения
- 2.3 Демонстрация
3. Перейти к двусвязному списку
- 3.1 Описание
- 3.2 Реализация
4. Резюме
5. Ссылки

1. Связанный список

1.1 Описание

Связный список — это общая базовая структура данных, это линейный список, но он хранит данные не в линейном порядке, а хранит указатель (Pointer) на следующий узел в каждом узле. Поскольку его не нужно хранить по порядку, связанный список может достичь сложности O (1) при вставке, что намного быстрее, чем другой последовательный список линейного списка, но для поиска узла или доступа к определенному элементу требуется O (n). число узлов время, а соответствующая временная сложность последовательной таблицы составляет O (logn) и O (1) соответственно.

Существует множество различных типов связанных списков: односвязные списки, двусвязные списки и круговые связанные списки.

Преимущество:

Это может преодолеть недостаток, заключающийся в том, что связанный список массива должен знать размер данных заранее, а структура связанного списка может полностью использовать пространство памяти компьютера и реализовать гибкое управление динамической памятью. Связанные списки позволяют вставлять и удалять узлы в любом месте списка.

Недостаток:

Поскольку связанный список увеличивает указатель узла, накладные расходы пространства относительно велики. Как правило, при поиске данных в связанном списке необходимо каждый раз посещать следующий узел от первого узла до тех пор, пока не будет достигнута требуемая позиция, что относительно медленно для поиска данных.

использовать:

Он часто используется для организации меньшего количества запросов, но для удаления, добавления и просмотра большего количества данных.

Например: файловая система, кэш LRU, список Redis, управление памятью и т. д.

1.2 Односвязный список

Самый простой тип связанного списка — это односвязный список.

Узлы односвязного списка делятся на две части. Он содержит два поля, информационное поле и поле указателя. Первая часть содержит или отображает информацию об узле, вторая часть хранит адрес следующего узла, а последний узел указывает на нулевое значение. Односвязный список можно пройти только в одном направлении.

Односвязный список имеет заголовок головного узла, который указывает на первый адрес связанного списка в памяти. Тип данных каждого узла в связанном списке является типом структуры, и узел имеет два члена: целочисленный член (данные, которые фактически необходимо сохранить) и указатель на следующий узел типа структуры, то есть адрес следующего узла (на самом деле, этот односвязный список представляет собой динамический массив, используемый для хранения целочисленных данных). Доступ к каждому узлу связанного списка в соответствии с этой структурой должен быть найден из головы связанного списка, а адрес последующего узла задается текущим узлом. Независимо от того, какой узел посещается в списке, он должен начинаться с головы связанного списка и выполнять поиск в обратном порядке. Поскольку хвостовой узел связанного списка не имеет последующих узлов, его поле указателя пусто и записывается как NULL.

1.3 Круговой связанный список

Циклический связанный список аналогичен односвязному списку и образует циклическую цепочку.

Работа циклического связанного списка в основном такая же, как у односвязного списка. Различия заключаются в следующем:

1. При создании кругового связанного списка указатель последнего узла должен указывать на узел заголовка, а не устанавливаться в NULL, как в односвязном списке.

2. При оценке того, достигнут ли конец таблицы, необходимо определить, является ли значение поля цепочки узла узлом заголовка.Когда значение поля цепочки равно указателю заголовка, это означает, что достигнут конец таблицы. Вместо того, чтобы судить, является ли значение поля цепочки NULL, как односвязный список.

1.4 Двусвязный список

Двусвязный список на самом деле является усовершенствованием односвязного списка.Когда мы работаем с односвязным списком, иногда, когда вы хотите работать с прямым предшественником узла, вы должны начать поиск с головы. Это ограничено структурой односвязных узлов списка. Поскольку каждый узел односвязного списка имеет только один домен ссылок, в котором хранится адрес непосредственного узла-преемника, можем ли мы определить домен ссылок, в котором хранится как адрес непосредственного узла-преемника, так и домен ссылок, в котором хранится адрес непосредственного узла-преемника. узел-предшественник? Это двусвязный список.

В двусвязном списке помимо поля данных узел имеет два поля цепочки, в одном хранится адрес непосредственного узла-преемника, который обычно называется полем правой цепочки (когда это «соединение» является последним «соединением» , оно указывает на пустое значение или пустой список); адрес узла-предшественника хранилища, обычно называемый левым полем цепочки (когда это «соединение» является первым «соединением», оно указывает на нулевое значение или пустой список).

2. Очередь Redis

2.1 Описание

Списки Redis — это простые списки строк, отсортированные по порядку вставки. Вы можете добавить элемент в начало (слева) или хвост (справа) списка

Список Redis использует две структуры данных в качестве базовой реализации: двусторонний список (linkedlist), сжатый список (ziplist).

Какая реализация выбирается файлом конфигурации (list-max-ziplist-entries, list-max-ziplist-value)

Когда объем данных относительно невелик, разница в производительности между использованием двустороннего связанного списка и сжатого списка незначительна, но использование сжатого списка может сэкономить больше места в памяти.

Исходный код реализации связанного списка redisredis src/adlist.h

2.2 Сценарии применения

Очередь сообщений, убить проект за секунды

Спайк проект:

Заранее сохраните необходимую информацию о коде продукта в очереди Redis, и каждый пользователь извлечет код продукта из очереди Redis во время панической покупки.Поскольку Redis является однопоточным, одновременно можно извлечь только один код продукта. имеет успех при покупке, а производительность Redis относительно высока, что позволяет выдерживать большее давление пользователей.

2.3 Демонстрация

Как предотвратить перепроданность товаров в параллельных ситуациях через очередь Redis.

Предполагать:

На сайте есть три товара для продажи, мы храним данные в очереди Redis.

1. Сохраните три товарных кода (10001, 10002, 10003) в очереди Redis.

# 存入商品
RPUSH commodity:queue 10001 10002 10003

2. После сохранения проверьте, соответствуют ли данные ожиданиям

# 查看全部元素
LRANGE commodity:queue 0 -1

# 查看队列的长度
LLEN commodity:queue

3. Когда начнется срочная покупка, получите код продукта, и пользователь, получивший код продукта, сможет его купить (поскольку Redis является однопоточным, один и тот же код продукта можно получить только один раз). )

# 出队
LPOP commodity:queue

Узнайте, как используется список Redis здесь.Давайте реализуем двусвязный список на языке Go для реализации этих функций.

3. Перейти к двусвязному списку

3.1 Описание

Это просто реализация двусвязного списка на языке Go для достижения: запроса длины связанного списка, вставки данных в правый конец связанного списка, выборки данных с левого конца и получения узлов указанного интервала ( аналогично функциям RPUSH, LRANGE, LPOP, LLEN в списке Redis).

3.2 Реализация

Определение узла

Двусвязный список имеет два указателя, указывающих на предыдущий узел и следующий узел соответственно.

заголовок связанного спискаprevУказатель пустой, конец связанного спискаnextуказатель нулевой

// 链表的一个节点
type ListNode struct {
    prev  *ListNode // 前一个节点
    next  *ListNode // 后一个节点
    value string    // 数据
}

// 创建一个节点
func NewListNode(value string) (listNode *ListNode) {
    listNode = &ListNode{
        value: value,
    }

    return
}

// 当前节点的前一个节点
func (n *ListNode) Prev() (prev *ListNode) {
    prev = n.prev

    return
}

// 当前节点的前一个节点
func (n *ListNode) Next() (next *ListNode) {
    next = n.next

    return
}

// 获取节点的值
func (n *ListNode) GetValue() (value string) {
    if n == nil {

        return
    }
    value = n.value

    return
}

определить связанный список

Для удобства работы связанный список определяет структуру, к которой можно получить доступ непосредственно из верхнего и нижнего колонтитула, и определяет атрибутlen, вы можете напрямую вернуть длину связанного списка и напрямую запросить длину связанного списка, не преодолевая временную сложность от O (n) до O (1).

// 链表
type List struct {
    head *ListNode // 表头节点
    tail *ListNode // 表尾节点
    len  int       // 链表的长度
}


// 创建一个空链表
func NewList() (list *List) {
    list = &List{
    }
    return
}

// 返回链表头节点
func (l *List) Head() (head *ListNode) {
    head = l.head

    return
}

// 返回链表尾节点
func (l *List) Tail() (tail *ListNode) {
    tail = l.tail

    return
}

// 返回链表长度
func (l *List) Len() (len int) {
    len = l.len

    return
}

Вставить элемент справа от связанного списка

// 在链表的右边插入一个元素
func (l *List) RPush(value string) {

    node := NewListNode(value)

    // 链表未空的时候
    if l.Len() == 0 {
        l.head = node
        l.tail = node
    } else {
        tail := l.tail
        tail.next = node
        node.prev = tail

        l.tail = node
    }

    l.len = l.len + 1

    return
}

Возьмите узел из левой части связанного списка

// 从链表左边取出一个节点
func (l *List) LPop() (node *ListNode) {

    // 数据为空
    if l.len == 0 {

        return
    }

    node = l.head

    if node.next == nil {
        // 链表未空
        l.head = nil
        l.tail = nil
    } else {
        l.head = node.next
    }
    l.len = l.len - 1

    return
}

Найти узел по индексу

Найти узел по индексу, если индекс отрицательный, начать поиск с конца таблицы.

Существует два способа найти узлы для натурального числа и отрицательного индекса соответственно, и поиск завершается, когда указанный индекс найден или просматривается весь связанный список.

// 通过索引查找节点
// 查不到节点则返回空
func (l *List) Index(index int) (node *ListNode) {

    // 索引为负数则表尾开始查找
    if index < 0 {
        index = (-index) - 1
        node = l.tail
        for true {
            // 未找到
            if node == nil {

                return
            }

            // 查到数据
            if index == 0 {

                return
            }

            node = node.prev
            index--
        }
    } else {
        node = l.head
        for ; index > 0 && node != nil; index-- {
            node = node.next
        }
    }

    return
}

Возвращает элементы указанного диапазона

// 返回指定区间的元素
func (l *List) Range(start, stop int) (nodes []*ListNode) {
    nodes = make([]*ListNode, 0)

    // 转为自然数
    if start < 0 {
        start = l.len + start
        if start < 0 {
            start = 0
        }
    }

    if stop < 0 {
        stop = l.len + stop
        if stop < 0 {
            stop = 0
        }
    }

    // 区间个数
    rangeLen := stop - start + 1
    if rangeLen < 0 {

        return
    }

    startNode := l.Index(start)
    for i := 0; i < rangeLen; i++ {
        if startNode == nil {
            break
        }

        nodes = append(nodes, startNode)
        startNode = startNode.next
    }

    return
}

4. Резюме

На этом использование связанных списков закончено, в нем рассказывается, что такое связанные списки (односвязные списки, двусвязные списки и круговые связанные списки), а также вводятся сценарии применения связанных списков (списки Redis используют связанные списки в качестве базовой реализации). ) и, наконец, реализовать его в Go. Двусвязный список демонстрирует, как связанный список используется в языке Go, и вы можете использовать его в более практической ситуации в проекте.

5. Ссылки

связанный список википедии

github redis

адрес проекта:иди внедряй очередь

GitHub.com/Lincoln1Body/Лим…