Определение и пояснение??
Когда мы будем говорить “связный список”, то подразумеваться будет однонаправленный связный список. Чтобы получше понять эту структуру данных, давайте рассмотрим ее отличительные особенности и возможности.
В массиве вы можете обращаться к элементам в произвольном порядке (напрямую), но в связном списке вам придётся перемещаться через все элементы, потому что в нём присутствуют так называемые ссылки (связки). Позже мы рассмотрим, что это означает. Что касается массивов, если вы делаете их динамическими, то возникает много сложностей. В случае же со связным списком всё намного проще, поскольку он растёт динамически.
Представление связного списка
Вот, как он выглядит:
Теперь, давайте разберём эту диаграмму. В ней мы видим 4 рамки, называемые узлами. Каждый узел может обладать двумя характеристиками: значением и связкой, содержащей адрес ячейки памяти следующего узла. В нашей диаграмме первый узел содержит значение 10 и адрес следующего узла 4900 (таким образом он находит в памяти следующий узел).
Первый узел называется Head (голова), а последний Tail (хвост). В последнем узле на приведённой диаграмме адрес указан как null. Это означает, что за ним узла не последует.
Важно помнить при работе с кодом?
В С++ и С элемент, хранящий адрес ячейки памяти, мы называем Pointer (указатель).
В Java, Python его же мы называем Reference (ссылкой).
Для хранения деталей узла в С мы используем Struct (структуры), а в C++, Java или Python — Class (класс).
В C и C++ в последнем узле адрес обозначается как nil (ноль), а в Python как None (нет).
Создание узла
Давайте создадим узел в Python:
При каждом использовании class автоматически вызывается конструктор.
Здесь мы создаём Class под названием Node и добавляем в него конструктор. Поскольку узел может иметь значение и ссылку, то мы соответственно называем эти компоненты value и link. Нужно отметить, что изначально мы определяем link как none, потому что, когда первый узел только создается, для него ещё не существует соседнего узла и, соответственно, адреса в памяти тоже нет ?.
Теперь в строке 7 мы создаём экземпляр этого класса под названием first и передаём его узлу значение 10. При выводе в консоль значения этого узла мы получим 10, а при выводе значения link — none.
Добавление узла
Теперь добавим в связный список узел и отобразим его. Для добавления мы напишем insert_at_beginning в начале списка и insert_at_end в конце.
Обратите внимание: обычно первый узел называется head, но в данном случае вместо head мы используем firstnode. Это не лучший вариант ?, но так нагляднее.
Теперь мы создали для нашего связного списка класс, который будет содержать столько узлов, сколько нам потребуется (Class LinkedList).
В строке 8 мы создаём конструктор. Теперь в коде будет два метода для добавления узлов в начале и в конце. Давайте их рассмотрим:
- В методе insert_at_beginning мы создаём новый узел и проверяем, является ли он первым узлом. При наличии узлов будет выполнена инструкция if, при их отсутствии же будет выполнена инструкция else.
- В методе inser_at_end мы создаём новый узел, и если список при проверке не окажется пуст, то сработает ветка условия if. Чтобы добавить узел в конец списка, потребуется перебрать его весь, поскольку обращаться к узлам напрямую нельзя. Здесь мы применяем перебор посредством цикла while, выполняя в нём проверку обнаружения последнего узла и размещая в итоге за ним новый узел. Если же связный список оказывается пуст, тогда срабатывает инструкция else и узел становится первым.
Компиляция 1
Давайте скомпилируем наш код и попробуем использовать эти методы:
Как и в коде выше, мы вставляем элементы в начало и конец. В итоге наш список должен выглядеть так: 5, 10, 20, 30.
Настал черёд написания метода для отображения этого списка.
Отображение связного списка
Добавляем метод для отображения:
Этот метод сначала будет проверять список на наличие элементов. Если он окажется пуст, будет выводится надпись List empty, в противном случае метод произведёт итерацию и выведет в консоль значения.
Компиляция 2
Давайте выполним компиляцию и используем методы класса LinkedList:
В этом коде мы используем метод display, и наш связный список будет выглядеть так:
Удаление узла
Теперь создадим метод, куда будет передаваться значение элемента, который нужно удалить, и назовём этот метод delete_node.
В этом методе сначала мы проверяем список на наличие элементов. Если он окажется пуст, тогда в консоль выводится LinkedList is Empty. Следующее условие проверяет, является ли удаляемый элемент firstNode. Если да, то удаляется первый узел.
Если же оба условия окажутся неверны, тогда придётся перебрать весь список, чтобы найти удаляемый элемент.
Компиляция 3
Теперь давайте применим этот метод удаления для нашего списка:
В итоге мы получим следующий вывод:
Поиск узлов
Теперь найдем узлы по их значению и создадим для этого метод search.
Добавив этот метод в класс LinkedList, мы вновь сначала проверяем список на наличие элементов. Если он пуст, тогда выводится list is empty, иначе производится его перебор в поиске нужного элемента.
Компиляция 4
Пробуем поиск по нашему списку:
Здесь мы ищем узел со значением 30, и вывод должен получиться следующий:
Недостатки связных списков
- Они используют больше памяти, чем массивы из-за занимаемого их указателями пространства.
- Для получения доступа к нужному узлу необходимо считывать их все по порядку, начиная сначала.
Читайте также:
- 10 трюков для мастеров Python
- 5 любопытных библиотек Python
- Пошаговое построение логистической регрессии в Python
Перевод статьи Mohd Yasir: All About Singly Linked List
