Data Structures - Doubly Linked List Other Related Topics

Doubly Linked List - Delete first node by key



In this method, first node in the doubly linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->10->20 and the first occurrence of 20 is deleted, the List becomes 10->30->10->20.

First, the head of the doubly linked list is checked for null value. If the head is not null and the value stored in it is equal to the key, make head next as head, delete previous head, and adjust previous of head. Else, traverse to the node previous to the node with value equal to key, and adjust links.

The function pop_first is created for this purpose. It is a 3-step process.

void pop_first(int key) {     
  Node* temp = head;
  //1. check if the head is not null
  if(temp != NULL) {
    
    //2. if head is not null and value stored at head
    //   is equal to the key, make head next as head,
    //   delete previous head, adjust previous of head
    if(temp->data == key) {
      Node* nodeToDelete = head;
      head = head->next;
      free(nodeToDelete);
      if(head != NULL)
        head->prev = NULL;
    } else {

      //3. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while(temp->next != NULL) {
        if(temp->next->data == key) {
          Node* nodeToDelete = temp->next;
          temp->next = temp->next->next;
          if(temp->next != NULL)
            temp->next->prev = temp;          
          free(nodeToDelete);
          break; 
        }
        temp = temp->next;
      }
    }
  }
} 
void pop_first(struct Node** head_ref, int key) {     
  struct Node* temp = *head_ref;
  //1. check if the head is not null
  if(temp != NULL) {
    
    //2. if head is not null and value stored at head
    //   is equal to the key, make head next as head,
    //   delete previous head, adjust previous of head
    if(temp->data == key) {
      struct Node* nodeToDelete = *head_ref;
      *head_ref = (*head_ref)->next;
      free(nodeToDelete);
      if(*head_ref != NULL)
        (*head_ref)->prev = NULL;
    } else {

      //3. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while(temp->next != NULL) {
        if(temp->next->data == key) {
          struct Node* nodeToDelete = temp->next;
          temp->next = temp->next->next;
          if(temp->next != NULL)
            temp->next->prev = temp;   
          free(nodeToDelete);
          break; 
        }
        temp = temp->next;
      }
    }
  }
}    
def pop_first(self, key):     
  
  temp = self.head
  #1. check if the head is not null
  if(temp != None):
    
    #2. if head is not null and value stored at head
    #   is equal to the key, make head next as head,
    #   delete previous head, adjust previous of head
    if(temp.data == key):
      nodeToDelete = self.head
      self.head = self.head.next
      nodeToDelete = None
      if (self.head != None):
        self.head.prev = None
    else:

      #3. Else, traverse to the node previous to the 
      #   node with value equal to key, and adjust links 
      while(temp.next != None):
        if(temp.next.data == key):
          nodeToDelete = temp.next
          temp.next = temp.next.next
          if(temp.next != None):
            temp.next.prev = temp  
          nodeToDelete = None
          break

        temp = temp.next
