Содержание

Понятие односвязного линейного списка и его реализация на языке C

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

Списку можно дать несколько определений. Здесь представлены некоторые из них.

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

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

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

  1. Пустой список является списком
  2. Структура вида [Голова | Хвост] является списком, если голова — первый элемент списка, а хвост — список, состоящий из оставшихся элементов исходного списка

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

Существует несколько видов списка: односвязный линейный список (ОЛС), последовательный линейный список (ПЛС), двусвязный линейный список (ДЛС) и другие. Однако в данной статье будет рассматриваться именно ОЛС.

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

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

Над линейный списком определены следующие операции:

  1. Инициализация
  2. Включение элемента
  3. Исключение элемента
  4. Переход в начало списка
  5. Переход в конец списка
  6. Переход к следующему элементу
  7. Уничтожение списка

При реализации ОЛС в статической памяти располагают дескриптор, состоящий из двух полей:

  1. Указатель на фиктивный элемент
  2. Указатель на текущий элемент

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

P.S. При использовании фиктивного элемента, все операции нужно выполнять после того элемента, на который указывает ptr.

Содержание

  1. Инициализация списка
  2. Включение элемента
  3. Исключение элемента
  4. Файл List_One.h
  5. Файл List_One.c

Инициализация списка

Инициализация происходит в три шага:

  1. Выделение памяти для фиктивного элемента
  2. В дескрипторе указателю start присвоить блок с только что выделенной памятью
  3. Указателю ptr присвоить start.

Поясню, что здесь, и зачем. При инициализации происходит создание списка, но не заполнение его элементами. Создание списка подразумевает создание фиктивного элемента. Так как его поле данных не используется, то список остается по-прежнему пуст. Когда память выделена, остается лишь правильно присвоить ссылки указателям.Код инициализации таков:

Включение элемента

Так как ptr указывает на фиктивный элемент, то новый элемент нужно вставить после него, но перед элементом со значением 5. Прежде чем вставить, нужно выделить память под новый элемент и занести информацию в него. Допустим, мы вставляем элемент с данными — 100.Теперь нужно вставить новый элемент между двумя элементами списка, то есть изменить ссылки, находящиеся в полях ptr.#image.jpgТеперь рассмотрим код операции включения.

Исключение элемента

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

#image.jpgТак как ptr указывает на фиктивный — исключаем первый. Здесь перемычка ссылок немного сложнее, чем в предыдущем примере. Нужно создать временный элемент так, чтобы он был равен исключаемому, т.е. имел один и тот же с ним адрес. Это нужно для того, чтобы не потерять тот элемент, на который исключаемый ссылается.#image.jpgТеперь — перемычка указателей и удаление временного элемента. #image.jpg

Вот и вся операция исключения. Ниже представлен код.

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

Файл List_One.h

Файл List_One.

c

Осталось только добавить, что перечисленные мной операции — далеко не все, которые можно реализовать для списка. Вы сами можете создавать новые. На этом все, если что было не понятно, пишите в комментариях.

использование операций вставки, удаления и переворачивания

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

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

Плюсы и минусы

Ниже приведены некоторые плюсы и минусы двусвязного списка:

Плюсы:

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

Минусы:

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

Реализация

В этом разделе мы увидим, как мы можем создать очень простой двусвязный список в Python. Если вы читали часть 1 и часть 2 этой серии статей, код должен быть довольно простым.

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

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

В приведенном выше коде вы можете видеть, что мы создаем класс Node с тремя переменными-членами: item, nref и pref. Переменная item будет хранить фактические данные для узла. Nref хранит ссылку на следующий узел, а pref сохраняет ссылку на предыдущий узел в двусвязном списке.

Затем нам нужно создать класс DoublyLinkedList, который содержит различные функции, связанные с двусвязным списком Python. Добавьте следующий код:

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

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

Вставка элементов в пустой список

