VerketteteListe Verfahren entfernen

Question

Was für eine doppelt verknüpfte Liste zu entfernen Methode?

Answer 1

Der gleiche Algorithmus, der Bill the Lizard gesagt, aber in einer grafischen Weise :-)

_{(Quelle: jaffasoft.co.uk )}

Answer 2

Der allgemeine Algorithmus ist wie folgt:

• Finden Sie den Knoten zu entfernen.
• node.previous.next = node.next
• node.next.previous = node.previous
• node.previous = null
• node.next = null
• Entsorgen Sie Knoten, wenn Sie in einer nicht-GC-Umgebung sind

Sie haben den vorherigen und nächsten Knoten für null zu überprüfen, um zu sehen, ob Sie den Kopf oder den Schwanz sind zu entfernen, aber das sind die einfachen Fälle.

Answer 3

public void remove ()
{
    if (getPreviousNode () != null)
        getPreviousNode ().setNextNode (getNextNode ());
    if (getNextNode () != null)
        getNextNode ().setPreviousNode (getPreviousNode ());    
}

Answer 4

doppelt verknüpfte Liste Implementierung entfernen Methoden (aus meiner zweiten Programmieraufgabe):

public void remove(int index) {
    if(index<0 || index>size())
    throw new IndexOutOfBoundsException("Index out of bounds. Can't remove a node. No node exists at the specified index");
    if(size()==0) {
        throw new NullPointerException("Empty list");
    }
    if(!isEmpty()) {
        Node current;
        //starting next one to our head
        current = head.next;
        for(int i=0;i<index;i++) {
            current = current.next;
        }
        current.previous.next = current.next;
        current.next.previous = current.previous;
        numOfNodes--;
        sizeChangeCount++;
    }
}

public boolean remove(T o) {
    Node current = head;
    for(int i=0;i<size();i++) {
        current=current.next;
        if(current.data.equals(o)) {
            current.previous.next = current.next;
            current.next.previous = current.previous;
            numOfNodes--;
            sizeChangeCount++;
            return true;
        }           
    }
    return false;
}

Answer 5

Sind Sie fragen nach dem Namen eines Verfahrens im api? Diese Antwort einfach entfernen würde, vorausgesetzt, Sie über java.util.LinkedList fragen, die in der Tat eine doppelt verkettete Liste ist.

... oder fragen Sie über das, was der Name des Algorithmus ein Element aus dieser Art von Datenstruktur entfernen heißt? Nun .. die Antwort für das wäre auch ein Element zu entfernen. Nun zu dem eigentlichen Algorithmus, es zu tun ... es ist wirklich nur darum, die nächsten Zeiger in dem vorherigen Knoten und den letzten Zeiger in dem nächsten Knoten zu ändern. Wenn Sie jedoch sind Ihre Datenstruktur von mehreren Threads verwenden, müssen Sie entweder die Methode remove synchronisieren will, oder die Entfernungsschritte in einer Reihenfolge, die sinnvoll für Ihre Nutzungsmuster für die Datenstruktur machen.

Answer 6

Was ist mit dem aktuellen Zeiger Zeiger? Sie müssen crnt zum nächsten Knoten verschieben. http://pastebin.ca/1249635