Связанные списки подробно с примерами Python: Одиночные связанные списки

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

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

Что такое Связанный список?

Прежде чем мы изучим, что такое связанные списки, давайте сначала кратко рассмотрим, как массивы хранят данные. В массивах данные хранятся в смежных ячейках памяти. Например, если первый элемент массива хранится в индексе 10 памяти и имеет размер 15 байт, то второй элемент будет храниться в индексе index. Поэтому пересечь массив очень просто.

Чтобы найти третий элемент в массиве, вы можете просто использовать начальный индекс первого элемента, плюс размер первого элемента, плюс размер второго элемента, плюс 1.

Как Связанные Списки Хранят Данные

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

Например, если узел состоит из 34/10, это означает, что значение узла равно 30, а следующий элемент хранится в ячейке памяти “10”. Чтобы пройти по связанному списку, вам просто нужно знать местоположение памяти или ссылку на первый узел, остальные узлы могут быть последовательно пройдены, используя ссылку на следующий элемент в каждом узле.

Ссылка на первый узел также известна как начальный узел.

Связанные списки против массивов:

Связанный список-это динамическая структура данных, которая означает, что память, зарезервированная для списка ссылок, может быть увеличена или уменьшена во время выполнения. Для структуры данных связанного списка заранее не выделяется память. Всякий раз, когда требуется добавить новый элемент в связанный, память для нового узла создается во время выполнения. С другой стороны, в случае массива память должна быть заранее выделена для определенного количества элементов. В тех случаях, когда недостаточно элементов для заполнения всего индекса массива, пространство памяти тратится впустую.
Поскольку массивы требуют смежных ячеек памяти, очень трудно удалить или вставить элемент в массив, поскольку ячейки памяти большого числа элементов должны быть обновлены. С другой стороны, элементы связанных списков не хранятся в смежной области памяти, поэтому вы можете легко обновлять связанные списки.
Благодаря своей гибкости связанный список более подходит для реализации таких структур данных, как стеки, очереди и списки.

Однако у связанного списка есть и некоторые недостатки.

Поскольку каждый элемент связанного списка должен хранить ссылку на следующий элемент, требуется некоторая дополнительная память.
В отличие от массивов, где вы можете получить прямой доступ к элементу, вы не можете получить прямой доступ к элементу связанного списка, поскольку единственная имеющаяся у вас информация-это ссылка на первый элемент. В терминах Big O наихудшее время доступа равно O(n).

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

Единый связанный список
Двусвязный список
Круговой Связанный список
Связанный список с заголовком
Сортированный Связанный список

В этой первой части статьи мы сосредоточимся на одном связанном списке и его различных операциях.

Создание класса Node Создание класса Single Linked List Обход элементов Связанного списка Вставка элементов Подсчет элементов Поиск элементов Создание связанного списка Удаление элементов Реверсирование связанного списка

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

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

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

Создание класса Node

Первое, что вам нужно сделать, это создать класс для узлов. Объектами этого класса будут фактические узлы, которые мы вставим в наш связанный список. Мы знаем, что узел для одного связанного списка содержит элемент и ссылку на следующий узел. Поэтому наш класс node будет содержать две переменные-члена item и ref . Значение item будет задано значением, переданным через конструктор, в то время как ссылка будет изначально установлена в null.

Выполните следующий сценарий:

class Node:
    def __init__(self, data):
        self.item = data
        self.ref = None

Создание класса единого связанного списка

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

class LinkedList:
    def __init__(self):
        self.start_node = None

Теперь мы создали класс для нашего единого списка. Следующий шаг-добавить функцию вставки для вставки элементов в связанный список. Но перед этим мы добавим функцию для обхода связанного списка. Эта функция поможет нам прочитать данные в нашем списке.

Обход Элементов Связанного Списка

Код Python для функции traverse выглядит следующим образом. Добавьте приведенную ниже функцию в класс LinkedList , который мы создали в предыдущем разделе.

def traverse_list(self):
    if self.start_node is None:
        print("List has no element")
        return
    else:
        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Давайте посмотрим, что происходит в приведенной выше функции. Эта функция состоит из двух основных частей. Во – первых, он проверяет, является ли связанный список пустым или нет. Следующий код проверяет это:

  if self.start_node is None:
        print("List has no element")
        return

Если связанный список пуст, это означает, что нет элемента для итерации. В таких случаях функция traverse_list() просто выводит утверждение о том, что в списке нет элемента.

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

    n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

Как мы уже говорили ранее, переменная start будет содержать ссылку на первые узлы. Поэтому мы инициализируем переменную n с помощью переменной start . Затем мы выполняем цикл, который выполняется до тех пор, пока n не станет none. Внутри цикла мы печатаем элемент, хранящийся в текущем узле , а затем устанавливаем значение переменной n в n.ref , которое содержит ссылку на следующий узел. Ссылка на последний узел-это None , так как после этого узла нет. Поэтому, когда n становится None , цикл завершается.

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

