Lista vinculada individualmente em estruturas de dados
Sarah Chen
O que é uma lista vinculada individualmente?
Lista vinculada individualmente é uma estrutura de dados linear e unidirecional, onde os dados são salvos nos nós e cada nó é conectado por meio de um link ao seu próximo nó. Cada nó contém um campo de dados e um link para o próximo nó. Listas vinculadas individualmente podem ser percorridas em apenas uma direção, enquanto listas duplamente vinculadas podem ser percorridas em ambas as direções.
Aqui está uma estrutura de nós de uma lista vinculada individualmente:
Por que usar lista vinculada em vez de array?
Existem vários casos em que é melhor usar a Lista Vinculada em vez da Ordem. Aqui estão alguns cenários:
- Número desconhecido de elementos: Quando você não sabe quantos elementos precisa armazenar durante o tempo de execução do programa, você pode usar a Lista Vinculada. A memória é alocada dinamicamente à medida que você adiciona elementos às listas vinculadas.
- Acesso aleatório: Em um cenário onde você não precisa usar o acesso aleatório dos elementos, você pode usar a Lista Vinculada.
- Inserção no meio: A inserção no meio de um array é uma tarefa complexa. Porque você precisa empurrar outros elementos para a direita. No entanto, uma lista vinculada permite adicionar um elemento a qualquer posição desejada.
Operações de lista vinculada individualmente
Lista vinculada individualmente é boa para alocar memória dinamicamente. Ele fornece todas as operações básicas da lista vinculada, ou seja, inserção, exclusão, pesquisa, atualização, fusão de duas listas vinculadas, deslocamento, etc.
Aqui discutiremos a seguinte operação da lista vinculada:
- Inserindo na cabeça
- Inserindo na cauda
- Inserindo após um nó
- Inserindo antes de um nó
- Exclua o nó principal
- Exclua o nó final
- Pesquisar e excluir um nó
- Percorrendo a lista vinculada
Aqui está um exemplo de lista vinculada com quatro nós.
Inserção no topo de uma lista vinculada individualmente
Esta é uma operação simples. Geralmente, é conhecido como enviar uma lista vinculada individualmente. Você precisa criar um novo nó e colocá-lo no topo da lista vinculada.
Para realizar esta operação, precisamos seguir duas condições importantes. Eles estão
- Se a lista estiver vazia, o nó recém-criado será o nó principal e o próximo nó principal será “NULL”.
- Se a lista não estiver vazia, o novo nó será o nó principal e o próximo apontará para o nó principal anterior.
Aqui está o pseudocódigo para inserir um nó no topo de uma lista vinculada:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Inserção no final de uma lista vinculada individualmente
A inserção de um nó no final de uma lista encadeada tem algumas semelhanças com a inserção no cabeçalho. Tudo o que você precisa fazer é atravessar até o nó final ou o nó final. Em seguida, aponte o “próximo” nó do nó final para o nó recém-criado. Se o nó principal for nulo, o novo nó será o nó principal.
Aqui estão os passos:
Passo 1) Percorra até que o “próximo” nó do nó atual se torne nulo.
Passo 2) Crie um novo nó com o valor especificado.
Passo 3) Atribua o novo nó como o próximo nó do nó final.
O pseudocódigo para inserir um nó no final de uma lista única:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
Inserção após um nó em uma lista vinculada individualmente
A inserção após um nó tem duas partes: Procurar o nó e anexar após o nó pesquisado. Precisamos percorrer todos os nós. Para cada nó, precisamos combinar com o elemento de pesquisa. Se houver uma correspondência, adicionaremos o novo nó após o nó pesquisado.
Aqui estão os passos:
Passo 1) Percorra o próximo nó até que o valor do nó atual seja igual ao item de pesquisa.
Passo 2) O próximo ponteiro do novo nó será o próximo ponteiro do nó atual.
Passo 3) O próximo nó do nó atual será o novo nó.
Aqui está o pseudocódigo para inserir um nó após um nó:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Inserção antes de um nó em uma lista vinculada individualmente
Esta função é muito semelhante à inserção após um nó. Devemos criar um novo nó e percorrer a lista vinculada até que o nó atual corresponda ao nó de pesquisa. Depois disso, adicionaremos o novo nó como o nó anterior do nó atual.
Aqui estão os passos:
Passo 1) Percorra até que o valor do próximo nó seja igual ao item de pesquisa.
Passo 2) Crie um novo nó e atribua o “próximo” do nó ao próximo ao próximo nó do nó atual.
Passo 3) Atribua o novo nó como o próximo nó do nó atual.
Aqui está o pseudocódigo:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Exclua o cabeçalho da lista vinculada individualmente
Em cada função da lista vinculada, o ponteiro principal é fornecido como parâmetro. Você precisa excluir o nó principal e tornar o próximo nó do nó principal o novo nó principal da lista vinculada. Também precisamos liberar a memória do nó excluído. Caso contrário, a memória será marcada como ocupada quando outro programa tentar acessá-la.
Aqui estão as etapas para excluir o cabeçalho da lista vinculada individualmente:
Passo 1) Atribua o próximo nó do nó principal como o novo nó principal.
Passo 2) Libere a memória alocada pelo nó principal anterior.
Passo 3) Retorne o novo nó principal.
O pseudocódigo para excluir o nó principal:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Exclua o final da lista vinculada individualmente
A exclusão do nó final é mais familiar à exclusão do nó principal. A diferença é que precisamos ir até o final da lista vinculada e excluí-la. Na lista vinculada individualmente, o nó com o próximo nó como “NULL” é o nó final.
Aqui estão as etapas para excluir o nó final da lista vinculada:
Passo 1) Percorra antes do nó final. Salve o nó atual.
Passo 2) Libere a memória do próximo nó do nó atual.
Passo 3) Defina o próximo nó do nó atual como NULL.
Aqui está o pseudocódigo para excluir o nó final:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Pesquise e exclua um nó de uma lista vinculada individualmente
Esta função tem duas tarefas, pesquisar e excluir. Precisamos pesquisar até o final das listas vinculadas individualmente. Se encontrarmos algum nó semelhante, iremos excluí-lo. Depois disso, precisamos mesclar ou vincular os nós esquerdo e direito do nó excluído. Aqui estão as etapas para fazer isso:
Passo 1) Percorra até o final da lista vinculada. Verifique se o nó atual é igual ao nó de pesquisa ou não.
Passo 2) Se algum nó corresponder, armazene o ponteiro do nó no nó atual.
Passo 3) O “próximo” do nó anterior será o próximo nó do nó atual.
Passo 4) Exclua e libere a memória do nó atual.
Pseudocódigo para pesquisar e excluir um nó de uma lista vinculada individualmente:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
Percorrer uma lista vinculada individualmente
A lista vinculada individualmente tem apenas a funcionalidade de percorrer de ponta a ponta. Não há ponteiros para o nó anterior; é por isso que não podemos percorrer a lista vinculada individualmente na ordem inversa. Percorreremos cada nó e imprimiremos o valor do nó atual até obtermos nulo.
Aqui estão os passos:
Passo 1) Percorra cada nó até obtermos nulo como o próximo nó.
Passo 2) Imprima o valor do nó atual.
Pseudocódigo para percorrer uma lista vinculada individualmente:
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
Exemplo de lista vinculada individualmente em C++
#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
void insertAtHead(Node* &head, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if(head!=NULL){
newNode->next = head;
}
head = newNode;
cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
if(head==NULL){
insertAtHead(head,value);
}
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newNode;
cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
Node *temp = new Node();
if( (*headPtr)->data == searchItem ){
temp = *headPtr;
*headPtr = (*headPtr)->next;
free(temp);
}else{
Node *currentNode = *headPtr;
while(currentNode->next != NULL){
if(currentNode->next->data == searchItem){
temp = currentNode->next;
currentNode->next = currentNode->next->next;
free(temp);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->next->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
Node* tempNode = new Node();
tempNode = headPointer;
cout<<"Traversal from head:\t";
while(tempNode !=NULL){
cout<<tempNode->data;
if(tempNode->next)
cout<<" --> ";
tempNode = tempNode ->next;
}
cout<<endl;
}
int main(){
Node *head = NULL;
insertAtHead(head,5);
insertAtHead(head,6);
insertAtHead(head,7);
insertEnd(head,9);
traverse(head);
searchAndDelete(&head,6);
traverse(head);
insertAfter(head,7,10);
insertBefore(head,9,11);
traverse(head);
}
Saída:
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9
Exemplo de lista vinculada individualmente em Python Programa
class Node:
def __init__(self,data = None, next = None):
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def insertAtHead(self, value):
newNode = Node(data=value)
if self.head is not None:
newNode.next = self.head
self.head = newNode
print(f'Added {newNode.data} at the front.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
newNode = Node(value)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
print(f'Added {newNode.data} at the end.')
def searchAndDelete(self,searchItem):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
def insertAfter(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} after node\t{searchItem}')
return
def insertbefore(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} before node\t{searchItem}')
return
def traverse(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()
Saída:
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
Complexidade da lista vinculada individualmente
Existem dois tipos de complexidade: complexidade de tempo e complexidade de espaço. A complexidade de tempo do pior caso e da média é a mesma para a lista vinculada individualmente.
A complexidade do tempo para o melhor caso:
- A inserção na cabeça pode ser feita em O(1). Como não precisamos percorrer dentro da lista vinculada.
- A operação de busca e exclusão pode ser feita em O(1) se o elemento de busca estiver presente no nó principal.
A complexidade de tempo para o caso médio:
- A inserção dentro de uma lista vinculada levará O (n) se “n” elementos estiverem presentes na lista vinculada individualmente.
- Pesquisar e excluir também podem levar O(n), pois o elemento de pesquisa pode estar presente no nó final. Nesse caso, você deve percorrer toda a lista.
Complexidade espacial da lista vinculada individualmente
A lista vinculada individualmente aloca memória dinamicamente. Se quisermos armazenar n elementos, serão alocadas n unidades de memória. Portanto, a complexidade do espaço é O(n).
