LinkedList remove method

Question

What is a doubly linked list's remove method?

Answer 1

The same algorithm that Bill the Lizard said, but in a graphical way :-)

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

Answer 2

The general algorithm is as follows:

• Find the node to remove.
• node.previous.next = node.next
• node.next.previous = node.previous
• node.previous = null
• node.next = null
• Dispose of node if you're in a non-GC environment

You have to check the previous and next nodes for null to see if you're removing the head or the tail, but those are the easy cases.

Answer 3

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

Answer 4

Doubly Linked List Implementation Remove Methods (from my second programming assignment):

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

Are you asking for the name of a method in the api? That answer would simply be remove, assuming you are asking about java.util.LinkedList which is in fact a double linked list.

...or are you asking about what the name of the algorithm to remove an element from that type of data structure is called? Well.. the answer for that would also be to remove an element. Now for the actual algorithm to do it... it's really just a matter of changing the next pointer in the previous node and the last pointer in the next node. However, if you are using your data structure from multiple threads, you will need to either synchronize the remove method, or do the removal steps in an order that will make sense for your usage pattern for the data structure.

Answer 6

What about the current pointer pointer? You have to move crnt to the next node. http://pastebin.ca/1249635