Метод удаления LinkedList

Question

Что такое метод удаления двусвязного списка?

Answer 1

Тот же алгоритм, что и Билл Ящерица , но графически:

_{(источник: jaffasoft.co.uk )}

Answer 2

Общий алгоритм выглядит следующим образом:

• Найдите узел для удаления.
• node.previous.next = node.next
• node.next.previous = node.previous
• node.previous = null
• node.next = null
• Утилизируйте узел, если вы находитесь в среде без GC

Вы должны проверить предыдущий и следующий узлы на ноль, чтобы увидеть, удаляете ли вы голову или хвост, но это простые случаи.

Answer 3

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

Answer 4

Методы удаления для реализации двусвязного списка (из моего второго программного задания):

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

А как насчет текущего указателя указателя? Вы должны переместить crnt к следующему узлу. http://pastebin.ca/1249635

Answer 6

Вы спрашиваете название метода в API? Этот ответ будет просто удален, при условии, что вы спрашиваете о java.util.LinkedList, который на самом деле является двойным связанным списком.

... или вы спрашиваете, как называется алгоритм удаления элемента из этого типа структуры данных? Ну ... ответом на это также будет удаление элемента. Теперь для фактического алгоритма, чтобы сделать это ... это просто вопрос изменения следующего указателя в предыдущем узле и последнего указателя в следующем узле. Однако если вы используете свою структуру данных из нескольких потоков, вам нужно будет либо синхронизировать метод удаления, либо выполнить шаги удаления в порядке, который будет иметь смысл для вашего шаблона использования структуры данных.