Односвязный список положительных целых чисел - это линейная структура данных, в которой один элемент данных указывает на другой, но не наоборот. Это создает список элементов, проходимый в одном направлении.
Переменная, указывающая на первый элемент, называется заголовком списка. Обход связанного списка начинается с заголовка и продолжается до тех пор, пока не останется элементов, на которые можно было бы указать.
Переменная, указывающая на последний элемент, называется хвостом списка. Хвост помогает отслеживать последний узел и упрощает добавление новых элементов в список.
Шаг 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: Стеки - на ходу!