Облако знаний. Связные списки (Python). Информатика. 11 класс

Связные списки (Python)

Связный список – структура данных, состоящая из последовательности элементов, где каждый узел хранит:
- данные (значение);
- указатель (ссылку) на следующий узел в списке.
Элементы располагаются в динамической памяти (куче), а не в непрерывной области памяти, как в массиве. Реализация на Python:
class Node:
def __init__ (self, data):
self.data = data # полезные данные
self.next = None # ссылка на следующий узел
Основные виды связных списков:
- односвязный список – узел содержит указатель только на следующий элемент:
  class Node:
  def __init__ (self, data):
  self.data = data
  self.next = None
- двусвязный список – узел содержит указатели и на следующий, и на предыдущий элемент:
  class DNode:
  def __init__ (self, data):
    self.data = data
    self.next = None # ссылка на следующий узел
    self.prev = None # ссылка на предыдущий узел
- кольцевой список – «хвост» списка указывает на его «голову», образуя кольцо.
Преимущество перед массивами: эффективная вставка/удаление. Не требует сдвига всех последующих элементов, как в массиве.

Было полезно?