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 :-)

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

• Deepak: How to make sure the node we are trying to delete is existing? Dont we need to find if the node is in the LL? In that case the worst case time complexity to find the element to be removed is O(n) isnt it?

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.

• paxdiablo: 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.
• Bill the Lizard: That is sneaky, but I like it. :)
• Steve Jessop: 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.
• Peck_conyon: after setting node.previous = null , node.next = null do we need to call garbage collector in java or c# ?

Answer 3

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

• Will Hartung: That is applied to the node to be deleted (i.e. it doesn't "search" for the node). Yes, it is that simple.
• twodayslate: 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: public boolean remove() { if(crnt != null) { if(crnt == head) { head = crnt.getNext(); }
• twodayslate: if(crnt == tail) { tail = crnt.getPrev(); } ListNode<E> temp = crnt.getNext(); if(crnt.getNext() != null) {
• twodayslate: crnt.getNext().setPrev(crnt.getPrev()); } crnt.setPrev(null); crnt.setNext(null); crnt = temp; return true; } return false; }

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.

• twodayslate: I was asking for the method body and signature.

Answer 6

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

Answer 7

https://i.sstatic.net/UmZuYNhE.jpg

The above image shows that, for the doubly linklist we want to remove the temp, that is the data to be removed , so the previous of temp is connected to the temp1, so this connection is give to the previous of tempe2. Also the connection to the temp2 is taken palace through temp.next , so this connection is given to the temp1.next for connecting with the temp2.image description here. This is a simple program to delete a particular element from the doublyLinked list in java.

public class DlinkedList {
 
// make a class for the doublyLinkedList;
 class Node{
 int data;
 Node next;
 Node prev;
 
 Node(int data){
 this.data = data;
 
 }
 }
 public Node head = null;
 public Node tail = null;
//method for deleting the particular element from the java
public void delete(int data) {
// here we created three node temp1, temp and temp2
 
 Node temp = head , temp1 = null, temp2 = null;
// this code for deleting the data , if the data is in head ;
 if(temp.data == data ) {
 head = temp.next;
 return;
 }
 while(temp != null && temp.data != data) {
// the temp is come in the middle with occupy the data to be deleted;
//while running the loop;
 temp1 = temp;
 temp = temp.next;
 temp2 = temp.next;
 
 }
 if(temp == null) {
 return;
 }if(temp== tail) {
 tail = temp2;
 tail.next = null;
 return;
 }
//this is code for actual deletion of our data;
 temp2.prev = temp.prev;
 temp1.next = temp.next;
 
 }