Insertion in Doubly Linked Lists

 

Alright so for this post we are going to tackle a very basic question- What do we do when we want to go anywhere in the linked list? 

The thing with a normal single linked list is that it is unidirectional which in essence is easy to understand but less efficient to work with, it brings with it a set of advantages and disadvantages. To tackle some basic disadvantages we include another pointer in the node family, Enter 'Prev' pointer. This pointer along with 'Next' pointer works seamlessly to define the position of a node with respect to not only what is after that node but also what is in front of that node. 

Some of it's advantages are -

  • A doubly linked list can be traversed in both directions
  • The deletion in DLL is more efficient if pointer to the node to be deleted is given 
  • We can quickly insert a new node.
 Function : Add a node at front 

void insertatfront(Node * head, int new_data)

{

     Node* new_node= new Node(new_data);

     new_node->next= head;

     new_node->prev=NULL;

    if(head!=NULL)

        head->prev= new_node;    

    head=new_node;

}


Here we have defined a new node with pointers prev and next, prev points to NULL value and next points to the old head value, then we update the head to the new node value as Head must always stay in front.

Function: Add a node after a given node

void addafter(Node* previous_node, int new_data)

{

    if(previous_node=NULL)

         return;

    Node* new_node= new Node(new_data);

    new_node->prev=previous_node;

    new_node->next=previous_node->next;

    if(new_node->next!=NULL)

            new_node->next->prev=new_node;

}

Here we have defined a new node with its previous pointer pointing to the previous node value, it's next pointer pointing to the previous node's next pointer, The if condition is needed to update the previous pointer of new node.

Function: Add node at the end 

void addend(Node* head, int new_data)

{

    Node* new_node= new Node(new_data);

    new_node->next=NULL;

    if(head==NULL)

           new_node->prev= NULL;

           head= new_node;

           return;

    while(last->next!=NULL)    

        last=last->next;

    last->next=new_node;

    new_node->prev=last;

    return;

}

In this specific function we have a new node, The if condition checks if head is empty or not and the while loop traverses until the last node, once we have traversed to the end of the list, we add our new_node and define the next pointer as NULL and prev pointer as last node value.


Function: Add a node before a given node

void addbefore(Node* head, Node* next_node, int new_data)

{

        Node* new_node= new Node(new_data);

        new_node->prev=next_node->prev;

        next_node->prev=new_node;

        new_node->next=next_node;

        if(new_node->prev!=NULL)

            new_node->prev->next=new_node;

        else

                nead=new_node;

}


Here we have a new_node which is added before next_node, the pointers of new_node i.e Next points to next_node, the Prev pointer points to prev of the next_node, If the new_node's previous pointer is not pointing to null, then we update the next previous pointer of the new node as the new_node value, hence making sure the new_node remains at the specified position, An else condition is added in case the prev pointer points to NULL which means it is the first node in the whole list, hence Head is updated as new_node.


Oh wow, that was a lot of explaining, I must say i've got quite a grasp on the subject of linked lists now! 

Next post is going to be something different! See you soon guys! 




Popular posts from this blog

Finding the Subarrays (Hackerearth)

Image
Finding subarrays can become a cumbersome task to handle if we don't know the right approach for it. In this particular question we will be using a new method.  Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit. Such as vector<first attribute, second attribute>. To access these attributes we use keywords 'first' and 'second' Approach - Input values and find total sum of all terms Create a loop and calculate average term by term, use logic ->  sum= first element this_average=sum/elements in the sum SZ= Elements left in array= size-elements in sum other_average=(total-sum)/SZ Use if loop to find whether this_average is bigger than other_average or not. If true, input the (i+1)th and (j+1)th element in the pair, Increment counter by 1 Sort the pair and output it. Code- #include< bits/stdc++.h > using namespace std ; int main () {       ...
Read more

Palindrome Index (Hackerrank)

Image
Here we have another Hackerrank question on String manipulation, this one involving the classic Palindrome index.  Question-  Approach - Pretty simple, we just need to check values one by one, iterating a loop from index 0 being compared to index n, where n is the last value in the index, narrowing it down to inner values one by one. The point where the elements do not stay equal is the point where element needs to be removed in order to make the string into a palindrome  The steps are -  initialise i = 0; j= string.length()-1 //last value in the string Run a loop from i to middle of the string, i increments while j decrements, bringing us a section to focus on within the string Run an if condition which checks whether character at i is equal to j or not If it is not equal, we check if the element after character at i is equal to j or not If yes, we check whether the element before j is equal to character at i and character after i is subsequently equal to element at...
Read more

Sherlock and Array (Hackerrank)

Image
Sometimes it's better to stop and first formulate a way to solve a problem before jumping right into it. Why? Well because it gives you more time to better understand a problem and secondly, in some cases even a simpler way to solve a problem.  Remember kids! When solving algorithms, Math is your friend! I realized that a little late into this question and when i did, it was just a 5 min snippet. Question-  Approach - It's quite simple and straight forward.  Instead of dividing array into two halves, getting their sums, checking whether the sums are equal and trying to find out if an element which causes sum to be unequal exist or not, here's a better approach. array - [5,6,8,11] , here we have 5+6=11 in LHS and 11 in RHS with 8 being an extra element. Imagine LHS and RHS as same, ex - x+y+x= sum. i.e 2x= sum-y. Here we just need to check if this equality holds, if it does we print YES and add value to x, else we print NO Code- 
Read more