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

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

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

Шаг 1. Общие сведения о сценариях использования

Связанные списки используются следующим образом:

  • Вставить: вставьте узел в конец списка.

  • Поиск: возвращает позицию узла с заданным значением.

  • DeleteVal: удалить узел с заданным значением.
  • DeleteAt: удалить узел с заданной позицией.

  • GetAt: возвращает значение узла в заданной позиции.

Другие варианты использования включают:

  • Связанный список позиционирование элемента начинается с 1
  • Функции Search и GetAt возвращают -1, если такой узел не существует.

Шаг 2. Решите, какие структуры данных использовать

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

Наконец, наш связанный список должен выглядеть так:

Шаг 3. Вспомогательные функции и переменные

Мы создаем следующие вспомогательные функции, чтобы упростить процесс разработки:

  • previousNode: возвращает узел, предшествующий данной позиции. Это особенно полезно для функции удаления. Так как нам нужно обновить ссылку на узел, предшествующий удаленному.
  • insertAfter: вставляет узел после заданного узла.
  • getNode: возвращает узел в заданной позиции.

Шаг 4. Приступим к кодированию

Начните с создания пакета настраиваемого списка, создав папку ‘src / list /’ в GOPATH с файлом list.go.

Не забудьте включить package list в начало файла, чтобы указать пакет.

Базовый блок узла:

Создание экспортируемой структуры связанного списка:

Вспомогательные функции

1. Предыдущий узел:

Чтобы вернуть предыдущий узел в заданную позицию pos, нам нужно пройти узлы pos-2. (Поскольку следующий узел pos-2 даст узел pos-1).

Мы работаем с позициями вне пределов, возвращая head и tail для выхода за левую и правую границы соответственно. Это всего лишь моя собственная реализация, и вы можете решать ее, как хотите.

2. Вставить после:

Эта функция вставляет узел с заданным значением Val после заданного узла ptr. Мы создаем узел temp, в котором хранится это значение Val, а затем, чтобы интегрировать его в связанный список, мы указываем temp.next на ptr.next. Это поддерживает поток связанного списка. А теперь, поскольку узел temp должен стоять после ptr, мы обновляем ptr.next на temp адрес.

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

3. Получите узел:

Вспомогательная функция Get Node просто проходит через узлы и возвращает узел в позиции pos. Если позиция недействительна, мы возвращаем nil.

Функции варианта использования

1. Вставить (значение)

Функция Insert вставляет узел в конец списка. Для связанного списка без данных head будет nil. В противном случае мы вставляем новое значение после хвоста, используя нашу вспомогательную функцию insertAfter. Видеть? Насколько они полезны!

2. Поиск (значение)

Функция поиска возвращает позицию узла с заданным значением, просматривая список. Если желаемый узел не найден, возвращается -1.

3. DeleteAt (позиция)

Функция DeleteAt удаляет узел в заданной позиции.

  • Если данная позиция выходит за пределы - ничего не делать
  • Если голова должна быть удалена, просто обновите указатель головы. В отличие от C, вам не нужно беспокоиться об освобождении предыдущей главы, которую мы только что отсоединили от нашего связанного списка. Go сделает это за вас.
  • Найдите предыдущий узел в позиции - скажите предыдущая. Обновите предыдущая.следующая как предыдущая.следующая.следующая. При этом удаляется нужный узел.

4. DeleteVal

DeleteVal ищет и удаляет первый найденный узел с заданным значением. Это просто реализовать с помощью функций Search и DeleteAt.

5. получить

Функция GetAt возвращает значение узла с учетом его положения. Мы воспользуемся вспомогательной функцией getNode, чтобы получить желаемый узел и вернуть его значение. Если такой узел не существует, мы возвращаем -1.

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

Запуск нашего кода

Создайте файл main.go в GOPATH / src / main и используйте новую структуру данных!

package main
import "list"
import "fmt"
func main(){
    var l list.List
    l.insert(2)
    l.insert(1)
    fmt.Println(l.getAt(2)) //Output: 1
}

Запустите go run main.go, чтобы запустить свой код.

Есть проблемы? загляните в репозиторий Github: Ссылка на Github

Шаг 5: домашнее задание

Попробуйте создать свои собственные функции для этих случаев использования:

  • Печать: печать элементов связанного списка.
  • Реверс: переворачивание связанного списка
  • Повернуть

Приложения

  • Реализация стеков и очередей. (Что мы рассмотрим в будущих уроках)
  • Реализация арифметических операций над длинными целыми числами.
  • Манипулирование многочленами путем сохранения констант в узле связанного списка.

Заключение

Связанные списки - это отличные структуры данных для динамического хранения данных. Мы видели различные способы манипулирования данными в связанном списке - функции вставки, удаления, поиска и получения.

Вот и все, ребята!

Репозиторий Github: Ссылка на Github | Next Up: Стеки - на ходу!