Вставка элементов

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

Вставка элементов в начале

Самый простой способ вставить элемент в один связанный список-это добавить элемент в начало списка. Следующая функция вставляет элемент в начало списка. Добавьте эту функцию в класс LinkedList , который мы создали ранее.

    def insert_at_start(self, data):
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node= new_node

В приведенном выше скрипте мы создаем метод insert_at_start () , метод принимает один параметр , который в основном является значением элемента, который мы хотим вставить. Внутри метода мы просто создаем объект класса Node и устанавливаем его ссылку на start_node так как start_node ранее хранил первый узел, который после вставки нового узла в начале станет вторым узлом.

Поэтому мы добавляем ссылку start_node в переменную ref нового узла. Теперь, поскольку new_node является первым узлом, мы устанавливаем значение переменной start_node в new_node .

Вставка элементов в конце

Следующая функция используется для добавления элемента в конец связанного списка.

  def insert_at_end(self, data):
        new_node = Node(data)
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

В приведенном выше скрипте мы создаем функцию insert_at_end() , которая вставляет элемент в конец связанного списка. Значение элемента, который мы хотим вставить, передается в качестве аргумента функции. Функция состоит из двух частей. Сначала мы проверяем, пуст ли связанный список или нет, если связанный список пуст, все, что нам нужно сделать, это установить значение переменной start_node в new_node object.

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

Добавьте функцию insert_at_end() в класс LinkedList .

Вставка элемента после другого элемента

Возможно, нам придется добавлять один элемент за другим в один связанный список. Для этого мы можем использовать функцию insert_after_item () , как определено ниже:

    def insert_after_item(self, x, data):

        n = self.start_node
        print(n.ref)
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

Функция insert_after_item() принимает два параметра: x и data . Первый параметр-это элемент, после которого вы хотите вставить новый узел, а второй параметр содержит значение для нового узла.

Начнем с создания новой переменной n и присвоения ей переменной start_node . Затем мы проходим через связанный список, используя цикл while. Цикл while выполняется до тех пор, пока n не станет None . Во время каждой итерации мы проверяем, равно ли значение, хранящееся в текущем узле, значению, переданному параметром x . Если сравнение возвращает true, мы разрываем цикл.

Далее, если элемент найден, переменная n не будет None . Ссылка на new_node устанавливается в ссылку, хранящуюся в n , а ссылка на n устанавливается в new_node . Добавьте функцию insert_after_item() в класс Linkedlist .

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

    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List has no element")
            return

        if x == self.start_node.item:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
            return

        n = self.start_node
        print(n.ref)
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
        if n.ref is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

В приведенном выше скрипте мы определяем функцию insert_before_item () . Эта функция состоит из трех частей. Давайте рассмотрим каждую часть в деталях.

     if self.start_node is None:
        print("List has no element")
        return

В приведенном выше сценарии мы проверяем, пуст ли список. Если он на самом деле пуст, мы просто печатаем, что в списке нет элемента, и возвращаемся из функции.

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

     if x == self.start_node.item:
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node = new_node
        return

Если элемент, после которого мы хотим вставить новый узел, находится в первом индексе. Мы просто устанавливаем ссылку вновь вставленного узла на start_node , а затем устанавливаем значение start_node в new_node .

Наконец, если список не None и элемент не найден в первом индексе, мы создаем новую переменную n и присваиваем ей переменную start_node . Затем мы проходим через связанный список, используя цикл while. Цикл while выполняется до тех пор, пока n.ref не станет None . Во время каждой итерации мы проверяем, равно ли значение, хранящееся в ссылке текущего узла, значению, переданному параметром x . Если сравнение возвращает true, мы разрываем цикл.

Далее, если элемент найден, переменная n.ref не будет None . Ссылка new_node устанавливается на ссылку n , а ссылка n устанавливается на new_node . Посмотрите на следующий сценарий:

    if n.ref is None:
        print("item not in the list")
    else:
        new_node = Node(data)
        new_node.ref = n.ref
        n.ref = new_node

Добавьте функцию insert_before_item() в класс LinkedList .

Вставка элемента в определенный индекс

Иногда нам нужно вставить элемент в определенный индекс, мы можем сделать это с помощью следующего скрипта:

    def insert_at_index (self, index, data):
        if index == 1:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
        i = 1
        n = self.start_node
        while i < index-1 and n is not None:
            n = n.ref
            i = i+1
        if n is None:
            print("Index out of bound")
        else: 
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

В скрипте мы сначала проверяем, равен ли индекс, в который мы хотим сохранить элемент, 1, затем просто назначаем start_node ссылке на new_node , а затем устанавливаем значение start_node в new_node .

