Понимание реализации связанных списков в Python

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

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

Связный список — это линейная структура данных. Он не хранит данные в смежных областях памяти, таких как массивы. И каждый элемент в соединении называется узлом, и они связаны указателями. Первый узел в связанном списке называется головным.

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

Существует два типа связанных списков. Давайте составим подробное руководство по ним один за другим.

№1. Односвязный список

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

Последний узел в связанном списке содержит null в качестве следующего указателя, представляющего конец связанного списка.

Вы можете увидеть иллюстрацию по ссылке ниже.

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

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

1. Первый шаг — создать узел для связанного списка.

Как его создать?

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

См. код узла.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

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

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

2. Создайте класс LinkedList с заголовком, инициализированным значением None. См. код ниже.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. У нас есть классы Node и LinkedList. Как вставить новый узел в связанный список? Простым ответом может быть использование метода в классе LinkedList. Да, это было бы мило. Давайте напишем метод для вставки нового узла в связанный список.

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

Давайте посмотрим на них.

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

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

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

Ура! мы завершили метод для вставки нового узла в связанный список. Как мы можем получить доступ к данным узла из связанного списка?

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

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

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

Давайте посмотрим код.

class LinkedList:

	####

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')

ЭУ! мы закончили создание связанных с нужными методами. Давайте проверим связанный список, создав его экземпляр с некоторыми данными.

Мы можем создать узел с кодом Node(1). Давайте посмотрим полный код реализации связанного списка вместе с примером использования.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')


if __name__ == '__main__':
	## instantiating the linked list
	linked_list = LinkedList()

	## inserting the data into the linked list
	linked_list.insert(Node(1))
	linked_list.insert(Node(2))
	linked_list.insert(Node(3))
	linked_list.insert(Node(4))
	linked_list.insert(Node(5))
	linked_list.insert(Node(6))
	linked_list.insert(Node(7))

	## printing the linked list
	linked_list.display()

Запустите приведенную выше программу, чтобы получить следующий вывод.

1->2->3->4->5->6->7->Null

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

№ 2. Двусвязный список

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

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

Вы можете увидеть иллюстрацию по ссылке ниже.

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

Реализация двусвязного списка

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

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Класс двусвязных списков.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Способ вставки нового узла в двусвязный список.

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the last node to the previous pointer of the new node
			new_node.prev = last_node

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

4. Способ отображения данных двусвязного списка.

class LinkedList:

	####

	def display(self):

		## printing the data in normal order
		print("Normal Order: ", end='')

		temp_node = self.head
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.next
		print()

		## printing the data in reverse order using previous pointer
		print("Reverse Order: ", end='')

		## getting the last node
		last_node = self.head
		while last_node.next != None:
			last_node = last_node.next

		temp_node = last_node
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.prev
		print()

Мы видели код двусвязного списка. И нет кода для использования класса двусвязного списка. Это для тебя. Используйте класс двусвязного списка, аналогичный односвязному списку. Получайте удовольствие ?

Заключение

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

Удачного кодирования ?