Se entendi bem, comparando uma lista duplamente ligada, com uma individualmente ligada (não sei se é a tradução correta para Singly Linked List), a única vantagem seria para remover o último elemento, neste caso como já possuímos uma referência para o último, fica fácil encontrar o anterior this.ultimo.getAnterior(). O tempo é constante.
Não haveria vantagem para remover um elemento no meio. Em ambas eu precisaria navegar a lista para encontrar o elemento anterior ao que eu quero remover, e a partir dele, encontrar o próximo, ou seja, em ambas as listas, o tempo de remoção de um elemento no meio é linear.
Código para remover um elemento no meio, em uma lista ligada:
public void remove(int index) {
if (this.size == 0) {
throw new IllegalArgumentException("The list is empty");
} else if (!this.isIndexOccupied(index)) {
throw new IllegalArgumentException("Inexistent index");
}
if (index == 0) {
this.removeFirst();
} else if (index == this.size - 1) {
this.removeLast();
} else {
Cell previous = this.getCell(index - 1);
Cell next = previous.getNext().getNext();
previous.setNext(next);
this.size--;
}
}Já em uma lista duplamente ligada, a diferença é que no próximo elemento ao que estou removendo, preciso alterar a seta de anterior para o anterior ao que estou removendo:
public void remove(int index) {
if (this.size == 0) {
throw new IllegalArgumentException("The list is empty");
} else if (!this.isIndexOccupied(index)) {
throw new IllegalArgumentException("Inexistent index");
}
if (index == 0) {
this.removeFirst();
} else if (index == this.size - 1) {
this.removeLast();
} else {
Cell previous = this.getCell(index - 1);
Cell next = previous.getNext().getNext();
previous.setNext(next);
next.setPrevious(previous);
this.size--;
}
}Gostaria de saber se entendi corretamente, entre os dois tipos de lista:
- Não existe benefício em relação a remover um elemento no meio?
- A única vantagem da lista duplamente ligada seria simplesmente remover o último elemento com tempo constante?
