Lista vinculada individualmente em estruturas de dados

O que é uma lista vinculada individualmente?

Uma lista simplesmente encadeada é uma estrutura de dados linear e unidirecional onde os dados são armazenados nos nós, e cada nó é conectado ao nó seguinte por meio de uma ligação. Cada nó contém um campo de dados e uma ligação para o próximo nó. Listas simplesmente encadeadas podem ser percorridas em apenas uma direção, enquanto uma lista não encadeada pode ser percorrida em uma única direção. Lista duplamente vinculada Pode ser percorrido em ambas as direções.

Aqui está a estrutura de nós de uma Lista Simplesmente Encadeada:

Estrutura de um nó em uma lista vinculada

Por que usar uma lista encadeada em vez de um array?

Diversos cenários favorecem uma Lista Ligada em detrimento de uma Lista Encadeada. Ordem:

• Número desconhecido de elementos: Quando a quantidade de elementos necessária não é conhecida em tempo de compilação, uma Lista Ligada aloca memória dinamicamente à medida que os elementos são adicionados.
• Acesso aleatório: Quando o acesso indexado aleatório não é necessário, uma lista encadeada é uma escolha adequada.
• Inserção no meio: Inserir um elemento no meio de um array requer o deslocamento de elementos. Uma lista ligada permite a inserção em qualquer posição, reescrevendo apenas alguns ponteiros.

Operações de lista vinculada individualmente

Uma lista simplesmente encadeada é ideal para alocação dinâmica de memória. Ela suporta as operações padrão de uma lista encadeada, como inserção, remoção, busca, atualização, fusão de duas listas e percurso.

As seguintes operações são discutidas neste artigo:

• 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
• Pesquise e exclua um nó
• Percorrendo a lista vinculada

Aqui está um exemplo de uma lista encadeada com quatro nós.

Exemplo de uma lista vinculada individualmente

Inserção no cabeçalho de uma lista simplesmente encadeada

Esta é uma operação simples. Geralmente é conhecida como inserção em uma lista simplesmente encadeada. Um novo nó é criado e colocado no início da lista.

Para realizar esta operação, observe duas condições importantes:

1. Se a lista estiver vazia, o nó recém-criado torna-se o nó principal e seu Próximo O ponteiro é NULL.
2. Se a lista não estiver vazia, o novo nó se torna o nó principal e seu Próximo O ponteiro aponta para o nó principal anterior.

Segue o pseudocódigo para inserir um nó no início de uma lista encadeada:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Inserindo na cabeça

Inserção no final de uma lista simplesmente encadeada

Inserir um nó no final de uma lista encadeada é semelhante a inserir no início. Percorra a lista até o nó final e, em seguida, aponte para ele. Próximo Ponteiro para o novo nó. Se o cabeçalho for NULL, o novo nó se torna o cabeçalho.

Passo 1) Atravesse até o Próximo O ponteiro do nó atual torna-se NULL.

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 elemento no final de uma lista com apenas um elemento:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Inserindo na cauda

Inserção após um nó em uma lista simplesmente encadeada

A inserção após um nó envolve duas partes: buscar o nó alvo e anexar um novo nó após ele. Percorrer a lista até encontrar uma correspondência e, em seguida, inserir o novo nó.

Passo 1) Percorra a lista até que o valor do nó atual seja igual ao item de busca.

Passo 2) Defina o novo nó Próximo ponteiro para o nó atual Próximo ponteiro.

Passo 3) Aponte o nó atual para Próximo ponteiro para o novo nó.

Pseudocódigo:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Inserindo um nó após um nó na lista vinculada individualmente

Inserção antes de um nó em uma lista simplesmente encadeada

Isso é semelhante à inserção após um nó. Percorra a lista até encontrar o próximo nó que corresponda ao valor de busca e, em seguida, insira o novo nó antes dele.

Passo 1) Percorra até que o valor do próximo nó seja igual ao item de pesquisa.

Passo 2) Crie um novo nó e defina-o Próximo ponteiro para o nó atual Próximo.

