Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Doubly Linked List – Introduction and Insertion

Last Updated on June 15, 2022 by Ria Pathak

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

A doubly linked list is a list that contains links to the next and previous nodes. We know that in a singly linked list, we can only traverse forward. But, in a doubly linked list, we can traverse both in a forward and backward manner.

• A doubly linked list can be traversed both in the forward and backward directions.
• If the pointer to the node to be deleted is given, then the delete operation in a doubly-linked list is more efficient.
• Insertion of a new node before a given node is more efficient.

• Extra space is required to store the previous pointer.
• All operations of a doubly-linked list require an extra previous pointer to be maintained. We have to modify the previous pointers together with the next pointer.

### Insertion in a doubly-linked list

#### Insert at the beginning.

In this approach, the new node is always added at the start of the given doubly linked list, and the newly added node becomes the new head.

#### Approach

The approach is going to be very simple. We’ll make the next of the new node point to the head. Then, we will make the previous pointer of head point to the new node. Lastly, we will make the new node the new head.

#### Algorithm

• Allocate the new node and put in the data
• Make the next of the new node as head and previous as NULL.
• If the head is not pointing to NULL, then change the previous pointer of the head node to the new node.
• Make the new node the new head.

### Dry Run

#### Code Implementation

```void push(struct Node** head_ref, int new_data)
{
struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));

NewNode->data = new_data;

NewNode->prev = NULL;

}
```
```public void push(int new_data)
{

Node new_Node = new Node(new_data);

new_Node.prev = null;

}
```
```def push(self, new_data):

new_node = Node(data = new_data)
new_node.prev = None

```

Time Complexity: O(1), as no traversal is needed.
Space Complexity: O(1), as no extra space is required.

#### Insert at the end

In this approach, the new node will always be added after the last node of the given doubly linked list.

#### Approach

The approach is going to be very simple. Firstly, we have to traverse till the end of the list. After reaching the last node, we will make it point to the new node. After this step, we will make the previous pointer of the new node point to the last node.

#### Algorithm

• Allocate the new node and put in the data.
• As the new node is going to be the last, so the next of this new node will be NULL.
• If the linked list is empty, then simply make the new node as the head node and return.
• Else, traverse till the end of the doubly linked list and make the next of the last node point to the new node.
• Lastly, make the prev of the new node point to the last node.

#### Code Implementation

```void append(struct Node** head_ref, int new_data)
{
struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));

NewNode->data = new_data;

NewNode->next = NULL;

NewNode->prev = NULL;
return;
}

while (last->next != NULL)
last = last->next;

last->next = NewNode;

NewNode->prev = last;

return;
}
```
```void append(int new_data)
{

Node new_node = new Node(new_data);

new_node.next = null;

new_node.prev = null;
return;
}

while (last.next != null)
last = last.next;

last.next = new_node;

new_node.prev = last;
}
```
```def append(self, new_data):
new_node = Node(data = new_data)
new_node.next = None

new_node.prev = None
return

while (last.next is not None):
last = last.next

last.next = new_node
new_node.prev = last
```

Time Complexity: O(n), as one traversal is needed.
Space Complexity: O(1), as no extra space is required apart from the creation of node, which takes 20 bytes.

#### Insert after a given node

In this approach, the new node will always be added after a given node.

#### Approach

The approach is going to be very simple. We are given a pointer to a node as prev_node. The new node is to be inserted after prev_node.

As we have the pointer to that node (prev_node), we can perform this operation in O(1) time. Firstly, we will create the new node. Now, we will make the new node point to the next of prev_node. By doing this, we are making the new node point to the next node of prev_node.

Now, prev will point to the new node. Now, we just have to change the necessary links. So, we will make prev_node as the previous of the new node. In the end, if the new node is not the last node, we will make the new node’ s next node’s prev as the new node. By doing this, we are making the previous of the next node of the new node point to the new node.

#### Algorithm

• Allocate the new node and put in the data.
• Make the new node point to the next of prev_node.
• Now, make the prev_node point to the new node.
• The previous of the new node will point to the prev_node.
• If the new node is not the last node, it’s next’s previous point to the new node. By doing this, the new node becomes the previous of the next of the new node.
• If the linked list is empty, then simply make the new node as the head node and return.

### Dry Run

#### Code Implementation

```void insertAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = prev_node->next;

prev_node->next = new_node;

new_node->prev = prev_node;

if (new_node->next != NULL)
new_node->next->prev = new_node;
}
```
```public void InsertAfter(Node prev_Node, int new_data)
{

if (prev_Node == null) {
System.out.println("The given previous node cannot be NULL ");
return;
}

Node new_node = new Node(new_data);

new_node.next = prev_Node.next;

prev_Node.next = new_node;

new_node.prev = prev_Node;

if (new_node.next != null)
new_node.next.prev = new_node;
}
```
```def insertAfter(self, prev_node, new_data):

if prev_node is None:
print("the given previous node cannot be NULL")
return

new_node = Node(data = new_data)
new_node.next = prev_node.next
prev_node.next = new_node
new_node.prev = prev_node

if new_node.next is not None:
new_node.next.prev = new_node
```

Time Complexity: O(1), as no traversal is needed.
Space Complexity: O(1), as no extra space is required.

#### Insert before a given node

In this approach, the new node will always be added before a given node.

#### Approach

The approach is going to be very simple. We are given a pointer to a node as next_node. The new node is to be inserted before next_node.

As we have the pointer to that node (next_node), we can perform this operation in O(1) time. Firstly, we will create the new node. Now, we will make the previous of the new node as the previous of the next_node. By doing this, we are trying to add the new node in between the next_node and the previous node of the next node.

Now, the previous of the next node will point to the new node and the next of the new node will point to the next_node. Now, if the previous of the new node is not NULL, then the next of the previous node of the new node will point to the new node. By doing this, the we are changing the appropriate links.

If the previous of the new node is NULL, it means that the new node is the first node in the list, hence it will become our new head.

#### Algorithm

• Allocate the new node and put in the data.
• Make the previous of the new node point to the previous of the next node.
• The previous of the next_node will point to the new node.
• The new node will point to the next_node
• If the new node is not the head of the list, then the next of the previous of the new node will point to the new node. Else, the new node will become the head of the list.

### Dry Run

#### Code Implementation

```void insertBefore(struct Node** head_ref,
struct Node* next_node, int new_data)
{

if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));

new_node->data = 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
}
```
```void insertBefore(Node head_ref, Node next_node,int new_data)
{
if(nex_node==null)
{
System.out.println("the display next node cannot be null");
return;
}
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
{
}
}
```
```def insertBefore(self, next_node, new_data):

if next_node is None:
print("the given next node cannot be NULL")
return

new_node = Node(new_data)
new_node.prev = next_node.prev
next_node.prev = new_node
new_node.next = next_node

if new_node.prev:
new_node.prev.next = new_node

else: