.png)
Insert at End 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 end (tail) of the list and return the updated head.
Each node of a doubly linked list contains:
- data → value stored
- prev → pointer to previous node
- next → pointer to next node
After insertion at the end:
- New node becomes the last node
- Its next = NULL
- Its prev = old tail
- Old tail’s next = new node
If the list is empty, the new node becomes the head.
Example
Input List
10 ⇄ 20 ⇄ 30
Insert 40 at end
Output
10 ⇄ 20 ⇄ 30 ⇄ 40
Approach 1 — Traversal to the Last Node
Idea
Traverse the list from head until reaching the last node, then attach the new node there.
Steps
- Create a new node with value X
- If head is NULL
→ return new node as head - Traverse until current.next == NULL (last node)
- Set:
- current.next = newNode
- newNode.prev = current
- Return head
Time Complexity
O(N)
Because traversal of the list may be required.
Space Complexity
O(1) auxiliary space
No extra memory except the inserted node.
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* insertAtEnd(struct Node* head, int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = NULL;
head = insertAtEnd(head, 10);
head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);
printList(head);
return 0;
}Output
10 20 30
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 = next = NULL;
}
};
Node* insertAtEnd(Node* head, int x) {
Node* newNode = new Node(x);
if (head == NULL)
return newNode;
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = NULL;
head = insertAtEnd(head, 10);
head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);
printList(head);
return 0;
}Output
10 20 30
Java Implementation
class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public class Main {
static Node insertAtEnd(Node head, int x) {
Node newNode = new Node(x);
if (head == null)
return newNode;
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
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 = insertAtEnd(head, 10);
head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);
printList(head);
}
}
Output
10 20 30
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert_at_end(head, x):
new_node = Node(x)
if not head:
return new_node
temp = head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
return head
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = None
head = insert_at_end(head, 10)
head = insert_at_end(head, 20)
head = insert_at_end(head, 30)
print_list(head)
Output
10 20 30
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
function insertAtEnd(head, x) {
let newNode = new Node(x);
if (head === null)
return newNode;
let temp = head;
while (temp.next !== null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = null;
head = insertAtEnd(head, 10);
head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);
printList(head);
Output
10 20 30
Approach 2 — Using Tail Pointer (Optimized)
Idea
If a pointer to the tail is maintained, insertion at the end can be done in constant time without traversal.
Steps
- Create new node
- If list empty → head = tail = new node
- Else
- tail.next = newNode
- newNode.prev = tail
- Update tail = 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;
};
void insertAtEnd(struct Node** head, struct Node** tail, int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
if (*head == NULL) {
*head = *tail = newNode;
return;
}
(*tail)->next = newNode;
newNode->prev = *tail;
*tail = newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = NULL;
struct Node* tail = NULL;
insertAtEnd(&head, &tail, 10);
insertAtEnd(&head, &tail, 20);
insertAtEnd(&head, &tail, 30);
printList(head);
return 0;
}Output
10 20 30
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 = next = NULL;
}
};
void insertAtEnd(Node*& head, Node*& tail, int x) {
Node* newNode = new Node(x);
if (head == NULL) {
head = tail = newNode;
return;
}
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = NULL;
Node* tail = NULL;
insertAtEnd(head, tail, 10);
insertAtEnd(head, tail, 20);
insertAtEnd(head, tail, 30);
printList(head);
return 0;
}
Output
10 20 30
Java Implementation
class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public class Main {
static Node head = null;
static Node tail = null;
static void insertAtEnd(int x) {
Node newNode = new Node(x);
if (head == null) {
head = tail = newNode;
return;
}
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
static void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String[] args) {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
printList();
}
}
Output
10 20 30
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_end(self, x):
new_node = Node(x)
if not self.head:
self.head = self.tail = new_node
return
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
dll = DoublyLinkedList()
dll.insert_at_end(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.print_list()
Output
10 20 30
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
insertAtEnd(x) {
let newNode = new Node(x);
if (this.head === null) {
this.head = this.tail = newNode;
return;
}
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
printList() {
let temp = this.head;
while (temp !== null) {
process.stdout.write(temp.data + " ");
temp = temp.next;
}
}
}
let dll = new DoublyLinkedList();
dll.insertAtEnd(10);
dll.insertAtEnd(20);
dll.insertAtEnd(30);
dll.printList();
Output
10 20 30
.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)
