CODEWITHSUNDEEP
javadata-structureslinked-list
twodayslate
twodayslate

Reputation: 262

LinkedList remove method

What is a doubly linked list's remove method?

Upvotes: 9

Views: 41175

Answers (6)

Christian C. Salvadó
Christian C. Salvadó

Reputation: 827208

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

Remove From Linked List
(source: jaffasoft.co.uk)

Upvotes: 22

ashokgelal
ashokgelal

Reputation: 81528

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;
}

Upvotes: 1

albertein
albertein

Reputation: 27120

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

Upvotes: 4

twodayslate
twodayslate

Reputation: 262

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

Upvotes: 0

Bill the Lizard
Bill the Lizard

Reputation: 405695

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.

Upvotes: 19

kasperjj
kasperjj

Reputation: 3664

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.

Upvotes: 0

Related Questions