What is a doubly linked list's remove method?
I always use the sneaky trick of having a sentinal at the start and end of the list (so an empty list has two elements). This eases my code greatly, using a little more memory. Of course, the searches have to start at first->next and end at last->prev but I don't have to worry about the edge cases.
paxdiablo
2008-11-07 01:29:34
That is sneaky, but I like it. :)
Bill the Lizard
2008-11-07 01:40:36
Or store your list as a ring. There's only one sentinal, it appears at both head and tail, and an empty list consists of one element with both fields pointing to itself.
Steve Jessop
2008-11-07 02:28:46
A:
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.
kasperjj
2008-11-07 01:20:02
+3
A:
public void remove ()
{
if (getPreviousNode () != null)
getPreviousNode ().setNextNode (getNextNode ());
if (getNextNode () != null)
getNextNode ().setPreviousNode (getPreviousNode ());
}
AlbertEin
2008-11-07 01:49:29
That is applied to the node to be deleted (i.e. it doesn't "search" for the node). Yes, it is that simple.
Will Hartung
2008-11-07 02:24:11
Yeah, it deleted the current node. Gotcha. This is what I had before I posted the question.. my directions were a little different but I just wanted to see the default method to get an idea.
twodayslate
2008-11-07 02:32:52
public boolean remove() { if(crnt != null) { if(crnt == head) { head = crnt.getNext(); }
twodayslate
2008-11-07 02:33:32
if(crnt == tail) { tail = crnt.getPrev(); } ListNode<E> temp = crnt.getNext(); if(crnt.getNext() != null) {
twodayslate
2008-11-07 02:34:53
crnt.getNext().setPrev(crnt.getPrev()); } crnt.setPrev(null); crnt.setNext(null); crnt = temp; return true; } return false; }
twodayslate
2008-11-07 02:35:33
A:
What about the current pointer pointer? You have to move crnt to the next node. http://pastebin.ca/1249635
twodayslate
2008-11-09 17:31:56
+1
A:
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;
}
askgelal
2008-11-10 17:24:20