void pop_first(int key) {     
  Node temp = head;
  //1. check if the head is not null
  if(temp != null) {
    
    //2. if head is not null and value stored at head
    //   is equal to the key, make head next as head,
    //   delete previous head, adjust previous of head
    if(temp.data == key) {
      Node nodeToDelete = head;
      head = head.next;
      nodeToDelete = null;
      if (head != null)
        head.prev = null;
    } else {

      //3. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while(temp.next != null) {
        if(temp.next.data == key) {
          Node nodeToDelete = temp.next;
          temp.next = temp.next.next;
          if(temp.next != null)
            temp.next.prev = temp;   
          nodeToDelete = null;
          break; 
        }
        temp = temp.next;
      }
    }
  }
} 
public void pop_first(int key) {     
  Node temp = head;
  //1. check if the head is not null
  if(temp != null) {
    
    //2. if head is not null and value stored at head
    //   is equal to the key, make head next as head,
    //   delete previous head, adjust previous of head
    if(temp.data == key) {
      Node nodeToDelete = head;
      head = head.next;
      nodeToDelete = null;
      if (head != null)
        head.prev = null;
    } else {

      //3. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while(temp.next != null) {
        if(temp.next.data == key) {
          Node nodeToDelete = temp.next;
          temp.next = temp.next.next;
          if(temp.next != null)
            temp.next.prev = temp;   
          nodeToDelete = null;
          break; 
        }
        temp = temp.next;
      }
    }
  }
} 
public function pop_first($key) {     
  $temp = $this->head;
  //1. check if the head is not null
  if($temp != null) {
    
    //2. if head is not null and value stored at head
    //   is equal to the key, make head next as head,
    //   delete previous head, adjust previous of head
    if($temp->data == $key) {
      $nodeToDelete = $this->head;
      $this->head = $this->head->next;
      $nodeToDelete = null;
      if ($this->head != null)
        $this->head->prev = null;
    } else {

      //3. Else, traverse to the node previous to the 
      //   node with value equal to key, and adjust links 
      while($temp->next != null) {
        if($temp->next->data == $key) {
          $nodeToDelete = $temp->next;
          $temp->next = $temp->next->next;
          if($temp->next != null)
            $temp->next->prev = $temp;   
          $nodeToDelete = null;
          break; 
        }
        $temp = $temp->next;
      }
    }
  }
} 

The below is a complete program that uses above discussed concept to delete first occurrence of the specified key (if exists) of the doubly linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
      } else {
        Node* temp = head;
        while(temp->next != NULL)
          temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
      }    
    }

    //Delete first node by key
    void pop_first(int key) {     
      Node* temp = head;
      if(temp != NULL) {
        if(temp->data == key) {
          Node* nodeToDelete = head;
          head = head->next;
          free(nodeToDelete);
          if(head != NULL)
            head->prev = NULL;
        } else {
          while(temp->next != NULL) {
            if(temp->next->data == key) {
              Node* nodeToDelete = temp->next;
              temp->next = temp->next->next;
              if(temp->next != NULL)
                temp->next->prev = temp;          
              free(nodeToDelete);
              break; 
            }
            temp = temp->next;
          }
        }
      }
    } 

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<"\n";
      } else {
        cout<<"The list is empty.\n";
      }
    }   
};

// test the code
int main() {
  LinkedList MyList;

  //Add five elements at the end of the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.PrintList();

  //Delete the first occurrence of 20
  MyList.pop_first(20);
  MyList.PrintList();

  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20 
#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  newNode->prev = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
  } else {
    temp = *head_ref;
    while(temp->next != NULL) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->prev = temp;
  }
}

