Python - listas vinculadas

Uma lista vinculada é uma sequência de elementos de dados, que são conectados por meio de links. Cada elemento de dados contém uma conexão com outro elemento de dados na forma de um ponteiro. Python não possui listas vinculadas em sua biblioteca padrão. Implementamos o conceito de listas vinculadas usando o conceito de nós conforme discutido no capítulo anterior. Já vimos como criamos uma classe de nó e como atravessar os elementos de um nó. Neste capítulo, estudaremos os tipos de listas vinculadas conhecidas como listas unidas individualmente. Nesse tipo de estrutura de dados, há apenas um link entre quaisquer dois elementos de dados. Criamos essa lista e criamos métodos adicionais para inserir, atualizar e remover elementos da lista.

Criação de lista vinculada

Uma lista ligada é criada usando a classe de nó que estudamos no último capítulo. Criamos um objeto Node e criamos outra classe para usar este objeto ode. Passamos os valores apropriados pelo objeto de nó para apontar para os próximos elementos de dados. O programa abaixo cria a lista vinculada com três elementos de dados. Na próxima seção, veremos como percorrer a lista vinculada.

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

Percorrendo uma lista vinculada

Listas unidas individualmente podem ser percorridas apenas na direção escrita, começando do primeiro elemento de dados. Simplesmente imprimimos o valor do próximo elemento de dados atribuindo o ponteiro do próximo nó ao elemento de dados atual.

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()

Quando o código acima é executado, ele produz o seguinte resultado:

Mon
Tue
Wed

Inserção em uma lista vinculada

A inserção de um elemento na lista vinculada envolve a reatribuição dos ponteiros dos nós existentes para o nó recém-inserido. Dependendo se o novo elemento de dados está sendo inserido no início ou no meio ou no final da lista vinculada, temos os cenários abaixo.

Inserindo no início da lista vinculada

Isso envolve apontar o próximo ponteiro do novo nó de dados para o cabeçalho atual da lista vinculada. Assim, o cabeçalho atual da lista encadeada se torna o segundo elemento de dados e o novo nó se torna o cabeçalho da lista encadeada.

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()

Quando o código acima é executado, ele produz o seguinte resultado:

Sun
Mon
Tue
Wed

Inserindo no final da lista vinculada

Isso envolve apontar o próximo ponteiro do último nó atual da lista vinculada para o novo nó de dados. Portanto, o último nó atual da lista vinculada se torna o segundo último nó de dados e o novo nó se torna o último nó da lista vinculada.

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()

Quando o código acima é executado, ele produz o seguinte resultado:

Mon
Tue
Wed
Thu

Inserindo entre dois nós de dados

Isso envolve mudar o ponteiro de um nó específico para apontar para o novo nó. Isso é possível passando o novo nó e o nó existente após o qual o novo nó será inserido. Portanto, definimos uma classe adicional que mudará o próximo ponteiro do novo nó para o próximo ponteiro do nó do meio. Em seguida, atribua o novo nó ao próximo ponteiro do nó do meio.

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()

Quando o código acima é executado, ele produz o seguinte resultado:

Mon
Tue
Fri
Thu

Remover um item de uma lista de gostos

Podemos remover um nó existente usando a chave para esse nó. No programa abaixo, localizamos o nó anterior do nó que deve ser excluído. Em seguida, aponte o próximo ponteiro deste nó para o próximo nó do nó a ser excluído.

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()

Quando o código acima é executado, ele produz o seguinte resultado:

Thu
Wed
Mon