DoublyLinkedList is a data structure that contains a head, tail and length property. Linked Lists consist of nodes, and each node has a value and a pointer to another node or null.
The DoublyLinkedList is an extension of LinkedList. It has two pointers, one to the first element of the list and another to the last element of the list.
Following are some methods used in DoublyLinkedList:
InsertAtHead(): Inserts an element at the beginning of a DoublyLinkedList.
insertAtHead(data: number) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
}
```
`InsertAtTail()`: Inserts an element at the end of a `DoublyLinkedList`.
```js
insertAtTail(data: number) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
InsertAtIndex(): Inserts an element at index n in a DoublyLinkedList.
insertAtIndex(data: number, index: number) {
if (index === 0) {
this.insertAtHead(data);
return;
}
if (index >= this.length) {
this.insertAtTail(data);
return;
}
const newNode = new Node(data);
let currentNode = this.head;
let currentIndex = 0;
while (currentIndex !== index) {
currentNode = currentNode.next;
currentIndex++;
}
newNode.next = currentNode;
newNode.prev = currentNode.prev;
currentNode.prev.next = newNode;
currentNode.prev = newNode;
this.length++;
}
DeleteAtHead(): Removes and returns the head node of this DoublyLinkedList.
deleteAtHead() {
if (this.head === null) {
return null;
}
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return;
}
this.head = this.head.next;
this.head.prev = null;
this.length--;
}
DeleteAtTail(): Removes and returns the tail node of this DoublyLinkedList.
deleteAtTail() {
if (this.head === null) {
return null;
}
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return;
}
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
}
Search(): Searches for a specified value within this DoublyLinkedList and returns its index if found; otherwise, returns -1
search(data: number) {
let currentNode = this.head;
while (currentNode !== null) {
if (currentNode.data === data) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
printList: This function prints the
printList(){
let currentNode = this.head;
let list = [];
while (currentNode !== null) {
list.push(currentNode.data);
currentNode = currentNode.next;
}
return list;
}
Time Complexity
- insertAtHead: O(1)
- insertAtTail: O(1)
- insertAtIndex: O(n)
- deleteAtHead: O(1)
- deleteAtTail: O(1)
- deleteAtIndex: O(n)
- search: O(n)
- printList: O(n)
Complete Source Code Of DoublyLinkedList
Below is the complete source code
class Node {
data: number;
next: Node;
prev: Node;
constructor(data: number) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
head: Node;
tail: Node;
length: number;
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
insertAtHead(data: number) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
}
insertAtTail(data: number) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
insertAtIndex(data: number, index: number) {
if (index === 0) {
this.insertAtHead(data);
return;
}
if (index >= this.length) {
this.insertAtTail(data);
return;
}
const newNode = new Node(data);
let currentNode = this.head;
let currentIndex = 0;
while (currentIndex !== index) {
currentNode = currentNode.next;
currentIndex++;
}
newNode.next = currentNode;
newNode.prev = currentNode.prev;
currentNode.prev.next = newNode;
currentNode.prev = newNode;
this.length++;
}
deleteAtTail() {
if (this.head === null) {
return null;
}
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return;
}
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
}
search(data: number) {
let currentNode = this.head;
while (currentNode !== null) {
if (currentNode.data === data) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
printList(){
let currentNode = this.head;
let list = [];
while (currentNode !== null) {
list.push(currentNode.data);
currentNode = currentNode.next;
}
return list;
}
}
const myDoublyLinkedList = new DoublyLinkedList();
myDoublyLinkedList.insertAtHead(10);
myDoublyLinkedList.insertAtHead(20);
myDoublyLinkedList.insertAtHead(30);
myDoublyLinkedList.insertAtTail(40);
myDoublyLinkedList.insertAtTail(50);
myDoublyLinkedList.insertAtTail(60);
myDoublyLinkedList.insertAtIndex(70, 3);
myDoublyLinkedList.deleteAtTail();
console.log(myDoublyLinkedList.printList()); // Output: [30, 20, 10, 70, 40, 50]