//Delete first node by key
void pop_first(struct Node** head_ref, int key) {     
  struct Node* temp = *head_ref;
  if(temp != NULL) {
    if(temp->data == key) {
      struct Node* nodeToDelete = *head_ref;
      *head_ref = (*head_ref)->next;
      free(nodeToDelete);
      if(*head_ref != NULL)
        (*head_ref)->prev = NULL;
    } else {
      while(temp->next != NULL) {
        if(temp->next->data == key) {
          struct Node* nodeToDelete = temp->next;
          temp->next = temp->next->next;
          if(temp->next != NULL)
            temp->next->prev = temp;   
          free(nodeToDelete);
          break; 
        }
        temp = temp->next;
      }
    }
  }
}    

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (temp != NULL) {
      printf("%i ",temp->data);
      temp = temp->next;  
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code
int main() {
  struct Node* MyList = NULL;

  //Add five elements at the end of the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  PrintList(MyList);

  //Delete the first occurrence of 20
  pop_first(&MyList, 20);
  PrintList(MyList);  

  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20 
# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class LinkedList
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode
      newNode.prev = temp

  #Delete first node by key
  def pop_first(self, key):        
    temp = self.head
    if(temp != None):
      if(temp.data == key):
        nodeToDelete = self.head
        self.head = self.head.next
        nodeToDelete = None
        if (self.head != None):
          self.head.prev = None
      else:
        while(temp.next != None):
          if(temp.next.data == key):
            nodeToDelete = temp.next
            temp.next = temp.next.next
            if(temp.next != None):
              temp.next.prev = temp
            nodeToDelete = None
            break
          temp = temp.next

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      print()
    else:
      print("The list is empty.")

# test the code                
MyList = LinkedList()

#Add five elements at the end of the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(10)
MyList.push_back(20)
MyList.PrintList()

#Delete the first occurrence of 20
MyList.pop_first(20)
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20 
//node structure
class Node {
    int data;
    Node next;
    Node prev;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the end of the list
  void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null;
    newNode.prev = null; 
    if(head == null) {
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
      newNode.prev = temp;
    }    
  }

  //Delete first node by key
  void pop_first(int key) {     
    Node temp = head;
    if(temp != null) {
      if(temp.data == key) {
        Node nodeToDelete = head;
        head = head.next;
        nodeToDelete = null;
        if (head != null)
          head.prev = null;
      } else {
        while(temp.next != null) {
          if(temp.next.data == key) {
            Node nodeToDelete = temp.next;
            temp.next = temp.next.next;
            if(temp.next != null)
              temp.next.prev = temp;   
            nodeToDelete = null;
            break; 
          }
          temp = temp.next;
        }
      }
    }
  } 

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }    
};

// test the code
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements at the end of the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.PrintList();

    //Delete the first occurrence of 20
    MyList.pop_first(20);
    MyList.PrintList();    
  }
}

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20 
using System;

//node structure
class Node {
  public int data;
  public Node next;
  public Node prev;
};

class LinkedList {
  Node head;

  public LinkedList(){
    head = null;
  }
  
  //Add new element at the end of the list
  public void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    newNode.prev = null;
    if(head == null) {
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
      newNode.prev = temp;
    }    
  }

  //Delete first node by key
  public void pop_first(int key) {     
    Node temp = head;
    if(temp != null) {
      if(temp.data == key) {
        Node nodeToDelete = head;
        head = head.next;
        nodeToDelete = null;
        if (head != null)
          head.prev = null;
      } else {
        while(temp.next != null) {
          if(temp.next.data == key) {
            Node nodeToDelete = temp.next;
            temp.next = temp.next.next;
            if(temp.next != null)
              temp.next.prev = temp;   
            nodeToDelete = null;
            break; 
          }
          temp = temp.next;
        }
      }
    }
  } 

  //display the content of the list
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("The list contains: ");
      while(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
      Console.WriteLine();
    } else {
      Console.WriteLine("The list is empty.");
    }
  }     
};

// test the code
class Implementation {
  static void Main(string[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements at the end of the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.PrintList(); 

    //Delete the first occurrence of 20
    MyList.pop_first(20);
    MyList.PrintList();   
  }
}

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20 
<?php
//node structure
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //Add new element at the end of the list
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null;
    $newNode->prev = null; 
    if($this->head == null) {
      $this->head = $newNode;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->prev = $temp;
    }    
  }

  //Delete first node by key
  public function pop_first($key) {     
    $temp = $this->head;
    if($temp != null) {
      if($temp->data == $key) {
        $nodeToDelete = $this->head;
        $this->head = $this->head->next;
        $nodeToDelete = null;
        if ($this->head != null)
          $this->head->prev = null;
      } else {
        while($temp->next != null) {
          if($temp->next->data == $key) {
            $nodeToDelete = $temp->next;
            $temp->next = $temp->next->next;
            if($temp->next != null)
              $temp->next->prev = $temp;   
            $nodeToDelete = null;
            break; 
          }
          $temp = $temp->next;
        }
      }
    }
  } 

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }   
};

// test the code
$MyList = new LinkedList();

//Add five elements at the end of the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->PrintList();

//Delete the first occurrence of 20
$MyList->pop_first(20);
$MyList->PrintList();
?>

The above code will give the following output:

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 20