Passo 3) Aponte o nó atual para Próximo para o novo nó.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Inserindo um nó antes de um nó na lista vinculada individualmente

Excluir o cabeçalho da lista simplesmente encadeada

O ponteiro para o nó inicial é fornecido como parâmetro. O nó inicial é removido e o próximo nó se torna o novo nó inicial. A memória do nó excluído deve ser liberada para evitar vazamentos de memória.

Passo 1) Atribua o próximo nó da cabeça como a nova cabeça.

Passo 2) Libere a memória alocada do nó cabeçalho anterior.

Passo 3) Retorne o novo nó principal.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Excluindo o cabeçalho de uma lista vinculada

Excluir a cauda da lista simplesmente encadeada

Excluir o nó final é semelhante a excluir o nó inicial. A diferença é que é necessário percorrer toda a lista até o final. Em uma lista simplesmente encadeada, o nó cujo Próximo O ponteiro é NULL e é o nó final.

Passo 1) Percorra o trajeto até um pouco antes do nó final. Salve o nó atual.

Passo 2) Libere a memória do próximo nó (a cauda).

Passo 3) Defina o próximo nó do nó atual como NULL.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Excluindo o final da lista vinculada individualmente

Pesquisar e excluir um nó de uma lista simplesmente encadeada

Esta função executa duas tarefas: busca e exclusão. Percorre a lista até o final. Se um nó correspondente for encontrado, remove-o e religa o nó anterior. Próximo ponteiro.

Passo 1) Percorra a lista até o final. Verifique se o nó atual é igual ao nó de busca.

Passo 2) Se uma correspondência for encontrada, armazene um ponteiro para o nó atual.

Passo 3) O Próximo O nó anterior torna-se o próximo nó do nó atual.

Passo 4) Exclua o nó atual e libere sua memória.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Pesquise e exclua um nó da lista vinculada individualmente

Percorrer uma lista simplesmente encadeada

Uma lista simplesmente encadeada suporta apenas a travessia do início ao fim. Não há ponteiro para o nó anterior, portanto a travessia reversa não é possível. Cada nó é visitado sequencialmente, imprimindo seu valor até que NULL seja alcançado.

Passo 1) Percorra cada nó até encontrar NULL.

Passo 2) Imprima o valor do nó atual.

function traverse(head):
  while head is not NULL:
    print head.value
    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);
    return;
  }
  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 = NULL;
  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);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
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 = 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

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.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    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):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  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 no pior caso e no caso médio são as mesmas para uma lista simplesmente encadeada.

Complexidade de tempo no melhor caso:

• A inserção no início pode ser feita em O(1). Não é necessário percorrer a lista.
• A busca e a exclusão podem ser feitas em O(1) se o elemento alvo estiver no nó cabeça.

Complexidade de tempo no caso médio:

• A inserção dentro de uma lista ligada leva tempo O(n), onde n é o número total de elementos.
• A busca e a exclusão também podem levar O(n), porque o elemento alvo pode estar em qualquer lugar até o nó final.

Complexidade espacial de uma lista simplesmente encadeada

Uma lista simplesmente encadeada aloca memória dinamicamente. Para armazenar n elementos, ele aloca n unidades de memória. Portanto, a complexidade de espaço é O(n).

Aplicações de listas simplesmente encadeadas

Listas simplesmente encadeadas aparecem em muitos lugares onde a travessia apenas para frente e a memória dinâmica são úteis:

• Pilhas e filas: Armazenamento subjacente para pilhas LIFO e filas FIFO construídas a partir de nós.
• Encadeamento de tabelas hash: As colisões são resolvidas encadeando as entradas em uma Lista Simplesmente Encadeada por bucket.
• Listas de adjacência: Os grafos esparsos utilizam uma lista simplesmente encadeada de vizinhos para cada vértice.
• Tabelas de símbolos: Compiladores e interpretadores encadeiam identificadores em uma Lista Simplesmente Encadeada por escopo.
• Alocadores de memória: alocadores de lista livre track blocos livres como uma lista simplesmente encadeada.

Perguntas Frequentes