Затем выполните цикл while, который выполняется до тех пор, пока счетчик i не станет больше или равен index-1 . Например, если вы хотите добавить новый узел в третий индекс. Во время первой итерации цикла while i станет 2, а текущий итерационный узел будет равен “2”. Цикл не будет выполняться снова, так как i теперь равен 2, что равно индексу-1). Поэтому петля разорвется. Затем мы добавляем новый узел после текущего итерационного узла (который является узлом 2), следовательно, новый узел добавляется в индекс.

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

Тестирование Функций Вставки

Теперь мы определили все наши функции вставки, давайте их протестируем.

Сначала создайте объект класса связанного списка следующим образом:

new_linked_list = LinkedList()

Затем давайте сначала вызовем функцию insert_at_end () , чтобы добавить три элемента в связанный список. Выполните следующий сценарий:

new_linked_list.insert_at_end(5)
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(15)

Чтобы увидеть, действительно ли элементы были вставлены, давайте пройдемся по связанному списку с помощью функции traverse.

new_linked_list.traverse_list()

Вы должны увидеть следующий вывод:

5
10
15

Далее, давайте добавим элемент в начале:

new_linked_list.insert_at_start(20)

Теперь, если вы пройдете по списку, вы увидите следующий вывод:

Давайте добавим новый пункт 17 после пункта 10:

new_linked_list.insert_after_item(10, 17)

Обход списка теперь возвращает следующий вывод:

Вы можете увидеть 17 вставленных после 10.

Теперь давайте вставим еще один элемент 25 перед элементом 17, используя функцию insert_before_item () , как показано ниже:

new_linked_list.insert_before_item(17, 25)

Теперь список будет содержать следующие элементы:

Наконец, давайте добавим элемент в третьем месте, которое в настоящее время занято 10. Вы увидите, что 10 переместится на одно место вперед, и новый элемент будет вставлен на его место. Для этой цели можно использовать функцию insert_at_index () . Следующий скрипт вставляет элемент 8 у индекса третий индекс списка.

new_linked_list.insert_at_index(3,8)

Теперь, если вы пройдете по списку, вы увидите следующий вывод:

И с этим мы протестировали все наши функции вставки. В настоящее время в нашем списке есть 7 элементов. Давайте напишем функцию, которая возвращает количество элементов в связанном списке.

Счетные элементы

Следующая функция подсчитывает общее количество элементов.

    def get_count(self):
        if self.start_node is None:
            return 0;
        n = self.start_node
        count = 0;
        while n is not None:
            count = count + 1
            n = n.ref
        return count

В приведенном выше скрипте мы создаем функцию get_count() , которая просто подсчитывает количество элементов в связанном списке. Функция просто проходит через все узлы массива и увеличивает счетчик с помощью цикла while. В конце цикла счетчик содержит общее количество элементов в цикле.

Добавьте приведенную выше функцию в класс LinkedList , скомпилируйте класс LinkedList и затем вставьте некоторые элементы в LinkedList , как мы сделали в предыдущем разделе. К концу последнего раздела в нашем связанном списке было 7 пунктов.

Давайте используем функцию get_count () , чтобы получить общее количество элементов в списке:

new_linked_list.get_count()

Вы должны увидеть количество элементов в вашем связанном списке в выходных данных.

В качестве альтернативы другим способом получения “количества” списка было бы отслеживание количества элементов, вставленных и удаленных из списка, в простой переменной счетчика, принадлежащей классу LinkedList . Это работает хорошо и быстрее, чем метод get_count выше, если базовая структура данных списка не может быть обработана извне класса.

Поиск Элементов

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

Сценарий для search_item() выглядит следующим образом:

    def search_item(self, x):
        if self.start_node is None:
            print("List has no elements")
            return
        n = self.start_node
        while n is not None:
            if n.item == x:
                print("Item found")
                return True
            n = n.ref
        print("item not found")
        return False

Добавьте вышеуказанную функцию в класс LinkedList . Давайте поищем элемент в ранее созданном списке. Выполните следующий сценарий:

new_linked_list.search_item(5)

Поскольку мы вставили 5 в наш связанный список, приведенная выше функция вернет true. Результат будет выглядеть следующим образом:

Item found
True

Создание связанного списка

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

    def make_new_list(self):
        nums = int(input("How many nodes do you want to create: "))
        if nums == 0:
            return
        for i in range(nums):
            value = int(input("Enter the value for the node:"))
            self.insert_at_end(value)

В приведенном выше сценарии функция make_new_list() сначала запрашивает у пользователя количество элементов в списке. Затем с помощью цикла for пользователю предлагается ввести значение для каждого узла, которое затем вставляется в связанный список с помощью функции insert_at_end () .

На следующем снимке экрана показана функция make_new_list() в действии.

Удаление Элементов

