A doubly linked list is a type of linked list in which each node has a reference to both the previous and next nodes in the list, unlike singly linked lists that only have a reference to the next node. This additional reference allows for efficient traversal of the list in both forward and backward directions, which is useful for certain algorithms such as sorting and reversing a list. The first node in the list is called the head, and the last node is called the tail. The head node’s previous reference is null, and the tail node’s next reference is null. Insertion and deletion operations are straightforward in a doubly linked list since we can simply update the references of the neighboring nodes to insert or delete a node. However, doubly linked lists require more memory compared to singly linked lists because of the additional reference in each node.
class Node(var data: Int) {
var prev: Node? = null
var next: Node? = null
}The Node class represents a node in the doubly linked list, which contains a data field and references to the previous and next nodes using the prev and next fields, respectively.
class DoublyLinkedList {
private var head: Node? = null
private var tail: Node? = null
fun insertAtEnd(data: Int) {
val newNode = Node(data)
if (head == null) {
head = newNode
tail = newNode
} else {
newNode.prev = tail
tail?.next = newNode
tail = newNode
}
}
The DoublyLinkedList class represents the doubly linked list itself, which contains a reference to the head and tail nodes. The insertAtEnd method inserts a new node with the given data at the end of the list, by creating a new node, updating the prev and next references of the appropriate nodes, and updating the head and tail references as necessary.
fun delete(data: Int) {
var current = head
while (current != null) {
if (current.data == data) {
if (current == head && current == tail) {
head = null
tail = null
} else if (current == head) {
head = head?.next
head?.prev = null
} else if (current == tail) {
tail = tail?.prev
tail?.next = null
} else {
current.prev?.next = current.next
current.next?.prev = current.prev
}
break
}
current = current.next
}
}The delete method deletes the node with the given data from the list, by traversing the list to find the node with the given data, updating the prev and next references of the appropriate nodes, and updating the head and tail references as necessary.
fun display() {
var current = head
while (current != null) {
print("${current.data} ")
current = current.next
}
println()
}The display method traverses the list and prints the data of each node.
class Node(var data: Int) {
var prev: Node? = null
var next: Node? = null
}
class DoublyLinkedList {
private var head: Node? = null
private var tail: Node? = null
fun insertAtEnd(data: Int) {
val newNode = Node(data)
if (head == null) {
head = newNode
tail = newNode
} else {
newNode.prev = tail
tail?.next = newNode
tail = newNode
}
}
fun delete(data: Int) {
var current = head
while (current != null) {
if (current.data == data) {
if (current == head && current == tail) {
head = null
tail = null
} else if (current == head) {
head = head?.next
head?.prev = null
} else if (current == tail) {
tail = tail?.prev
tail?.next = null
} else {
current.prev?.next = current.next
current.next?.prev = current.prev
}
break
}
current = current.next
}
}
fun display() {
var current = head
while (current != null) {
print("${current.data} ")
current = current.next
}
println()
}
}
fun main() {
val dll = DoublyLinkedList()
dll.insertAtEnd(1)
dll.insertAtEnd(2)
dll.insertAtEnd(3)
dll.insertAtEnd(4)
dll.insertAtEnd(5)
dll.display()
dll.delete(3)
dll.display()
}In the main function, we create a new DoublyLinkedList, insert five nodes using the insertAtEnd method, and display the list using the display method. Finally, we delete the node with data 3 using the delete method and display the updated list. The output should be 1 2 3 4 5 followed by 1 2 4 5.