Учебники

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

Декабрь 19, 2018

Связанный список — это последовательность элементов данных, которые связаны между собой ссылками. Каждый элемент данных содержит соединение с другим элементом данных в виде указателя. 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()

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

152
Share: