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

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

Создание связного списка

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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Обход связанного списка

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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Когда приведенный выше код выполняется, он дает следующий результат:

Mon
Tue
Wed

Вставка в связанный список

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

Вставка в начало связанного списка

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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

Когда приведенный выше код выполняется, он дает следующий результат:

Sun
Mon
Tue
Wed

Вставка в конец связанного списка

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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Когда приведенный выше код выполняется, он дает следующий результат:

Mon
Tue
Wed
Thu

Вставка между двумя узлами данных

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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Когда приведенный выше код выполняется, он дает следующий результат:

Mon
Tue
Fri
Thu

Удаление элемента из списка понравившихся

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

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

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

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Когда приведенный выше код выполняется, он дает следующий результат:

Thu
Wed
Mon