Самый простой способ вставить элемент в двусвязный список – это вставить элемент в пустой список.

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

 def insert_in_emptylist(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("list is not empty")

В приведенном выше скрипте мы определяем метод insert_in_emptylist(). Сначала метод проверяет, имеет ли значение переменной self.start_node значение None или нет. Если переменная равна None, это означает, что список фактически пуст.

Затем создается новый узел, и его значение инициализируется значением, переданным в качестве параметра данных функции insert_in_emptylist(). Наконец, значение переменной self.start_node устанавливается на новый узел. В случае, если список не пустой, пользователю просто отображается сообщение о том, что список не пуст.

Добавьте метод insert_in_emptylist() в созданный вами ранее класс DoublyLinkedList.

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

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

Иначе, если список не пустой, нам нужно выполнить три операции:

  1. Для нового узла ссылка на следующий узел будет установлена на self.start_node.
  2. Для self.start_node ссылка на предыдущий узел будет установлена на вновь вставленный узел.
  3. Наконец, self.start_node станет вновь вставленным узлом.

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

    def insert_at_start(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            print("node inserted")
            return
        new_node = Node(data)
        new_node.nref = self.start_node
        self.start_node.pref = new_node
        self.start_node = new_node

Добавьте метод insert_at_start() в созданный вами ранее класс DoublyLinkedList.

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

Вставка элемента в конец двусвязного списка чем-то похожа на вставку элемента в начало. Сначала нам нужно проверить, пуст ли список. Если список пуст, мы можем просто использовать метод insert_in_emptylist() для вставки элемента. Если список уже содержит какой-то элемент, мы проходим по списку, пока ссылка на следующий узел не станет None. Когда ссылка на следующий узел становится None, это означает, что текущий узел является последним узлом.

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

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

Добавьте метод insert_at_end() в созданный вами ранее класс DoublyLinkedList.

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

Чтобы вставить элемент после другого элемента, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

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

  1. Установите предыдущую ссылку вновь вставленного узла на выбранный узел.
  2. Установите следующую ссылку вновь вставленного узла на следующую ссылку выбранного.
  3. Если выбранный узел не является последним узлом, установите предыдущую ссылку следующего узла после выбранного узла на вновь добавленный узел.
  4. Наконец, установите следующую ссылку выбранного узла на вновь вставленный узел.

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

    def insert_after_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.pref = n
                new_node.nref = n.nref
                if n.nref is not None:
                    n.nref.prev = new_node
                n.nref = new_node

Добавьте метод insert_after_item() в созданный вами ранее класс DoublyLinkedList.

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

Чтобы вставить элемент перед другим элементом, мы сначала проверяем, пуст ли список. Если список действительно пуст, мы просто отображаем сообщение о том, что «список пуст».

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

  1. Установите следующую ссылку вновь вставленного узла на выбранный узел.
  2. Установите предыдущую ссылку вновь вставленного узла на предыдущую ссылку выбранного.
  3. Установите следующую ссылку узла, предшествующего выбранному узлу, на только что добавленный узел.
  4. Наконец, установите предыдущую ссылку выбранного узла на вновь вставленный узел.

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

    def insert_before_item(self, x, data):
        if self. start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.nref = n
                new_node.pref = n.pref
                if n.pref is not None:
                    n.pref.nref = new_node
                n.pref = new_node

Добавьте метод insert_before_item() в созданный вами ранее класс DoublyLinkedList.

Обход двусвязного списка

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

    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.nref

Добавьте метод traverse_list() в созданный вами ранее класс DoublyLinkedList.

Удаление элементов из двусвязного списка

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

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

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

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

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

Добавьте метод delete_at_start() к классу DoublyLinkedList, который вы создали ранее.

Удаление элементов с конца

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

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

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

Добавьте метод delete_at_end() к классу DoublyLinkedList, который вы создали ранее.

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

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

    def delete_element_by_value(self, x):
        if self. start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return 

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

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

Эта логика реализована в следующем фрагменте кода:

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

Затем мы проверяем, есть ли в списке единственный элемент и действительно ли этот элемент является элементом, который мы хотим удалить. Если единственным элементом является тот, который мы хотим удалить, мы просто устанавливаем для self.start_node значение None, что означает, что теперь в списке не будет элемента.

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

Следующий фрагмент кода реализует эту логику:

        if self.start_node.nref is None:
            if self.start_node. item == x:
                self.start_node = None
            else:
                print("Item not found")
            return

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

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

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

  1. Установите значение следующей ссылки предыдущего узла на следующую ссылку удаляемого узла.
  2. Установите предыдущее значение следующего узла на предыдущую ссылку удаляемого узла.

Наконец, если удаляемый узел является последним узлом, для следующей ссылки узла, предшествующего последнему узлу, устанавливается значение «None». Следующий скрипт реализует эту логику:

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

Добавьте метод delete_element_by_value() к классу DoublyLinkedList, который вы создали ранее.

Переворачивание списка

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

  1. Следующая ссылка начального узла должна иметь значение none, потому что первый узел станет последним узлом в обратном списке.
  2. Для предыдущей ссылки последнего узла необходимо установить значение «None», поскольку последний узел станет предыдущим узлом.
  3. Следующие ссылки узлов (кроме первого и последнего узла) в исходном списке должны быть заменены предыдущими ссылками.

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

    def reverse_linked_list(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        p = self.start_node
        q = p.nref
        p.nref = None
        p.pref = q
        while q is not None:
            q.pref = q.nref
            q.nref = p
            p = q
            q = q.pref
        self.start_node = p

Добавьте метод reverse_linked_list() в созданный вами ранее класс DoublyLinkedList.

Тестирование функций двусвязного списка

Сначала создадим объект класса DoublyLinkedList. Выполните следующий скрипт:

new_linked_list = DoublyLinkedList()

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

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

new_linked_list.insert_in_emptylist(50)

Теперь, если вы пройдете по списку, вы должны увидеть 50 как единственный элемент в списке, как показано ниже:

new_linked_list.traverse_list()

Вывод:

50

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

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

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

18
5
10
50

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

new_linked_list. insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

Теперь, если вы пройдете по двусвязному списку, вы должны увидеть следующие элементы:

18
5
10
50
29
39
49

Вставим элемент после 50.

new_linked_list.insert_after_item(50, 65)

Теперь список должен выглядеть так:

18
5
10
50
65
29
39
49

Наконец, давайте добавим элемент перед пунктом 29.

new_linked_list.insert_before_item(29, 100)

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

18
5
10
50
65
100
29
39
49

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

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

new_linked_list.delete_at_start()

Пункт 18 будет удален, и теперь список будет выглядеть так:

5
10
50
65
100
29
39
49

Точно так же следующий скрипт удаляет элемент из конца двусвязного списка:

new_linked_list.delete_at_end()

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

5
10
50
65 
100 
29
39

Наконец, вы также можете удалить элементы по значению, используя функцию delete_element_by_value(), как показано ниже:

new_linked_list.delete_element_by_value(65)

Если вы сейчас пройдете по списку, вы увидите, что элемент 65 будет удален из списка.

Проверка обратной функции

Наконец, давайте перевернем список с помощью функции reverse_linked_list(). Выполните следующий скрипт:

new_linked_list.reverse_linked_list()

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

39
29
100
50
10
5

Заключение

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

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

Подробное руководство по односвязному списку с использованием C++

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

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

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

Независимо от того, сколько узлов присутствует в связанном списке, самый первый узел называется head , а последний узел называется tail . Если создан только один узел, он называется головным и хвостовым.

Поскольку связанный список состоит из узлов, нам нужно объявить структуру, определяющую один узел. В нашей структуре должна быть как минимум одна переменная для раздела данных и указатель на следующий узел. В C++ наш код будет выглядеть так:

 struct node
  {
    внутренние данные;
    узел *следующий;
  };

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

 список классов
  {
    Частный:
    узел *голова, *хвост;
    публичный:
    список()
    {
      голова=НУЛЬ;
      хвост=НУЛЬ;
    }
  };

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

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

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

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

Создание нового узла в конце связанного списка состоит из 2 шагов:

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

Код C++ для создания нового узла будет таким:

 void createnode(int value)
    {
      узел *temp=новый узел;
      темп->данные=значение;
      темп-> следующий = NULL;
      если (голова == NULL)
      {
        голова=температура;
        хвост=темп;
        темп=НУЛЬ;
      }
      еще
      {
        хвост->следующий=temp;
        хвост=темп;
      }
    }

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

Код для отображения узлов связанного списка приведен ниже:

 void display()
  {
    узел *temp=новый узел;
    темп=напор;
    в то время как (темп! = NULL)
    {
      cout<данные<<"\t";
      темп=темп->следующий;
    }
  }

Обе функции createnode() и display() будут написаны в разделе public класса.

Базовая структура односвязного списка готова. Теперь пришло время выполнить некоторые другие операции в списке. В основном над связанными списками выполняются две операции:

  1. Вставка
  2. Удаление

Вставка

Вставка нового узла в связанный список называется вставкой.

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

При вставке узла учитываются три случая:

  1. Вставка в начале
  2. Вставка в конце
  3. Вставка в определенную позицию
Вставка в начале

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

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

Схематическая демонстрация этого процесса приведена ниже:

Код для этого процесса:

 void insert_start(int value)
  {
    узел *temp=новый узел;
    темп->данные=значение;
    темп->следующий=голова;
    голова=температура;
  }
Вставка в конец

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

Вставка в определенную позицию

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

Теперь новый узел можно вставить между предыдущим и текущим узлами, выполнив всего два шага:

  1. Передать адрес нового узла в поле next предыдущего узла.
  2. Передать адрес текущего узла в поле next нового узла.

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

Код C++ для вставки узла будет следующим:

 void insert_position(int pos, int value)
  {
    узел *pre=новый узел;
    узел *cur=новый узел;
    узел *temp=новый узел;
    кур = голова;
    for(int i=1;iследующий;
    }
    темп->данные=значение;
    пре->следующий=temp;
    темп->следующий=курс;
  }

Удаление:

Итак, вы познакомились с созданием связанных списков. Теперь пришло время немного поработать с созданным связанным списком. Связанные списки предоставляют нам замечательную возможность удаления узла. Процесс удаления также прост в реализации. Базовая структура заключается в объявлении временного указателя, указывающего на удаляемый узел. Затем немного поработаем над ссылками узлов. Есть также три случая, когда узел может быть удален:

  1. Удаление в начале
  2. Удаление в конце
  3. Удаление в определенной позиции
Удаление в начале

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

  1. Объявить указатель temp и передать адрес первого узла, т.е. перейти к этому указателю.
  2. Объявить второй узел списка головным, так как он будет первым узлом связанного списка после удаления.
  3. Удалить временный узел.

Код C++ для этого процесса приведен ниже:

 void delete_first()
  {
    узел *temp=новый узел;
    темп=напор;
    голова=голова->следующая;
    удалить темп;
  }
Удаление в конце

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

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

 недействительным delete_last()
  {
    узел *текущий=новый узел;
    узел *предыдущий=новый узел;
    ток=напор;
    в то время как (текущий-> следующий! = NULL)
    {
      предыдущий=текущий;
      текущий=текущий->следующий;
    }
    хвост = предыдущий;
    предыдущий->следующий=NULL;
    удалить текущий;
  }
Удаление в определенной позиции

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

Удаление может быть выполнено на C++ с помощью приведенного ниже кода:

 void delete_position(int pos)
  {
    узел *текущий=новый узел;
    узел *предыдущий=новый узел;
    ток=напор;
    for(int i=1;iследующий;
    }
    предыдущий->следующий=текущий->следующий;
  }

Я сделал для вас полный проект связанного списка. Он выполняет все описанные выше функции. Вы можете скачать его с этого Github. Вот скриншот его вывода:

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

Биография автора

Камаль Чоудхари (Kamal Choudhary) — технарь, который пишет учебные пособия по программированию на C++ для начинающих. Он изучает информатику в Университете Гуджрата, Пакистан. Он любит писать о компьютерном программировании. Вы можете найти его полную биографию здесь. Подпишитесь на него в Твиттере: @ikamalchoudhary

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

Изучение того, как с нуля писать объекты Linked List и Node с помощью Python 02 ·

6 мин чтения

·

20 декабря 2021 г.

Photo by Mael BALLAND on Unsplash

Введение

Связанные списки являются одной из наиболее фундаментальных структур данных, которые представляют собой последовательность узлов . Первый элемент последовательности называется 9.0007 head связанного списка, а последний элемент соответствует tail .

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

Односвязный список — Источник: Автор

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

Двусвязный список — Источник: Автор

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

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

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

Реализация определяемого пользователем класса связанных ссылок в Python

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

 class Node: 
 def __init__(self, value, next_node=None, prev_node=None): 
 self.value = value 
 self.next = next_node 
 self.prev = prev_node 
 def __str__(self): 
 return str (self.value)

Обратите внимание, что когда экземпляр Node имеет next , установленный на None , это означает, что он по существу является хвостом связанного списка (одиночного или двойного). Точно так же в двусвязных списках, когда для узла предыдущее установлено на Нет , то это указывает на то, что узел является главой связанного списка.

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

 class LinkedList: 
 def __init__(self, values=None): 
 self.head = None 
 self.tail = None, если values ​​не None: 
 self.add_multiple_nodes(values)

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

Первый метод с именем add_node используется для добавления одного узла в связанный список.

 def add_node(self, value): 
 если self.head равен None: 
 self.tail = self.head = Node(value) 
 else: 
 self. tail.next = Node(value) 
 self.tail = self.tail.next 
 return self.tail

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

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

 def add_multiple_nodes(self, values): 
 для значения в значениях: 
 self.add_node(value)

Пока наш класс Linked List выглядит следующим образом:

 class LinkedList: 
 def __init__(self, values=None): 
 self. head = None 
 self.tail = None if values is not None: 
 self.add_multiple_nodes(values) def add_node(self, value): 
 если self.head is None: 
 self.tail = self.head = Node(value) 
 else: 
 self.tail.next = Node(value) 
 self.tail = self.tail.next 
 return self.tail def add_multiple_nodes(self, values): 
 для значения в values: 
 self.add_node(value)

Теперь создадим дополнительный метод, который сможет вставить новый элемент, но на этот раз в начало Linked List, т.е. в заголовок.

 def add_node_as_head(self, value): 
 если self.head равен None: 
 self.tail = self.head = Node(value) 
 else: 
 self.head = Node(value, self.head) 
 return self .head

Теперь давайте переопределим некоторые специальные методы нашего класса, которые потенциально могут быть полезны. Во-первых, давайте реализуем __str__ , чтобы строковое представление объекта связанного списка было удобочитаемым для человека. Например, при печати связанного списка с узлами a, b, c, d вывод будет a -> b -> c -> d .

 def __str__(self): 
 return ' -> '.join([str(node) for node in self])

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

 def __len__(self): 
 count = 0 
 node = self.head 
 while node: 
 count += 1 
 node = node.next 
 return count

Наконец, давайте удостоверимся, что класс LinkedList является верным в состоянии реализация метода __iter__ .

 def __iter__(self): 
 current = self.head 
 while current: 
 yield current 
 current = current.next

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

 @property 
 def values(self): 
 return [node.value для узла в себе]

Окончательный класс выглядит следующим образом:

 class LinkedList: 
 def __init__(self, values=None): 
 self. head = None 
 self.tail = None, если values ​​не None: 
 self.add_multiple_nodes(values) def __str__(self): 
 return ' -> '.join([str(node) for node in self]) def __len__ (self): 
 count = 0 
 node = self.head 
 while node: 
 count += 1 
 node = node.next 
 счетчик возврата def __iter__(self): 
 current = self.head 
 while current: 
 yield current 
 current = current.next @property 
 def values(self): 
 return [node.value для узла в себе] def add_node (self, value): 
, если self.head равен None: 
 self.tail = self.head = Node(value) 
 else: 
 self.tail.next = Node(value) 
 self.tail = self.tail. следующий 
 return self.tail def add_multiple_nodes(self, values): 
 for value in values: 
 self. add_node(value) def add_node_as_head(self, value): 
, если self.head равен None: 
 self.tail = self.head = Node(value) 
 else: 
 self.head = Node(value, self.head) 
 return self.head

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

Чтобы иметь дело с двусвязными списками, мы можем просто создать дополнительный класс, который наследуется от класс LinkedList и переопределяет методы add_node и add_node_as_head :

класс 
 .хвост = сам.голова = Node(value) 
 else: 
 self.tail.next = Node(value, None, self.tail) 
 self.tail = self.tail.next 
 return self def add_node_as_head(self, value): 
 if self.head is None: 
 self.tail = self.head = Node(value) 
 else: 
 current_head = self.
No related posts.