Doubly linked list insert at position Python
Doubly Linked ListAbhishek Kumar Category: Data Structures Tags: datastructures linkedlistA Doubly Linked List is a linear data structure which collectively represents a sequence of data in which each node has three parts. Show
Table of contents
A Doubly Linked List is a collection of nodes in which each node has three parts i.e, pointer to previous node, data and pointer to next node and last node points to null. Declaration of type node for Doubly Linked ListWe have to create a data structure or Node which contains three part i.e, first part contains address of previous node, second part contains data of the node and third node contains address of next pointer. We can create this by using user defined data type (depends on the programming language used).
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None class Node {
constructor(data) {
this.prev = null;
this.data = data;
this.next = null;
}
} Traversing the Doubly Linked ListTraversing means visiting all the node once i.e, we want to read all the data available in the doubly linked list. Simply, use a temporary variable and initialize it with the head node so that we can start with the begining of the list and then go through all the nodes one by one till the last node is reached. And we can get the last node by checking the next value of node i.e., if next value of node is null then this is the end of node.
def traverse(self):
if self.head:
temp = self.head
while temp:
print(temp.data)
temp = temp.next
else:
print(None) traverse() {
if (this.head) {
let temp = this.head;
while (temp) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
} Reverse traversing of the Doubly Linked ListReverse traversing means visiting all the node once from the backward direction i.e, we want to read all the data available in the doubly linked list from the tail. Simply, use a temporary variable and initialize it with the tail node so that we can start with the end of the list and then go through all the nodes one by one till the first node is reached. And we can get the first node by checking the next value of node i.e., if next value of node is null then this is the begining of node.
def reverse_traverse(self):
if self.tail:
temp = self.tail
while temp:
print(temp.data)
temp = temp.prev
else:
print(None) reverseTraverse() {
if (this.tail) {
let temp = this.tail;
while (temp) {
console.log(temp.data);
temp = temp.prev;
}
} else {
console.log(null);
}
} Length of a Doubly Linked ListTo find length of a linked list we can simply use a temporary variable and initialize it by assigning the head node. Now, move it to every node one by one and increase the counter variable.
def length(self):
temp = self.head
count = 0
while temp:
count += 1
temp = temp.next
return count length() {
let temp = this.head;
let count = 0;
while (temp) {
count++;
temp = temp.next;
}
return count;
} Insertion in a Doubly Linked ListInsertion in a Linked List can be done in following three ways:
Insertion at the begining of the Doubly Linked ListWhile inserting a node at the begining position, two situation may arise:
def insert_at_start(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node insertAtStart(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} Insertion at the end of the Doubly Linked ListWhile inserting a node at the end position, two situation may arise:
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node insertAtEnd(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
} Insertion at given position in the Doubly Linked ListWhile inserting at any given position following 3 situation may arise based on user input:
def insert_at_position(self, pos, data):
new_node = Node(data)
if pos < 0 or pos > self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node.next = temp.next
temp.next = new_node
new_node.prev = temp insertAtPosition(pos, data) {
const newNode = new Node(data);
if (pos < 0 || pos > this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
this.insertAtStart(data);
} else if (pos == this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
}
} Deletion in a Doubly Linked ListSame as insertion deletion in a Linked List can be done in 3 ways:
Deletion from the begining of the Doubly Linked ListWhile deleting a node at the from begining, two situation may arise:
def delete_from_start(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.head.data
self.head = self.head.next
self.head.prev = None
return data
else:
raise Exception('Empty linked list') deleteFromStart() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.head.data;
this.head = this.head.next;
this.head.prev = null;
}
return data;
} else {
throw "Empty Linked List";
}
} Deletion from the end of the Doubly Linked ListWhile deleting a node at the from the end, two situation may arise:
def delete_from_end(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return data
else:
raise Exception('Empty linked list') deleteFromEnd() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.tail.data;
this.tail = this.tail.prev;
this.tail.next = null;
}
return data;
} else {
throw "Empty Linked List";
}
} Deletion from given position in the Doubly Linked ListWhile deleting at any given position following 3 situation may arise based on user input:
def delete_at_position(self, pos):
if pos < 0 or pos >= self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
temp = self.head
for _ in range(pos):
temp = temp.next
data = temp.data
prev_node = temp.prev
prev_node.next = temp.next
temp.next.prev = prev_node
return data deleteAtPosition(pos) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
const data = temp.data;
const prevNode = temp.prev;
prevNode.next = temp.next;
temp.next.prev = prevNode;
return data;
}
}
} Implementation of Doubly Linked ListImplementation of singly linked list linked list with all the function combined with output.
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_start(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def insert_at_position(self, pos, data):
new_node = Node(data)
if pos < 0 or pos > self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node.next = temp.next
temp.next = new_node
new_node.prev = temp
def delete_from_start(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.head.data
self.head = self.head.next
self.head.prev = None
return data
else:
raise Exception('Empty linked list')
def delete_from_end(self):
if self.head:
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
else:
data = self.tail.data
self.tail = self.tail.prev
self.tail.next = None
return data
else:
raise Exception('Empty linked list')
def delete_at_position(self, pos):
if pos < 0 or pos >= self.length():
raise Exception('Enter a valid postion')
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
temp = self.head
for _ in range(pos):
temp = temp.next
data = temp.data
prev_node = temp.prev
prev_node.next = temp.next
temp.next.prev = prev_node
return data
def get_first(self):
if self.head:
return self.head.data
else:
raise Exception('Linked List is empty')
def get_last(self):
if self.tail:
return self.tail.data
else:
raise Exception('Linked List is empty')
def traverse(self):
if self.head:
temp = self.head
while temp:
print(temp.data)
temp = temp.next
else:
print(None)
def reverse_traverse(self):
if self.tail:
temp = self.tail
while temp:
print(temp.data)
temp = temp.prev
else:
print(None)
def length(self):
temp = self.head
count = 0
while temp:
count += 1
temp = temp.next
return count
dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
dll.insert_at_end(5)
dll.insert_at_end(6)
dll.traverse() class Node {
constructor(data) {
this.prev = null;
this.data = data;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
insertAtStart(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
}
insertAtEnd(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
}
insertAtPosition(pos, data) {
const newNode = new Node(data);
if (pos < 0 || pos > this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
this.insertAtStart(data);
} else if (pos == this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos - 1; i++) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
}
}
deleteFromStart() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.head.data;
this.head = this.head.next;
this.head.prev = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
deleteFromEnd() {
if (this.head) {
let data;
if (this.head === this.tail) {
data = this.head.data;
this.head = this.tail = null;
} else {
data = this.tail.data;
this.tail = this.tail.prev;
this.tail.next = null;
}
return data;
} else {
throw "Empty Linked List";
}
}
deleteAtPosition(pos) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos == 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
const data = temp.data;
const prevNode = temp.prev;
prevNode.next = temp.next;
temp.next.prev = prevNode;
return data;
}
}
}
getFirst() {
if (this.head) return this.head.data;
throw "Linked List is empty";
}
getLast() {
if (this.tail) return this.tail.data;
throw "Linked List is empty";
}
traverse() {
if (this.head) {
let temp = this.head;
while (temp) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
reverseTraverse() {
if (this.tail) {
let temp = this.tail;
while (temp) {
console.log(temp.data);
temp = temp.prev;
}
} else {
console.log(null);
}
}
length() {
let temp = this.head;
let count = 0;
while (temp) {
count++;
temp = temp.next;
}
return count;
}
}
const dll = new DoublyLinkedList();
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.insertAtEnd(4);
dll.insertAtEnd(5);
dll.insertAtEnd(6);
dll.traverse(); OutputOutput 1 2 3 4 5 6Advantages of Doubly Linked List over Singly Linked List
Disadvantages of Doubly Linked List over Singly Linked List
« Linked List Program to find middle element of a Linked List » AUTHOR Abhishek KumarSoftware engineer | Blogger | Keen learner Recommended Posts -
|