В этом разделе мы рассмотрим различные способы удаления элемента из одного связанного списка.

Удаление с самого начала

Удалить элемент или элемент из начала связанного списка очень просто. Мы должны установить ссылку start_node на второй узел, что мы можем сделать, просто присвоив значение ссылки начального узла (который указывает на второй узел) стартовому узлу, как показано ниже:

    def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        self.start_node = self.start_node.ref

В приведенном выше сценарии мы сначала проверяем, пуст ли список или нет. Если список пуст, мы выводим сообщение о том, что в списке нет элемента для удаления. В противном случае мы присваиваем значение start_node.ref параметру start_node . Теперь start_node будет указывать на второй элемент. Добавьте функцию delete_at_start() в класс LinkedList .

Удаление в конце

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

Сценарий для функции delete_at_end выглядит следующим образом:

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return

        n = self.start_node
        while n.ref.ref is not None:
            n = n.ref
        n.ref = None

Добавьте приведенный выше скрипт в класс LinkedList () .

Удаление по значению элемента

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

  def delete_element_by_value(self, x):
    if self.start_node is None:
        print("The list has no element to delete")
        return

    # Deleting first node 
    if self.start_node.item == x:
        self.start_node = self.start_node.ref
        return

    n = self.start_node
    while n.ref is not None:
        if n.ref.item == x:
            break
        n = n.ref

    if n.ref is None:
        print("item not found in the list")
    else:
        n.ref = n.ref.ref

В приведенном выше сценарии мы сначала проверяем, пуст ли список. Далее мы проверяем, находится ли удаляемый элемент в начале связанного списка. Если элемент найден в начале, мы удаляем его, установив первый узел на ссылку первого узла (который в основном относится ко второму узлу).

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

Тестирование Функций Удаления

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

new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(20)
new_linked_list.insert_at_end(30)
new_linked_list.insert_at_end(40)
new_linked_list.insert_at_end(50)

Приведенный выше скрипт вставляет 5 элементов в связанный список. Если вы пройдете по списку, то увидите следующие пункты:

Давайте сначала удалим элемент с самого начала:

new_linked_list.delete_at_start()

Теперь, если вы пройдете по списку, вы увидите следующий вывод:

Теперь давайте удалим элемент из конца:

new_linked_list.delete_at_end()

Теперь список содержит следующие пункты:

20
30
40

Наконец, давайте удалим элемент по значению, скажем, 30.

new_linked_list.delete_element_by_value(30)

Теперь, если вы пройдете по списку, вы не увидите пункт 30.

Реверсирование связанного списка

Чтобы перевернуть связанный список, вам нужно иметь три переменные: prev , n и next . prev будет отслеживать предыдущий узел, next будет отслеживать следующий узел, n будет соответствовать текущему узлу.

Мы начинаем цикл while, назначая начальный узел переменной n , а переменная prev инициализируется значением none. Цикл выполняется до тех пор, пока n не станет none. Внутри цикла while вам нужно выполнить следующие функции.

Назначьте значение ссылки текущего узла на next .
Установите значение ссылки текущего узла n на предыдущий
Установите prev переменную в текущий узел n .
Установите текущий узел n в значение next node.

В конце цикла переменная prev будет указывать на последний узел, нам нужно сделать его первым узлом, поэтому мы устанавливаем значение переменной self.start_node в prev . Цикл while приведет к тому, что каждый узел будет указывать на свой предыдущий узел, что приведет к обратному связанному списку. Сценарий выглядит следующим образом:

    def reverse_linkedlist(self):
        prev = None
        n = self.start_node
        while n is not None:
            next = n.ref
            n.ref = prev
            prev = n
            n = next
        self.start_node = prev

Добавьте вышеуказанную функцию в класс LinkedList . Создайте связанный список случайных чисел, а затем посмотрите, можно ли его реверсировать с помощью функции reverse_linked list () .

Вывод

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

Это часть 1 серии статей из связанного списка. В следующей части ( скоро будет ) мы увидим, как сортировать один связанный список, как объединять отсортированные связанные списки и как удалять циклы из одного связанного списка.

Связанные списки подробно с примерами Python: Одиночные связанные списки

Что такое Связанный список?

Как Связанные Списки Хранят Данные

Связанные списки против массивов:

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

Создание класса Node

Создание класса единого связанного списка

Обход Элементов Связанного Списка

Вставка элементов

Вставка элементов в начале

Вставка элементов в конце

Вставка элемента после другого элемента

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

Вставка элемента в определенный индекс

Тестирование Функций Вставки

Счетные элементы

Поиск Элементов

Создание связанного списка

Удаление Элементов

Удаление с самого начала

Удаление в конце

Удаление по значению элемента

Тестирование Функций Удаления

Реверсирование связанного списка

Вывод

Читайте ещё по теме: