Python – Listas Ligadas
Uma lista ligada é uma sequência de elementos de dados, que estão ligados entre si através de ligações. Cada elemento de dados contém uma ligação a outro elemento de dados sob a forma de um ponteiro. Python não tem listas ligadas na sua biblioteca padrão. Implementamos o conceito de listas ligadas utilizando o conceito de nós, tal como discutido no capítulo anterior. Já vimos como criar uma classe de nós e como atravessar os elementos de um nó. Neste capítulo vamos estudar os tipos de listas ligadas conhecidas como listas ligadas individualmente. Neste tipo de estrutura de dados existe apenas uma ligação entre quaisquer dois elementos de dados. Criamos tal lista e criamos métodos adicionais para inserir, actualizar e remover elementos da lista.
Criação de lista ligada
Uma lista ligada é criada usando a classe de nó que estudámos no último capítulo. Criamos um objecto de Nodo e criamos outra classe para utilizar este objecto de ode. Passamos os valores apropriados ao objecto do nó para apontar os elementos de dados seguintes. O programa abaixo cria a lista ligada com três elementos de dados. Na secção seguinte veremos como atravessar a lista ligada.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = Nonelist1 = SLinkedList()list1.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist1.headval.nextval = e2# Link second Node to third nodee2.nextval = e3
Viajando uma Lista Ligada
Listas ligadas por ligação podem ser atravessadas apenas na direcção forwrad, começando pelo 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 actual.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist.headval.nextval = e2# Link second Node to third nodee2.nextval = e3list.listprint()
Quando o código acima é executado, produz o seguinte resultado:
MonTueWed
Inserção numa lista ligada
Inserção de elemento na lista ligada envolve a reatribuição das indicações dos nós existentes para o nó recém inserido. Dependendo se o novo elemento de dados está a ser inserido no início ou no meio ou no fim da lista ligada, temos os cenários abaixo.
Inserção no Início da Lista Ligada
Aqui envolve apontar o próximo ponteiro do novo nó de dados para o chefe actual da lista ligada. Assim, o actual cabeçalho da lista ligada torna-se o segundo elemento de dados e o novo nó torna-se o cabeçalho da lista ligada.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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 = NewNodelist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtBegining("Sun")list.listprint()
Quando o código acima é executado, produz o seguinte resultado:
SunMonTueWed
Inserindo no fim da lista ligada
Isto implica apontar o próximo ponteiro do último nó actual da lista ligada para o novo nó de dados. Assim, o último nó actual da lista ligada torna-se o segundo último nó de dados e o novo nó torna-se o último nó da lista ligada.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtEnd("Thu")list.listprint()
Quando o código acima é executado, produz o seguinte resultado:
MonTueWedThu
Inserir entre dois nós de dados
Isto envolve o ajuste do ponteiro de um nó específico para apontar para o novo nó. Isto é possível passando tanto no novo nó como no existente, após o que o novo nó será inserido. Assim, definimos uma classe adicional que mudará o próximo ponteiro do novo nó para o próximo ponteiro do nó médio. Em seguida, atribuir o novo nó ao próximo ponteiro do nó médio.
class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass 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.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Thu")list.headval.nextval = e2e2.nextval = e3list.Inbetween(list.headval.nextval,"Fri")list.listprint()
Quando o código acima é executado, produz o seguinte resultado:
MonTueFriThu
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 eliminado. Depois apontamos o próximo ponteiro deste nó para o próximo nó do nó a ser eliminado.
class Node: def __init__(self, data=None): self.data = data self.next = Noneclass 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.nextllist = SLinkedList()llist.Atbegining("Mon")llist.Atbegining("Tue")llist.Atbegining("Wed")llist.Atbegining("Thu")llist.RemoveNode("Tue")llist.LListprint()
Quando o código acima é executado, produz o seguinte resultado:
ThuWedMon