.png)
Insert at Beginning of Doubly Linked List
Problem
Given the head of a Doubly Linked List and a value X, insert a new node containing X at the beginning of the list and return the updated head.
A doubly linked list node contains:
- data → value stored
- prev → pointer to previous node
- next → pointer to next node
After insertion:
- New node becomes the new head
- Its prev = NULL
- Its next = old head
- Old head’s prev = new node
Approach 1 — Basic Pointer Adjustment
Steps
- Create a new node with value X.
- Set newNode.next = head.
- Set newNode.prev = NULL.
- If head is not NULL → set head.prev = newNode.
- Update head to newNode.
Time Complexity
O(1)
Space Complexity
O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* insertAtBeginning(struct Node* head, int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = head;
if (head != NULL)
head->prev = newNode;
return newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = NULL;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
return 0;
}
Output
20 10
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int x) {
data = x;
prev = NULL;
next = NULL;
}
};
Node* insertAtBeginning(Node* head, int x) {
Node* newNode = new Node(x);
newNode->next = head;
if (head != NULL)
head->prev = newNode;
return newNode;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = NULL;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
return 0;
}
Output
20 10
Java Implementation
class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public class Main {
static Node insertAtBeginning(Node head, int x) {
Node newNode = new Node(x);
newNode.next = head;
if (head != null)
head.prev = newNode;
return newNode;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node head = null;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
}
}
Output
20 10
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert_at_beginning(head, x):
new_node = Node(x)
new_node.next = head
if head:
head.prev = new_node
return new_node
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = None
head = insert_at_beginning(head, 10)
head = insert_at_beginning(head, 20)
print_list(head)
Output
20 10
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
function insertAtBeginning(head, x) {
let newNode = new Node(x);
newNode.next = head;
if (head !== null)
head.prev = newNode;
return newNode;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = null;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
Output
20 10
Approach 2 — Using Constructor + Helper Function
Idea
In this approach, we modularize the process by using a helper function (or constructor) to create the new node.
This improves code readability and reusability, especially in large implementations.
Instead of directly creating and linking the node inside the insertion function, we:
- Create the node using a helper function
- Handle empty list case separately
- Link pointers only if the list exists
- Return the new head
This approach is commonly used in production-level code where node creation logic may be reused.
Steps
- Create a new node using helper function
- If head is NULL
→ return new node (it becomes the head) - Otherwise
- Set newNode.next = head
- Set head.prev = newNode
- Return new node as new head
Time Complexity
O(1)
Insertion at the beginning does not depend on list size.
Only constant pointer updates are performed.
Space Complexity
O(1) auxiliary space
No extra memory except the new node being inserted.
Why This Approach is Useful
- Clean separation of responsibilities
- Reusable node creation logic
- Better for large projects
- Improves readability and maintainability
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* createNode(int x) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = x;
node->prev = NULL;
node->next = NULL;
return node;
}
struct Node* insertAtBeginning(struct Node* head, int x) {
struct Node* newNode = createNode(x);
if (head == NULL)
return newNode;
newNode->next = head;
head->prev = newNode;
return newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = NULL;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
return 0;
}
Output
20 10
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int x) {
data = x;
prev = NULL;
next = NULL;
}
};
Node* createNode(int x) {
return new Node(x);
}
Node* insertAtBeginning(Node* head, int x) {
Node* newNode = createNode(x);
if (head == NULL)
return newNode;
newNode->next = head;
head->prev = newNode;
return newNode;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = NULL;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
return 0;
}
Output
20 10
Java Implementation
class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public class Main {
static Node createNode(int x) {
return new Node(x);
}
static Node insertAtBeginning(Node head, int x) {
Node newNode = createNode(x);
if (head == null)
return newNode;
newNode.next = head;
head.prev = newNode;
return newNode;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node head = null;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
}
}
Output
20 10
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def create_node(x):
return Node(x)
def insert_at_beginning(head, x):
new_node = create_node(x)
if not head:
return new_node
new_node.next = head
head.prev = new_node
return new_node
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = None
head = insert_at_beginning(head, 10)
head = insert_at_beginning(head, 20)
print_list(head)
Output
20 10
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
function createNode(x) {
return new Node(x);
}
function insertAtBeginning(head, x) {
let newNode = createNode(x);
if (head === null)
return newNode;
newNode.next = head;
head.prev = newNode;
return newNode;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = null;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
printList(head);
Output
20 10
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
