Skip to main content

Insert node at beginning of Doubly linked list

The problem involves inserting a new node at the beginning of a doubly linked list. A doubly linked list is a data structure where each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. Your task is to add a new node with a given value at the front of the doubly linked list.

Problem Statement

Given a doubly linked list and a value, you need to insert a new node containing that value at the beginning of the list.


Consider the following example:

Suppose we are inserted the following (80,70,60,50,40,30,20,10) node in a sequence.

insertion node at beginning

Initial doubly linked list:

NULL <- 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60 <-> 70 -> NULL

Value to be inserted: 5

After inserting the new node:

NULL <- 5 <-> 10 <-> 20 <-> 30 <-> 40 <-> 50 <-> 60 <-> 70 -> NULL

Idea to Solve

To solve this problem, you need to create a new node with the given value and insert it at the beginning of the linked list. You will have to update the next and prev pointers of the new node and the previous head node to maintain the integrity of the doubly linked list.


insert(doublyLinkedList, value):
    new_node = create_node(value) = doublyLinkedList.head
    if doublyLinkedList.head is not null:
        doublyLinkedList.head.prev = new_node
    doublyLinkedList.head = new_node

Algorithm Explanation

  1. Create a new node using the create_node function with the given value.
  2. Set the next pointer of the new node to the current head of the doubly linked list.
  3. If the current head is not null (i.e., the list is not empty), update the prev pointer of the current head node to point to the new node.
  4. Update the head of the doubly linked list to the new node.

Code Solution

Time Complexity

The time complexity of this insertion algorithm is O(1), which means it's constant time. This is because inserting a node at the beginning of the doubly linked list involves only a few constant-time pointer updates, regardless of the size of the list.


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment