Insert node at beginning of circular doubly linked list
The problem involves inserting a new node at the beginning of a circular doubly linked list. A circular doubly linked list is a data structure in which each node has pointers to both its previous and next nodes, and the last node's next pointer points back to the first node, creating a loop.
Problem Statement
Given a circular doubly linked list, the task is to insert a new node at the beginning of the list while maintaining the circular structure.
Example
Consider the circular doubly linked list: 1 <-> 2 <-> 3 <-> 4 <-> 5. After inserting a new node with value 6 at the beginning, the list will become: 6 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6.
Idea to Solve the Problem

To insert a new node at the beginning of a circular doubly linked list, we need to follow these steps:
- Create the new node with the given value.
- If the list is empty, make the new node both the head and the tail.
- Otherwise, update the pointers of the new node and the existing nodes to insert the new node at the beginning.
- Finally, update the head pointer to point to the new node.
Pseudocode
Here's the pseudocode to insert a node at the beginning of a circular doubly linked list:
function insert(value):
// Create a new node
new_node = createNode(value)
if head is NULL:
// List is empty
head = new_node
tail = new_node
else:
head.prev = new_node
tail.next = new_node
new_node.next = head
new_node.prev = tail
head = new_node
Algorithm Explanation
- Create a new node with the given value using the
createNode
function. - Check if the linked list is empty. If it is, make the new node both the head and the tail.
- If the list is not empty, update the
prev
pointer of the current head node and thenext
pointer of the current tail node to point to the new node. - Update the
next
pointer of the new node to point to the current head node and theprev
pointer to point to the current tail node. - Finally, update the head pointer to point to the new node.
Program List
-
1) Insertion at beginning of circular doubly linked list in java
2) Insertion at beginning of circular doubly linked list in c++
3) Insertion at beginning of circular doubly linked list in c
4) Insertion at beginning of circular doubly linked list in c#
5) Insertion at beginning of circular doubly linked list in php
6) Insertion at beginning of circular doubly linked list in python
7) Insertion at beginning of circular doubly linked list in ruby
8) Insertion at beginning of circular doubly linked list in scala
9) Insertion at beginning of circular doubly linked list in swift
10) Insertion at beginning of circular doubly linked list in kotlin
11) Insertion at beginning of circular doubly linked list in golang
12) Insertion at beginning of circular doubly linked list in node js
13) Insertion at beginning of circular doubly linked list in vb.net
14) Insertion at beginning of circular doubly linked list in typescript
Resultant Output Explanation
For the provided example with the circular doubly linked list: 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1, the program will correctly insert a new node with value 9 at the beginning of the list. This will create a new circular doubly linked list: 9 <-> 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> 9.
Time Complexity
The time complexity of inserting a node at the beginning of a circular doubly linked list is O(1), as it involves a constant number of pointer updates.
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