Operations of Doubly Linked List with Implementation
A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in a singly linked list.
Below are operations on the given DLL:
- Add a node at the front of DLL: The new node is always added before the head of the given Linked List. And the newly added node becomes the new head of DLL & maintaining a global variable for counting the total number of nodes at that time.
- Traversal of a Doubly linked list
- Insertion of a node: This can be done in three ways:
- At the beginning: The new created node is insert in before the head node and head points to the new node.
- At the end: The new created node is insert at the end of the list and tail points to the new node.
- At a given position: Traverse the given DLL to that position(let the node be X) then do the following:
- Change the next pointer of new Node to the next pointer of Node X.
- Change the prev pointer of next Node of Node X to the new Node.
- Change the next pointer of node X to new Node.
- Change the prev pointer of new Node to the Node X.
- Deletion of a node: This can be done in three ways:
- At the beginning: Move head to the next node to delete the node at the beginning and make previous pointer of current head to NULL .
- At the last: Move tail to the previous node to delete the node at the end and make next pointer of tail node to NULL.
- At a given position: Let the prev node of Node at position pos be Node X and next node be Node Y, then do the following:
- Change the next pointer of Node X to Node Y.
- Change the previous pointer of Node Y to Node X.
Below is the implementation of all the operations:
C
// C program to implement all functions // used in Doubly Linked List #include <stdio.h> #include <stdlib.h> int i = 0; // Node for Doubly Linked List typedef struct node { int key; struct node* prev; struct node* next; } node; // Head, Tail, first & temp Node node* head = NULL; node* first = NULL; node* temp = NULL; node* tail = NULL; // Function to add a node in the // Doubly Linked List void addnode( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If Linked List is empty if (head == NULL) { head = ptr; first = head; tail = head; } // Else insert at the end of the // Linked List else { temp = ptr; first->next = temp; temp->prev = first; first = temp; tail = temp; } // Increment for number of Nodes // in the Doubly Linked List i++; } // Function to traverse the Doubly // Linked List void traverse() { // Nodes points towards head node node* ptr = head; // While pointer is not NULL, // traverse and print the node while (ptr != NULL) { // Print key of the node printf ( "%d " , ptr->key); ptr = ptr->next; } printf ( "\n" ); } // Function to insert a node at the // beginning of the linked list void insertatbegin( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If head is NULL if (head == NULL) { first = ptr; first = head; tail = head; } // Else insert at beginning and // change the head to current node else { temp = ptr; temp->next = head; head->prev = temp; head = temp; } i++; } // Function to insert Node at end void insertatend( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If head is NULL if (head == NULL) { first = ptr; first = head; tail = head; } // Else insert at the end else { temp = ptr; temp->prev = tail; tail->next = temp; tail = temp; } i++; } // Function to insert Node at any // position pos void insertatpos( int k, int pos) { // For Invalid Position if (pos < 1 || pos > i + 1) { printf ( "Please enter a" " valid position\n" ); } // If position is at the front, // then call insertatbegin() else if (pos == 1) { insertatbegin(k); } // Position is at length of Linked // list + 1, then insert at the end else if (pos == i + 1) { insertatend(k); } // Else traverse till position pos // and insert the Node else { node* src = head; // Move head pointer to pos while (pos--) { src = src->next; } // Allocate memory to new Node node **da, **ba; node* ptr = (node*) malloc ( sizeof (node)); ptr->next = NULL; ptr->prev = NULL; ptr->key = k; // Change the previous and next // pointer of the nodes inserted // with previous and next node ba = &src; da = &(src->prev); ptr->next = (*ba); ptr->prev = (*da); (*da)->next = ptr; (*ba)->prev = ptr; i++; } } // Function to delete node at the // beginning of the list void delatbegin() { // Move head to next and // decrease length by 1 head = head->next; i--; } // Function to delete at the end // of the list void delatend() { // Mode tail to the prev and // decrease length by 1 tail = tail->prev; tail->next = NULL; i--; } // Function to delete the node at // a given position pos void delatpos( int pos) { // If invalid position if (pos < 1 || pos > i + 1) { printf ( "Please enter a" " valid position\n" ); } // If position is 1, then // call delatbegin() else if (pos == 1) { delatbegin(); } // If position is at the end, then // call delatend() else if (pos == i) { delatend(); } // Else traverse till pos, and // delete the node at pos else { // Src node to find which // node to be deleted node* src = head; pos--; // Traverse node till pos while (pos--) { src = src->next; } // previous and after node // of the src node node **pre, **aft; pre = &(src->prev); aft = &(src->next); // Change the next and prev // pointer of pre and aft node (*pre)->next = (*aft); (*aft)->prev = (*pre); // Decrease the length of the // Linked List i--; } } // Driver Code int main() { // Adding node to the linked List addnode(2); addnode(4); addnode(9); addnode(1); addnode(21); addnode(22); // To print the linked List printf ( "Linked List: " ); traverse(); printf ( "\n" ); // To insert node at the beginning insertatbegin(1); printf ( "Linked List after" " inserting 1 " "at beginning: " ); traverse(); // To insert at the end insertatend(0); printf ( "Linked List after " "inserting 0 at end: " ); traverse(); // To insert Node with // value 44 after 3rd Node insertatpos(44, 3); printf ( "Linked List after " "inserting 44 " "after 3rd Node: " ); traverse(); printf ( "\n" ); // To delete node at the beginning delatbegin(); printf ( "Linked List after " "deleting node " "at beginning: " ); traverse(); // To delete at the end delatend(); printf ( "Linked List after " "deleting node at end: " ); traverse(); // To delete Node at position 5 printf ( "Linked List after " "deleting node " "at position 5: " ); delatpos(5); traverse(); return 0; } |
C++
// C++ program to implement all functions // used in Doubly Linked List #include <iostream> #include <stdlib.h> using namespace std; int i = 0; // Node for Doubly Linked List typedef struct node { int key; struct node* prev; struct node* next; } node; // Head, Tail, first & temp Node node* head = NULL; node* first = NULL; node* temp = NULL; node* tail = NULL; // Function to add a node in the // Doubly Linked List void addnode( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If Linked List is empty if (head == NULL) { head = ptr; first = head; tail = head; } // Else insert at the end of the // Linked List else { temp = ptr; first->next = temp; temp->prev = first; first = temp; tail = temp; } // Increment for number of Nodes // in the Doubly Linked List i++; } // Function to traverse the Doubly // Linked List void traverse() { // Nodes points towards head node node* ptr = head; // While pointer is not NULL, // traverse and print the node while (ptr != NULL) { // Print key of the node cout << " " << ptr->key; ptr = ptr->next; } cout << "\n" ; } // Function to insert a node at the // beginning of the linked list void insertatbegin( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If head is NULL if (head == NULL) { first = ptr; first = head; tail = head; } // Else insert at beginning and // change the head to current node else { temp = ptr; temp->next = head; head->prev = temp; head = temp; } i++; } // Function to insert Node at end void insertatend( int k) { // Allocating memory // to the Node ptr node* ptr = (node*) malloc ( sizeof (node)); // Assign Key to value k ptr->key = k; // Next and prev pointer to NULL ptr->next = NULL; ptr->prev = NULL; // If head is NULL if (head == NULL) { first = ptr; first = head; tail = head; } // Else insert at the end else { temp = ptr; temp->prev = tail; tail->next = temp; tail = temp; } i++; } // Function to insert Node at any // position pos void insertatpos( int k, int pos) { // For Invalid Position if (pos < 1 || pos > i + 1) { cout << "Please enter a" " valid position\n" ; } // If position is at the front, // then call insertatbegin() else if (pos == 1) { insertatbegin(k); } // Position is at length of Linked // list + 1, then insert at the end else if (pos == i + 1) { insertatend(k); } // Else traverse till position pos // and insert the Node else { node* src = head; // Move head pointer to pos while (pos--) { src = src->next; } // Allocate memory to new Node node **da, **ba; node* ptr = (node*) malloc ( sizeof (node)); ptr->next = NULL; ptr->prev = NULL; ptr->key = k; // Change the previous and next // pointer of the nodes inserted // with previous and next node ba = &src; da = &(src->prev); ptr->next = (*ba); ptr->prev = (*da); (*da)->next = ptr; (*ba)->prev = ptr; i++; } } // Function to delete node at the // beginning of the list void delatbegin() { // Move head to next and // decrease length by 1 head = head->next; i--; } // Function to delete at the end // of the list void delatend() { // Mode tail to the prev and // decrease length by 1 tail = tail->prev; tail->next = NULL; i--; } // Function to delete the node at // a given position pos void delatpos( int pos) { // If invalid position if (pos < 1 || pos > i + 1) { cout << "Please enter a" " valid position\n" ; } // If position is 1, then // call delatbegin() else if (pos == 1) { delatbegin(); } // If position is at the end, then // call delatend() else if (pos == i) { delatend(); } // Else traverse till pos, and // delete the node at pos else { // Src node to find which // node to be deleted node* src = head; pos--; // Traverse node till pos while (pos--) { src = src->next; } // previous and after node // of the src node node **pre, **aft; pre = &(src->prev); aft = &(src->next); // Change the next and prev // pointer of pre and aft node (*pre)->next = (*aft); (*aft)->prev = (*pre); // Decrease the length of the // Linked List i--; } } // Driver Code int main() { // Adding node to the linked List addnode(2); addnode(4); addnode(9); addnode(1); addnode(21); addnode(22); // To print the linked List cout << "Linked List: " ; traverse(); cout << "\n" ; // To insert node at the beginning insertatbegin(1); cout << "Linked List after" " inserting 1 " "at beginning: " ; traverse(); // To insert at the end insertatend(0); cout << "Linked List after " "inserting 0 at end: " ; traverse(); // To insert Node with // value 44 after 3rd Node insertatpos(44, 3); cout << "Linked List after " "inserting 44 " "after 3rd Node: " ; traverse(); cout << "\n" ; // To delete node at the beginning delatbegin(); cout << "Linked List after " "deleting node " "at beginning: " ; traverse(); // To delete at the end delatend(); cout << "Linked List after " "deleting node at end: " ; traverse(); // To delete Node at position 5 cout << "Linked List after " "deleting node " "at position 5: " ; delatpos(5); traverse(); return 0; } // this code is contributed by shivanisinghss2110 |
Java
import java.util.*; import java.lang.*; // Java program to implement all functions // used in Doubly Linked List // Node for Doubly Linked List class node{ int key; node prev; node next; node(){ prev = null ; next = null ; } } class Main{ static node head = null ; static node first = null ; static node tail = null ; static node temp = null ; static int i = 0 ; // Function to add a node in the // Doubly Linked List static void addnode( int k) { // Allocating memory // to the Node ptr node ptr = new node(); // Assign Key to value k ptr.key = k; // Next and prev pointer to NULL ptr.next = null ; ptr.prev = null ; // If Linked List is empty if (head == null ) { head = ptr; first = head; tail = head; } // Else insert at the end of the // Linked List else { temp = ptr; first.next = temp; temp.prev = first; first = temp; tail = temp; } // Increment for number of Nodes // in the Doubly Linked List i++; } // Function to traverse the Doubly // Linked List static void traverse() { // Nodes points towards head node node ptr = head; // While pointer is not NULL, // traverse and print the node while (ptr != null ) { // Print key of the node System.out.print( ptr.key+ " " ); ptr = ptr.next; } System.out.println(); } // Function to insert a node at the // beginning of the linked list static void insertatbegin( int k) { // Allocating memory // to the Node ptr node ptr = new node(); // Assign Key to value k ptr.key = k; // Next and prev pointer to NULL ptr.next = null ; ptr.prev = null ; // If head is NULL if (head == null ) { first = ptr; first = head; tail = head; } // Else insert at beginning and // change the head to current node else { temp = ptr; temp.next = head; head.prev = temp; head = temp; } i++; } // Function to insert Node at end static void insertatend( int k) { // Allocating memory // to the Node ptr node ptr= new node(); // Assign Key to value k ptr.key = k; // Next and prev pointer to NULL ptr.next = null ; ptr.prev = null ; // If head is NULL if (head == null ) { first = ptr; first = head; tail = head; } // Else insert at the end else { temp = ptr; temp.prev = tail; tail.next = temp; tail = temp; } i++; } // Function to insert Node at any // position pos static void insertatpos( int k, int pos) { // For Invalid Position if (pos < 1 || pos > i + 1 ) { System.out.println( "Please enter a valid position" ); } // If position is at the front, // then call insertatbegin() else if (pos == 1 ) { insertatbegin(k); } // Position is at length of Linked // list + 1, then insert at the end else if (pos == i + 1 ) { insertatend(k); } // Else traverse till position pos // and insert the Node else { node src = head; // Move head pointer to pos while (pos--!= 0 ) { src = src.next; } // Allocate memory to new Node node da, ba; node ptr = new node(); ptr.next = null ; ptr.prev = null ; ptr.key = k; // Change the previous and next // pointer of the nodes inserted // with previous and next node ba = src; da = (src.prev); ptr.next = (ba); ptr.prev = (da); da.next = ptr; ba.prev = ptr; i++; } } // Function to delete node at the // beginning of the list static void delatbegin() { // Move head to next and // decrease length by 1 head = head.next; i--; } // Function to delete at the end // of the list static void delatend() { // Mode tail to the prev and // decrease length by 1 tail = tail.prev; tail.next = null ; i--; } // Function to delete the node at // a given position pos static void delatpos( int pos) { // If invalid position if (pos < 1 || pos > i + 1 ) { System.out.println( "Please enter a valid position" ); } // If position is 1, then // call delatbegin() else if (pos == 1 ) { delatbegin(); } // If position is at the end, then // call delatend() else if (pos == i) { delatend(); } // Else traverse till pos, and // delete the node at pos else { // Src node to find which // node to be deleted node src = head; pos--; // Traverse node till pos while (pos--!= 0 ) { src = src.next; } // previous and after node // of the src node node pre, aft; pre = (src.prev); aft = (src.next); // Change the next and prev // pointer of pre and aft node pre.next = (aft); aft.prev = (pre); // Decrease the length of the // Linked List i--; } } public static void main(String args[]) { // Adding node to the linked List addnode( 2 ); addnode( 4 ); addnode( 9 ); addnode( 1 ); addnode( 21 ); addnode( 22 ); // To print the linked List System.out.print( "Linked List: " ); traverse(); System.out.println(); // To insert node at the beginning insertatbegin( 1 ); System.out.print( "Linked List after inserting 1 at beginning: " ); traverse(); // To insert at the end insertatend( 0 ); System.out.print( "Linked List after inserting 0 at end: " ); traverse(); // To insert Node with // value 44 after 3rd Node insertatpos( 44 , 3 ); System.out.print( "Linked List after inserting 44 after 3rd Node: " ); traverse(); System.out.println(); // To delete node at the beginning delatbegin(); System.out.print( "Linked List after deleting node at beginning: " ); traverse(); // To delete at the end delatend(); System.out.print( "Linked List after deleting node at end: " ); traverse(); // To delete Node at position 5 System.out.print( "Linked List after deleting node at position 5: " ); delatpos( 5 ); traverse(); } } |
Python3
# Python3 program to implement all functions # used in Doubly Linked List i = 0 # Node for Doubly Linked List class node: def __init__( self , k = 0 , p = None , n = None ): self .key = k self .prev = p self . next = n # Head, Tail, first & temp Node head = None first = None temp = None tail = None # Function to add a node in the # Doubly Linked List def addnode(k: int ): global i, head, first, tail # Allocating memory # to the Node ptr ptr = node(k) # If Linked List is empty if head = = None : head = ptr first = head tail = head # Else insert at the end of the # Linked List else : temp = ptr first. next = temp temp.prev = first first = temp tail = temp # Increment for number of Nodes # in the Doubly Linked List i + = 1 # Function to traverse the Doubly # Linked List def traverse(): # Nodes points towards head node ptr = head # While pointer is not None, # traverse and print the node while ptr ! = None : # Print key of the node print (ptr.key, end = " " ) ptr = ptr. next print () # Function to insert a node at the # beginning of the linked list def insertatbegin(k: int ): global head, first, tail, i # Allocating memory # to the Node ptr ptr = node(k) # If head is None if head = = None : first = ptr first = head tail = head # Else insert at beginning and # change the head to current node else : temp = ptr temp. next = head head.prev = temp head = temp i + = 1 # Function to insert Node at end def insertatend(k: int ): global head, first, tail, i # Allocating memory # to the Node ptr ptr = node(k) # If head is None if head = = None : first = ptr first = head tail = head # Else insert at the end else : temp = ptr temp.prev = tail tail. next = temp tail = temp i + = 1 # Function to insert Node at any # position pos def insertatpos(k: int , pos: int ): global i # For Invalid Position if pos < 1 or pos > i + 1 : print ( "Please enter a" " valid position" ) # If position is at the front, # then call insertatbegin() elif pos = = 1 : insertatbegin(k) # Position is at length of Linked # list + 1, then insert at the end elif pos = = i + 1 : insertatend(k) # Else traverse till position pos # and insert the Node else : src = head # Move head pointer to pos while pos: pos - = 1 src = src. next # Allocate memory to new Node ptr = node(k) # Change the previous and next # pointer of the nodes inserted # with previous and next node ptr. next = src ptr.prev = src.prev src.prev. next = ptr src.prev = ptr i + = 1 # Function to delete node at the # beginning of the list def delatbegin(): # Move head to next and # decrease length by 1 global head, i head = head. next i - = 1 # Function to delete at the end # of the list def delatend(): # Mode tail to the prev and # decrease length by 1 global tail, i tail = tail.prev tail. next = None i - = 1 # Function to delete the node at # a given position pos def delatpos(pos: int ): global i # If invalid position if pos < 1 or pos > i + 1 : print ( "Please enter a" " valid position" ) # If position is 1, then # call delatbegin() elif pos = = 1 : delatbegin() # If position is at the end, then # call delatend() elif pos = = i: delatend() # Else traverse till pos, and # delete the node at pos else : # Src node to find which # node to be deleted src = head pos - = 1 # Traverse node till pos while pos: pos - = 1 src = src. next # Change the next and prev # pointer of pre and aft node src.prev. next = src. next src. next .prev = src.prev # Decrease the length of the # Linked List i - = 1 # Driver Code if __name__ = = "__main__" : # Adding node to the linked List addnode( 2 ) addnode( 4 ) addnode( 9 ) addnode( 1 ) addnode( 21 ) addnode( 22 ) # To print the linked List print ( "Linked List: " ) traverse() print ( "\n" ) # To insert node at the beginning insertatbegin( 1 ) print ( "Linked List after inserting 1 at beginning: " ) traverse() # To insert at the end insertatend( 0 ) print ( "Linked List after inserting 0 at end: " ) traverse() # To insert Node with # value 44 after 3rd Node insertatpos( 44 , 3 ) print ( "Linked List after inserting 44 after 3rd Node: " ) traverse() print ( "\n" ) # To delete node at the beginning delatbegin() print ( "Linked List after deleting node at beginning: " ) traverse() # To delete at the end delatend() print ( "Linked List after deleting node at end: " ) traverse() # To delete Node at position 5 print ( "Linked List after deleting node at position 5: " ) delatpos( 5 ) traverse() |
C#
// C# program to implement all functions // used in Doubly Linked List using System; // Node for Doubly Linked List class Node { public int key; public Node prev; public Node next; public Node( int k = 0, Node p = null , Node n = null ) { key = k; prev = p; next = n; } } class LinkedList { // Head, Tail, first & temp Node static Node head = null ; static Node first = null ; static Node temp = null ; static Node tail = null ; static int i = 0; // Function to add a node in the // Doubly Linked List static void addnode( int k) { // Allocating memory // to the Node ptr Node ptr = new Node(k); // If Linked List is empty if (head == null ) { head = ptr; first = head; tail = head; } // Else insert at the end of the // Linked List else { temp = ptr; first.next = temp; temp.prev = first; first = temp; tail = temp; } // Increment for number of Nodes // in the Doubly Linked List i++; } // Function to traverse the Doubly // Linked List static void traverse() { // Nodes points towards head node Node ptr = head; // While pointer is not None, // traverse and print the node while (ptr != null ) { // Print key of the node Console.Write(ptr.key + " " ); ptr = ptr.next; } Console.WriteLine(); } // Function to insert a node at the // beginning of the linked list static void insertatbegin( int k) { // Allocating memory // to the Node ptr Node ptr = new Node(k); // If head is None if (head == null ) { first = ptr; first = head; tail = head; } // Else insert at beginning and // change the head to current node else { temp = ptr; temp.next = head; head.prev = temp; head = temp; } i++; } // Function to insert Node at end static void insertatend( int k) { // Allocating memory // to the Node ptr Node ptr = new Node(k); // If head is None if (head == null ) { first = ptr; first = head; tail = head; } // Else insert at the end else { temp = ptr; temp.prev = tail; tail.next = temp; tail = temp; } i++; } // Function to insert Node at any // position pos static void insertatpos( int k, int pos) { // For Invalid Position if (pos < 1 || pos > i + 1) { Console.WriteLine( "Please enter a valid position" ); } // If position is at the front, // then call insertatbegin() else if (pos == 1) { insertatbegin(k); } // Position is at length of Linked // list + 1, then insert at the end else if (pos == i + 1) { insertatend(k); } // Else traverse till position pos // and insert the Node else { Node src = head; // Move head pointer to pos while (pos > 0) { pos--; src = src.next; } // Allocate memory to new Node Node ptr = new Node(k); // Change the previous and next // pointer of the nodes inserted // with previous and next node ptr.next = src; ptr.prev = src.prev; src.prev.next = ptr; src.prev = ptr; i++; } } // Function to delete node at the // beginning of the list static void delatbegin() { // Move head to next and // decrease length by 1 head = head.next; i--; } // Function to delete at the end // of the list static void delatend() { // Mode tail to the prev and // decrease length by 1 tail = tail.prev; tail.next = null ; i--; } // Function to delete the node at // a given position pos static void delatpos( int pos) { // If invalid position if (pos < 1 || pos > i + 1) { Console.WriteLine( "Please enter a valid position" ); } // If position is 1, then // call delatbegin() else if (pos == 1) { delatbegin(); } // If position is at the end, then // call delatend() else if (pos == i) { delatend(); } // Else traverse till pos, and // delete the node at pos else { // Src node to find which // node to be deleted Node src = head; pos--; // Traverse node till pos while (pos > 0) { pos--; src = src.next; } // Change the next and prev // pointer of pre and aft node src.prev.next = src.next; src.next.prev = src.prev; // Decrease the length of the // Linked List i--; } } // Driver Code static void Main( string [] args) { // Adding node to the linked List addnode(2); addnode(4); addnode(9); addnode(1); addnode(21); addnode(22); // To print the linked List Console.WriteLine( "Linked List: " ); traverse(); Console.WriteLine( "\n" ); // To insert node at the beginning insertatbegin(1); Console.WriteLine( "Linked List after inserting 1 at beginning: " ); traverse(); // To insert at the end insertatend(0); Console.WriteLine( "Linked List after inserting 0 at end: " ); traverse(); // To insert Node with // value 44 after 3rd Node insertatpos(44, 3); Console.WriteLine( "Linked List after inserting 44 after 3rd Node: " ); traverse(); Console.WriteLine( "\n" ); delatbegin(); Console.WriteLine( "Linked List after deleting node at beginning: " ); traverse(); delatend(); Console.WriteLine( "Linked List after deleting node at end: " ); traverse(); // To delete Node at position 5 Console.WriteLine( "Linked List after deleting node at position 5: " ); delatpos(5); traverse(); } } // This code is contributed by Shivhack999 |
Javascript
function Node(value) { this .value = value; this .next = null ; } let head = null ; // Adding node to the linked List function addnode(value) { let node = new Node(value); if (head === null ) { head = node; } else { let current = head; while (current.next) { current = current.next; } current.next = node; } } // To print the linked List function traverse() { let current = head; while (current) { process.stdout.write(current.value + " " ); current = current.next; } } // To insert node at the beginning function insertatbegin(value) { let node = new Node(value); node.next = head; head = node; } // To insert at the end function insertatend(value) { let node = new Node(value); if (head === null ) { head = node; } else { let current = head; while (current.next) { current = current.next; } current.next = node; } } // To insert Node with value 44 after 3rd Node function insertatpos(value, position) { let node = new Node(value); if (head === null ) { head = node; } else { let current = head; let count = 1; while (count < position && current.next) { current = current.next; count++; } node.next = current.next; current.next = node; } } // To delete node at the beginning function delatbegin() { if (head !== null ) { head = head.next; } } // To delete at the end function delatend() { if (head === null ) { return ; } if (head.next === null ) { head = null ; return ; } let current = head; while (current.next.next) { current = current.next; } current.next = null ; } // To delete Node at position 5 function delatpos(position) { if (head === null ) { return ; } let current = head; if (position === 1) { head = current.next; return ; } let count = 1; let prev = null ; while (count < position && current.next) { prev = current; current = current.next; count++; } if (current === null ) { return ; } prev.next = current.next; } // Adding node to the linked List addnode(2); addnode(4); addnode(9); addnode(1); addnode(21); addnode(22); // To print the linked List process.stdout.write( "Linked List: " ); traverse(); process.stdout.write( "\n" ); // To insert node at the beginning insertatbegin(1); process.stdout.write( "Linked List after inserting 1 at beginning: " ); traverse(); process.stdout.write( "\n" ); // To insert at the end insertatend(0); process.stdout.write( "Linked List after inserting 0 at end: " ); traverse(); process.stdout.write( "\n" ); // To insert Node with value 44 after 3rd Node insertatpos(44, 3); process.stdout.write( "Linked List after inserting 44 after 3rd Node: " ); traverse(); process.stdout.write( "\n" ); // To delete node at the beginning delatbegin(); process.stdout.write( "Linked List after deleting node at beginning: " ); traverse(); process.stdout.write( "\n" ); // To delete at the end delatend(); process.stdout.write( "Linked List after deleting node at end: " ); traverse(); process.stdout.write( "\n" ); // To delete Node at position 5 delatpos(5); process.stdout.write( "Linked List after deleting node at position 5: " ); traverse(); process.stdout.write( "\n" ); |
Linked List: 2 4 9 1 21 22 Linked List after inserting 1 at beginning: 1 2 4 9 1 21 22 Linked List after inserting 0 at end: 1 2 4 9 1 21 22 0 Linked List after inserting 44 after 3rd Node: 1 2 4 44 9 1 21 22 0 Linked List after deleting node at beginning: 2 4 44 9 1 21 22 0 Linked List after deleting node at end: 2 4 44 9 1 21 22 Linked List after deleting node at position 5: 2 4 44 9 21 22
Time and Space of Complexity of Each Operation :
Add a node at the front of DLL:
Time Complexity: O(1)
Space Complexity: O(1)
Traversal of a Doubly linked list:
Time Complexity: O(n)
Space Complexity: O(1)
Insertion of a node at the beginning:
Time Complexity: O(1)
Space Complexity: O(1)
Insertion of a node at the end:
Time Complexity: O(1)
Space Complexity: O(1)
Insertion of a node at a given position:
Time Complexity: O(n)
Space Complexity: O(1)
Deletion of a node at the beginning:
Time Complexity: O(1)
Space Complexity: O(1)
Deletion of a node at the end:
Time Complexity: O(1)
Space Complexity: O(1)
Deletion of a node given the position:
Time Complexity: O(n)
Space Complexity: O(1)
Contact Us