Insertion at a Specific Position of Doubly Linked List
To insert a node at a specific Position in doubly linked list, we can use the following steps:
- Traverse the list to find the node at the desired position.
- Create a new node with the data you want to insert.
- Adjust the pointers of the new node, the previous node, and the next node to include the new node in the list.
- Update the pointers of the neighboring nodes to maintain the doubly linked list structure.
Below is the implementation of the above approach:
#include <iostream>
using namespace std;
// Define the structure of a node in the doubly linked list
struct Node {
int data; // Data stored in the node
Node* prev; // Pointer to the previous node in the list
Node* next; // Pointer to the next node in the list
};
// Function to insert a node at a specific position in the doubly linked list
void insertAtPosition(Node** head, int position, int data) {
// Create a new node and allocate memory
Node* newNode = new Node();
// Set the data of the new node
newNode->data = data;
// Insert at the beginning of the list
if (position == 0) {
// New node points to the current head
newNode->next = *head;
// Previous of new node is null as it's the new head
newNode->prev = nullptr;
if (*head != nullptr) {
// If list is not empty, set the previous of old head to new node
(*head)->prev = newNode;
}
// Update the head to point to the new node
*head = newNode;
} else {
// Pointer to traverse the list
Node* current = *head;
// Counter to track the position
int count = 0;
// Traverse to the node at position - 1
while (current != nullptr && count < position - 1) {
current = current->next; // Move to the next node
count++; // Increment position counter
}
// If reached end of list and position not found
if (current == nullptr) {
// Inform user about out of range position
cout << "Position out of range" << endl;
return; // Exit function
}
// Insert the new node between current and current->next
newNode->next = current->next; // New node's next is set to current node's next
newNode->prev = current; // New node's previous is set to current node
if (current->next != nullptr) {
// If there's a node after current, set its previous to new node
current->next->prev = newNode;
}
// Set current node's next to the new node
current->next = newNode;
}
}
// Function to print the doubly linked list
void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Driver code to test the insertion function
int main() {
// Create an empty list
Node* head = nullptr;
// Insert elements at various positions
insertAtPosition(&head, 0, 10); // Insert 10 at position 0
insertAtPosition(&head, 1, 20); // Insert 20 at position 1
insertAtPosition(&head, 2, 30); // Insert 30 at position 2
// Print the list to verify the insertion
printList(head); // Expected output: 10 20 30
return 0;
}
// Node class represents each node in the doubly linked list
class Node {
int data;
Node prev;
Node next;
// Node constructor
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// DoublyLinkedList class represents the entire list
class DoublyLinkedList {
Node head;
// DoublyLinkedList constructor
public DoublyLinkedList() {
this.head = null;
}
// Method to insert a node at a specific position
public void insertAtPosition(int position, int data) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = this.head;
newNode.prev = null;
if (this.head != null) {
this.head.prev = newNode;
}
this.head = newNode;
} else {
Node current = this.head;
int count = 0;
while (current != null && count < position - 1) {
current = current.next;
count++;
}
if (current == null) {
System.out.println("Position out of range");
return;
}
newNode.next = current.next;
newNode.prev = current;
if (current.next != null) {
current.next.prev = newNode;
}
current.next = newNode;
}
}
}
// Main class
public class Main {
public static void main(String[] args) {
// Create a doubly linked list
DoublyLinkedList dll = new DoublyLinkedList();
// Insert nodes at specific positions
dll.insertAtPosition(0, 10);
dll.insertAtPosition(1, 20);
dll.insertAtPosition(2, 30);
// Print the list
Node current = dll.head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
}
class Node:
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insertAtPosition(self, position, data):
newNode = Node(data)
if position == 0:
newNode.next = self.head
newNode.prev = None
if self.head is not None:
self.head.prev = newNode
self.head = newNode
else:
current = self.head
count = 0
while current is not None and count < position - 1:
current = current.next
count += 1
if current is None:
print("Position out of range")
return
newNode.next = current.next
newNode.prev = current
if current.next is not None:
current.next.prev = newNode
current.next = newNode
# Create a doubly linked list
dll = DoublyLinkedList()
# Insert nodes at specific positions
dll.insertAtPosition(0, 10)
dll.insertAtPosition(1, 20)
dll.insertAtPosition(2, 30)
# Print the list
current = dll.head
while current:
print(current.data,end=" ")
current = current.next
// Define the structure of a node in the doubly linked list
class Node {
constructor(data) {
this.data = data; // Data stored in the node
this.prev = null; // Pointer to the previous node in the list
this.next = null; // Pointer to the next node in the list
}
}
// Function to insert a node at a specific position in the doubly linked list
function insertAtPosition(head, position, data) {
// Create a new node
const newNode = new Node(data);
// Insert at the beginning of the list
if (position === 0) {
// New node points to the current head
newNode.next = head;
// Previous of new node is null as it's the new head
newNode.prev = null;
if (head !== null) {
// If list is not empty, set the previous of old head to new node
head.prev = newNode;
}
// Update the head to point to the new node
return newNode;
}
let current = head;
let count = 0;
// Traverse to the node at position - 1
while (current !== null && count < position - 1) {
current = current.next;
count++;
}
// If reached end of list and position not found
if (current === null) {
console.log("Position out of range");
return head; // Return the original head unchanged
}
// Insert the new node between current and current.next
newNode.next = current.next;
newNode.prev = current;
if (current.next !== null) {
// If there's a node after current, set its previous to new node
current.next.prev = newNode;
}
// Set current node's next to the new node
current.next = newNode;
return head;
}
// Function to print the doubly linked list
function printList(head) {
let current = head;
while (current !== null) {
console.log(current.data);
current = current.next;
}
}
// Driver code to test the insertion function
(function main() {
// Create an empty list
let head = null;
// Insert elements at various positions
head = insertAtPosition(head, 0, 10); // Insert 10 at position 0
head = insertAtPosition(head, 1, 20); // Insert 20 at position 1
head = insertAtPosition(head, 2, 30); // Insert 30 at position 2
// Print the list to verify the insertion
printList(head); // Expected output: 10 20 30
})();
// This code is contributed by Shivam Gupta
Doubly Linked List Tutorial
A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.
Doubly Linked List in Data Structure