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

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

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

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

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

Как связанные списки хранят данные

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

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

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

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

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

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

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

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

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

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

Единый связанный список
Создание класса узла
Создание класса единого связанного списка
Обход элементов связанного списка
Вставка элементов
Подсчет элементов
Поиск элементов
Создание связного списка
Удаление элементов
Обращение связного списка

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

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

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

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

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

С другой стороны, если список уже содержит какие-то узлы. Мы инициализируем переменную 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 переменной start_node. Затем мы просматриваем связанный список, используя цикл while. Цикл while выполняется до тех пор, пока n станет None . Во время каждой итерации мы проверяем, равно ли значение, хранящееся в текущем узле, значению, переданному параметром x Если сравнение вернет истину, мы прервем цикл.

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

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

 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 

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

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

Затем, если элемент найден, 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 . Например, если вы хотите добавить новый узел в третий index. Во время первой итерации цикла while i станет равным 2, а текущий итерируемый узел будет равен «2». Цикл не будет выполняться снова, поскольку i равно 2, что равно index-1 (3-1 = 2). Следовательно, петля разорвется. Затем мы добавляем новый узел после текущего итеративного узла (который является узлом 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) 

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

 new_linked_list.traverse_list() 

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

 5 
 10 
 15 

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

 new_linked_list.insert_at_start(20) 

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

 20 
 5 
 10 
 15 

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

 new_linked_list.insert_after_item(10, 17) 

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

 20 
 5 
 10 
 17 
 15 

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

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

 new_linked_list.insert_before_item(17, 25) 

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

 20 
 5 
 10 
 25 
 17 
 15 

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

 new_linked_list.insert_at_index(3,8) 

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

 20 
 5 
 8 
 10 
 25 
 17 
 15 

И с этим мы протестировали все наши функции вставки. В настоящее время в нашем списке 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 и затем вставьте некоторые элементы в 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 выше функцию в класс 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() в действии.

{.ezlazyload .img-responsive}

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

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

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

Удалить элемент или элемент из начала связанного списка очень просто. Мы должны установить ссылку 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 

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

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

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

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

 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 элементов в связанный список. Если вы пройдете по списку, вы должны увидеть следующие элементы:

 10 
 20 
 30 
 40 
 50 

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

 new_linked_list.delete_at_start() 

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

 20 
 30 
 40 
 50 

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

 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 станет равным нулю. Внутри цикла while вам необходимо выполнить следующие функции.

• Присвойте значение ссылки текущего узла next .
• Установите значение ссылки текущего узла n на prev
• Установите prev на текущий узел n .
• Установите текущий узел n на значение next узла.

В конце цикла 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 выше функцию в класс LinkedList. Создайте связанный список случайных чисел, а затем посмотрите, можно ли его отменить, используя функцию reverse_linkedlist()

Заключение

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

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