Демистификация структур данных: связанные списки, часть 1

Основные операции над односвязными списками, выполняемые в Python.

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

Элементы связанного списка называются узлами. Узел обычно состоит из двух частей:

  • Данные или содержимое этого узла.
  • Ссылка или указатель на следующий Node.

Вот пример того, как выглядит связанный список:

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

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

Если вы создадите новый узел, он будет выглядеть так:

new_node = Node(10)

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

Начнем с определения класса следующим образом:

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

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

  • Вставка
  • Удаление
  • Обход

Вставка

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

  1. Вставка с начала списка

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

1. Получите новый узел.
2. Установите указатель этого узла так, чтобы он указывал на текущую головку.
3. Сделайте этот узел новой головкой.

def push(self, item):
        node = Node(item)
        
        node.next = self.head
        self.head = node

2. Вставка с конца списка

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

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

  1. Получите новый узел.
  2. Если список пуст, сделайте этот узел головным узлом.
  3. Если в списке есть элементы, просматривайте их, пока не найдете последний узел.
  4. Установите указатель последнего узла так, чтобы он указывал на новый узел.
def append(self, item):
        node = Node(item)
        
        if self.head is None: 
            self.head = node 
            return
    
        last = self.head
        while last.next:
            last = last.next
            
        last.next = node

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

Удаление

Как обсуждалось при вставке узла, удаление также можно выполнить либо с начала списка, либо с конца.

  1. Удаление с начала списка

Эта операция называется извлечение, так как она напоминает операцию извлечения из стека.

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

  1. Если список пуст, удалять нечего.
  2. Если есть только один элемент, удалите его. Другими словами, установите заголовок None.
  3. Если существует список:
  • Установите временный узел, temp, чтобы он указывал на узел после заголовка.
  • Установите новую головку на температуру узла.
def pop(self):
        #If the list is empty, do nothing
        if self.head is None:
            return
        
        #If there is only one element in the list, delete it
        if temp.next == None:
            self.head = None
            return
        #If there are elements, start with the head  
        temp = self.head.next
        self.head = temp
        return

2. Удаление из конца списка

Удаление с конца связанного списка похоже на удаление вагонов поезда, начиная с последнего вагона. Для этого мы находим два последних элемента и устанавливаем указатель последнего элемента на None.

  1. Если список пуст, ничего не делайте.
  2. Если в списке только один элемент, то удалите заголовок.
  3. Если в списке несколько элементов:
  • Задайте для переменной cur (текущий) текущий головной узел, а для prev (предыдущий) — значение None.
  • Теперь установите prev на элемент cur и сделайте так, чтобы cur указывал на следующий элемент.
  • Делая это, мы в основном находим два элемента за раз, пока не достигнем конца списка.
  • Мы прекращаем делать это, когда за cur не следует ни одного элемента. Это означает, что мы достигли последнего элемента.

4. Установите указатель prev на None. Это отключит последний элемент от списка. Теперь prev — последний элемент списка.

def delete(self):
        cur = self.head
        
        #If the list is empty
        if self.head is None:
            return
        
        #If there is only one element in the list
        if cur.next == None:
            self.head = None
            return
        
        while cur.next != None:
            prev = cur
            cur = cur.next
            
        prev.next = None
        return

Обход списка

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

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

def printList(self):
        if self.head is None:
            print('EMPTY LIST')
        
        temp = self.head 
        while temp: 
            print(temp.data, '\t') 
            temp = temp.next

И это все! Мы рассмотрели самые основные операции связанного списка. Вот весь код на Python.