Структуры данных: связанные списки

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

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

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

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

В чем разница между массивами и связными списками?

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

Если мы хотим получить доступ к третьему элементу в указанном выше массиве, мы можем просто сказать array[2] и иметь возможность получить доступ к нему за постоянное время O (1).

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

Попытка получить доступ к третьему элементу в связанном списке займет больше времени, чем доступ к третьему элементу в массиве. Мы должны начать с головы и продвигаться вперед, пока не найдем элемент, который ищем. Доступ к элементам занимает линейное время O (n), что намного медленнее, чем время доступа к массиву.

Зачем использовать связанный список поверх массива?

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

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

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

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

Для некоторых операций могут быть полезны двусвязные списки. Для доступа к последнему элементу в списке требуется O (1), а не O (n), а добавление или удаление последнего элемента также требует O (1) в двусвязном списке.

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

Давайте посмотрим, как реализовать односвязный список. Сначала нам нужно создать класс Node:

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

Когда у нас есть класс Node, мы можем реализовать наш класс LinkedList:

Глава списка

Во-первых, мы должны назначить узел head; верхняя часть нашего списка. Когда список инициализируется впервые, он не имеет узлов, поэтому для заголовка установлено значение None.

class LinkedList:
  def __init__(self, head=None):
    self.head = head

Вставка

Теперь мы хотим иметь возможность добавлять узлы в наш связанный список. Нам нужен метод вставки, который берет данные и добавляет их в список. Мы можем вставить узел в любом месте списка, но самый простой и быстрый способ - поместить его в начало списка и указать новый узел в старом заголовке. Это занимает O (1) по временной сложности.

def insertAtHead(self, data):
  new_node = Node(data)
  new_node.next = self.head
  self.head = new_node

Мы также можем вставить в конец списка. Мы должны пройти через весь список, чтобы найти конец, а затем добавить следующий элемент. Это будет иметь временную сложность O (n).

def insertAtTail(self, data):
  new_node = Node(data)
  current = self.head
  while current.next != None:
    current = current.next
  current.next = new_node

Длина

Определить длину нашего связанного списка довольно просто. Мы начинаем с головы и используем счетчик, который увеличивается после каждого найденного узла. Как только мы не можем найти другой узел next = None, мы возвращаем счетчик. Временная сложность для этого метода составляет O (n), потому что мы должны посетить каждый отдельный узел, чтобы его посчитать.

def length(self):
  current = self.head
  count = 0
  if current != None:
    count += 1
    while current.next != None:
      count += 1
      current = current.next
  return count

Поиск

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

def search(self, data):
  current = self.head
  while current:
    if current.data == data:
      return current
    else:
      current = current.next
  return None

Удалить

Удаление работает аналогично поиску. Мы просматриваем список так же, как и наш метод поиска, чтобы найти узел, который хотим удалить. Однако, помимо отслеживания текущего узла, нам нужно отслеживать предыдущий узел, потому что мы хотим связать его указатель со следующим узлом после удаления. Временная сложность также равна O (n), потому что в худшем случае мы посетим каждый узел.

def delete(self, data):
  current = self.head
  previous = None
  while current:
    if current.data == data:
      if previous is None:
        self.head = current.next
      else:
        previous.next = current.next
    else:
      previous = current
      current = current.next

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

def delete(self, data):
  current = self.head
  while current:
    if current.data == data:
      current.data = current.next.data
      current.next = current.next.next
    else:
     current = current.next

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

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

def reverse(self):
  previous = None
  current = self.head
  while current:
    temp = current.next
    current.next = previous
    previous = current
    current = temp
  self.head = previous

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

Затем мы проверяем, является ли следующий узел node None:

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

Как только будет достигнут последний узел, произойдет разворот.

def recursiveReverse(self, node):
  if node.next == None:
    self.head = node
    return
  self.recursiveReverse(node.next)
  temp = node.next 
  temp.next = node
  node.next = None