Insertion at the Beginning in Doubly Linked List
To insert a new node at the beginning of the doubly list, we can use the following steps:
- Allocate memory for a new node (say new_node) and assign the provided value to its data field.
- Set the previous pointer of the new_node to nullptr.
- If the list is empty:
- Set the next pointer of the new_node to nullptr.
- Update the head pointer to point to the new_node.
- If the list is not empty:
- Set the next pointer of the new_node to the current head.
- Update the previous pointer of the current head to point to the new_node.
- Update the head pointer to point to the new_node.
Below is the implementation of the 5 steps to insert a node at the front of the linked list:
// Given a reference (pointer to pointer) to the head
// of a list and an int, inserts a new node
// on the front of the list.
void push(Node** head_ref, int new_data)
{
// 1. allocate node
Node* new_node = new Node();
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as head
// and previous as NULL
new_node->next = (*head_ref);
new_node->prev = NULL;
// 4. change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// 5. move the head to point to the new node
(*head_ref) = new_node;
}
// This code is contributed by shivanisinghss2110
// Given a reference (pointer to pointer) to the head
// of a list and an int, inserts a new node
// on the front of the list.
void push(struct Node** head_ref, int new_data)
{
// 1. allocate node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as head and previous as NULL
new_node->next = (*head_ref);
new_node->prev = NULL;
// 4. change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// 5. move the head to point to the new node
(*head_ref) = new_node;
}
// Adding a node at the front of the list
public void push(int new_data)
{
// 1. allocate node
// 2. put in the data */
Node new_Node = new Node(new_data);
// 3. Make next of new node as head and previous as NULL
new_Node.next = head;
new_Node.prev = null;
// 4. change prev of head node to new node
if (head != null)
head.prev = new_Node;
// 5. move the head to point to the new node
head = new_Node;
}
// Adding a node at the front of the list
public void push(int new_data)
{
// 1. allocate node
// 2. put in the data
Node new_Node = new Node(new_data);
// 3. Make next of new node as head and previous as NULL
new_Node.next = head;
new_Node.prev = null;
// 4. change prev of head node to new node
if (head != null)
head.prev = new_Node;
// 5. move the head to point to the new node
head = new_Node;
}
// This code is contributed by aashish1995
// Adding a node at the front of the list
function push(new_data)
{
// 1. allocate node
// 2. put in the data
let new_Node = new Node(new_data);
// 3. Make next of new node as head and previous as NULL
new_Node.next = head;
new_Node.prev = null;
// 4. change prev of head node to new node
if (head != null)
head.prev = new_Node;
// 5. move the head to point to the new node
head = new_Node;
}
// This code is contributed by saurabh_jaiswal.
# Adding a node at the front of the list
def push(self, new_data):
# 1 & 2: Allocate the Node & Put in the data
new_node = Node(data=new_data)
# 3. Make next of new node as head and previous as NULL
new_node.next = self.head
new_node.prev = None
# 4. change prev of head node to new node
if self.head is not None:
self.head.prev = new_node
# 5. move the head to point to the new node
self.head = new_node
# This code is contributed by jatinreaper
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion in a Doubly Linked List
Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in four ways:
- At the front of the DLL.
- In between two nodes
- After a given node.
- Before a given node.
- At the end of the DLL.