Insertion at the End in Doubly Linked List
The new node is always added after the last node of the given Linked List. This can be done using the following steps:
- Create a new node (say new_node).
- Put the value in the new node.
- Make the next pointer of new_node as null.
- If the list is empty, make new_node as the head.
- Otherwise, travel to the end of the linked list.
- Now make the next pointer of last node point to new_node.
- Change the previous pointer of new_node to the last node of the list.
Below is the implementation of the steps to insert a node at the end of the linked list:
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(Node** head_ref, int new_data)
{
// 1. allocate node
Node* new_node = new Node();
Node* last = *head_ref; /* used in step 5*/
// 2. put in the data
new_node->data = new_data;
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node->next = NULL;
// 4. If the Linked List is empty, then make the new
// node as head
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// 5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
// 7. Make last node as previous of new node
new_node->prev = last;
return;
}
// This code is contributed by shivanisinghss2110
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(struct Node** head_ref, int new_data)
{
// 1. allocate node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
// 2. put in the data
new_node->data = new_data;
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node->next = NULL;
// 4. If the Linked List is empty, then make the new
// node as head
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// 5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
// 7. Make last node as previous of new node
new_node->prev = last;
return;
}
// Add a node at the end of the list
void append(int new_data)
{
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node.next = null;
// 4. If the Linked List is empty, then make the new
// node as head
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// 5. Else traverse till the last node
while (last.next != null)
last = last.next;
// 6. Change the next of last node
last.next = new_node;
// 7. Make last node as previous of new node
new_node.prev = last;
}
// Add a node at the end of the list
void append(int new_data)
{
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
// 3. This new node is going
// to be the last node, so
// make next of it as NULL
new_node.next = null;
// 4. If the Linked List is empty,
// then make the new node as head
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// 5. Else traverse till the last node
while (last.next != null)
last = last.next;
// 6. Change the next of last node
last.next = new_node;
// 7. Make last node as previous of new node
new_node.prev = last;
}
// This code is contributed by shivanisinghss2110
<script>
// Add a node at the end of the list
function append(new_data)
{
/* 1. allocate node
* 2. put in the data */
var new_node = new Node(new_data);
var last = head; /* used in step 5*/
/* 3. This new node is going to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
* node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// This code is contributed by Rajput-Ji
</script>
# Add a node at the end of the DLL
def append(self, new_data):
# 1. allocate node
# 2. put in the data
new_node = Node(data=new_data)
last = self.head
# 3. This new node is going to be the
# last node, so make next of it as NULL
new_node.next = None
# 4. If the Linked List is empty, then
# make the new node as head
if self.head is None:
new_node.prev = None
self.head = new_node
return
# 5. Else traverse till the last node
while (last.next is not None):
last = last.next
# 6. Change the next of last node
last.next = new_node
# 7. Make last node as previous of new node */
new_node.prev = last
# This code is contributed by jatinreaper
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Articles:
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.