javascript-algorithms

Lista Duplamente Ligada (Doubly Linked List)

Na ciência da computação, uma lista duplamente conectada é uma estrutura de dados vinculada que se consistem em um conjunto de registros sequencialmente vinculados chamados de nós (nodes). Em cada nó contém dois campos, chamados de ligações, que são referenciados ao nó anterior e posterior de uma sequência de nós. O começo e o fim dos nós anteriormente e posteiormente ligados, respectiviamente, apontam para algum tipo de terminação, normalmente um nó sentinela ou nulo, para facilitar a travessia da lista. Se existe somente um nó sentinela, então a lista é ligada circularmente através do nó sentinela. Ela pode ser conceitualizada como duas listas individualmente ligadas e formadas a partir dos mesmos itens, mas em ordem sequencial opostas.

Doubly Linked List

Os dois nós ligados permitem a travessia da lista em qualquer direção. Enquanto adicionar ou remover um nó de uma lista duplamente vinculada requer alterar mais ligações (conexões) do que em uma lista encadeada individualmente (singly linked list), as operações são mais simples e potencialmente mais eficientes (para nós que não sejam nós iniciais) porque não há necessidade de se manter rastreamento do nó anterior durante a travessia ou não há necessidade de percorrer a lista para encontrar o nó anterior, para que então sua ligação/conexão possa ser modificada.

Pseudocódigo para Operações Básicas

Inserir

Add(value)
  Pre: value is the value to add to the list
  Post: value has been placed at the tail of the list
  n ← node(value)
  if head = ø
    head ← n
    tail ← n
  else
    n.previous ← tail
    tail.next ← n
    tail ← n
  end if
end Add

Deletar

Remove(head, value)
  Pre: head is the head node in the list
       value is the value to remove from the list
  Post: value is removed from the list, true; otherwise false
  if head = ø
    return false
  end if
  if value = head.value
    if head = tail
      head ← ø
      tail ← ø
    else
      head ← head.next
      head.previous ← ø
    end if
    return true
  end if
  n ← head.next
  while n = ø and value !== n.value
    n ← n.next
  end while
  if n = tail
    tail ← tail.previous
    tail.next ← ø
    return true
  else if n = ø
    n.previous.next ← n.next
    n.next.previous ← n.previous
    return true
  end if
  return false
end Remove

Travessia reversa

ReverseTraversal(tail)
  Pre: tail is the node of the list to traverse
  Post: the list has been traversed in reverse order
  n ← tail
  while n = ø
    yield n.value
    n ← n.previous
  end while
end Reverse Traversal

Complexidades

Complexidade de Tempo

Acesso Pesquisa Inserção Remoção
O(n) O(n) O(1) O(n)

Complexidade de Espaço

O(n)

Referências