A doubly linked list is a data structure that allows for bi-directional traversal. It has prev and next pointers for each node, which enables more flexibility in operations like insertion, deletion, and searching.
A doubly linked list is a data structure that consists of a sequence of nodes, each of which contains two links, one to the previous node and one to the next node. This makes it possible to traverse the list in both directions.
Here’s an example of a doubly linked list:
null <=> 1 <=> 2 <=> 3 <=> null
In this example, the list has three nodes, with values of 1, 2, and 3. The first and last nodes have null links to indicate the start and end of the list.
To traverse a doubly linked list, you can start at either end and follow the links to the next or previous node. For example, starting at the beginning of the list, you would first follow the link from the null node to the node containing the value 1. From there, you could follow the link to the node containing the value 2, and then the link to the node containing the value 3.
Doubly linked lists have a few advantages over singly linked lists. Because they allow traversal in both directions, they can be more convenient to use in certain situations. For example, if you need to iterate over a list backwards, a doubly linked list can be much more efficient than reversing a singly linked list.
However, doubly linked lists are also more complex than singly linked lists, as they require additional links and bookkeeping to maintain the links correctly. Additionally, they require more memory than singly linked lists, as each node must store two pointers instead of one.
Following are the operations that can be used to manipulate and process data in a doubly linked list in a variety of ways. If you are preparing for an interview, these operations implementation should be on your tips.
Creation:
function createList():
head = None
return head
This function creates an empty doubly linked list with a null head.
Insertion at the beginning:
function insertAtBeginning(head, data):
newNode = Node(data)
newNode.next = head
newNode.prev = None
if head is not None:
head.prev = newNode
head = newNode
return head
This function inserts a new node with the given data value at the beginning of the doubly linked list. It creates a new node, sets its next pointer to the current head of the list, updates the previous pointer of the current head to point to the new node, and updates the head to point to the new node.
Deletion at the beginning:
function deleteAtBeginning(head):
if head is None:
return head
else:
if head.next is not None:
head.next.prev = None
head = head.next
return head
This function deletes the first node in the doubly linked list. It checks if the list is empty, and if not, updates the previous pointer of the new head to point to null and updates the head to point to the next node in the list.
Traversal:
function traverse(head):
if head is None:
return
else:
current = head
while current is not None:
print(current.data)
current = current.next
This function traverses the doubly linked list and prints the data value in each node. It starts at the head of the list, iterates through each node using the next pointers, and prints the data value of each node.
Searching for a node:
function search(head, key):
if head is None:
return None
else:
current = head
while current is not None:
if current.data == key:
return current
current = current.next
return None
This function searches for a node with the given data value in the doubly linked list. It starts at the head of the list, iterates through each node using the next pointers, and checks if the data value matches the key. If a match is found, it returns the node; otherwise, it returns None.
Insertion at a specific position:
function insertAtPosition(head, data, position):
newNode = Node(data)
if position == 1:
newNode.next = head
newNode.prev = None
if head is not None:
head.prev = newNode
head = newNode
else:
current = head
prev = None
for i in range(1, position):
prev = current
current = current.next
prev.next = newNode
newNode.prev = prev
newNode.next = current
if current is not None:
current.prev = newNode
return head
This function inserts a new node with the given data value at a specific position in the doubly linked list. It creates a new node, and then iterates through the list to find the node at the specified position. It updates the next pointers of the nodes before and after the new node to include the new node, and updates the previous pointers of the nodes before and after the new node to point to the new node.
Deletion at a specific position:
function deleteAtPosition(head, position):
if head is None:
return head
elif position == 1:
if head.next is not None:
head.next.prev = None
head = head.next
else:
current = head
prev = None
for i in range(1, position):
prev = current
current = current.next
prev.next = current.next
if current.next is not None:
current.next.prev = prev
return head
This function deletes the node at a specific position in the doubly linked list. It checks if the list is empty or if the position is the first node. If neither condition is true, it iterates through the list to find the node at the specified position and updates the next and previous pointers of the nodes before and after it to remove the node.
Reversing a linked list:
function reverseList(head):
if head is None or head.next is None:
return head
else:
current = head
while current is not None:
temp = current.next
current.next = current.prev
current.prev = temp
current = temp
head = head.prev
return head
This function reverses the order of nodes in the doubly linked list. It iterates through the list, reversing the next and previous pointers of each node as it goes. It also updates the head of the list to point to the last node, which becomes the new head.
Splitting a linked list:
function splitList(head, position):
if head is None:
return None, None
elif position == 1:
return head, None
else:
current = head
prev = None
for i in range(1, position):
prev = current
current = current.next
prev.next = None
current.prev = None
return head, current
This function splits the doubly linked list into two separate lists at a specific node position. It iterates through the list to find the node at the specified position, updates the next and previous pointers of the nodes before and after it to null to split the list, and returns the two separate lists as separate heads.
Joining two linked lists:
function joinLists(head1, head2):
if head1 is None:
return head2
elif head2 is None:
return head1
else:
current = head1
while current.next is not None:
current = current.next
current.next = head2
head2.prev = current
return head1
This function joins two doubly linked lists into a single doubly linked list. It finds the last node of the first list using iteration and updates its next pointer to point to the head of the second list. It also updates the previous pointer of the head of the second list to point to the last node of the first list, effectively joining the two lists.
Finding the middle node:
function findMiddleNode(head):
if head is None:
return None
else:
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
This function finds the middle node of the doubly linked list. It uses the Floyd’s algorithm to traverse the doubly linked list with two pointers, one that moves one node at a time (slow) and another that moves two nodes at a time (fast). When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
Removing duplicates:
function removeDuplicates(head):
if head is None:
return None
else:
current = head
while current is not None:
temp = current.next
while temp is not None and temp.data == current.data:
temp = temp.next
current.next = temp
if temp is not None:
temp.prev = current
current = temp
return head
This function removes duplicates from the doubly linked list. It iterates through the list, and for each node, it checks if any subsequent nodes have the same data value. If a duplicate is found, it updates the next pointer of the current node to skip over the duplicate. It also updates the previous pointer of the next node to point back to the current node.
Counting nodes in the list:
function countNodes(head):
count = 0
current = head
while current is not None:
count += 1
current = current.next
return count
This function counts the number of nodes in the doubly linked list. It starts at the head of the list, iterates through each node using the next pointers, and increments a counter variable for each node. The function returns the final count when all nodes have been counted.
Finding the Nth node from the beginning:
function findNthNodeFromBeginning(head, n):
if head is None:
return None
elif n == 1:
return head
else:
current = head
for i in range(1, n):
current = current.next
return current
This function finds the Nth node from the beginning of the doubly linked list. It starts at the head of the list and iterates through the list to find the node at the specified position. It returns the node when it is found.
Finding the Nth node from the end:
function findNthNodeFromEnd(head, n):
if head is None:
return None
else:
current = head
for i in range(1, n):
if current.next is None:
return None
else:
current = current.next
nthNode = head
while current.next is not None:
current = current.next
nthNode = nthNode.next
return nthNode
This function finds the Nth node from the end of the doubly linked list. It starts at the head of the list and iterates through the list to find the node at the specified position from the end. It returns the node when it is found.
Removing a node with a specific data value:
function removeNodeWithData(head, key):
if head is None:
return None
elif head.data == key:
if head.next is not None:
head.next.prev = None
head = head.next
else:
current = head
while current is not None and current.data != key:
current = current.next
if current is None:
return head
else:
current.prev.next = current.next
if current.next is not None:
current.next.prev = current.prev
return head
This function removes the first node with the given data value from the doubly linked list. It iterates through the list to find the node with the specified data value, updates the next and previous pointers of the nodes before and after it to remove the node, and returns the updated head of the list.
Sorting the list:
function sortList(head):
if head is None or head.next is None:
return head
else:
middle = findMiddleNode(head)
middle.next.prev = None
leftHalf = sortList(head)
rightHalf = sortList(middle.next)
head = mergeLists(leftHalf, rightHalf)
return head
This function sorts the doubly linked list using a merge sort algorithm. It finds the middle node of the list using the findMiddleNode function, recursively sorts the left and right halves of the list using the sortList function, and merges the two sorted halves using the mergeLists function.
Merging two sorted lists:
function mergeLists(head1, head2):
if head1 is None:
return head2
elif head2 is None:
return head1
else:
if head1.data <= head2.data:
mergedHead = head1
mergedHead.next = mergeLists(head1.next, head2)
mergedHead.next.prev = mergedHead
else:
mergedHead = head2
mergedHead.next = mergeLists(head1, head2.next)
mergedHead.next.prev = mergedHead
return mergedHead
This function merges two sorted doubly linked lists into a single sorted list. It compares the data values of the nodes at the heads of the two lists, selects the smaller value as the new head of the merged list, and recursively merges the remaining nodes using the next and previous pointers.
Finding the intersection of two lists:
function findIntersection(head1, head2):
if head1 is None or head2 is None:
return None
else:
current1 = head1
while current1 is not None:
current2 = head2
while current2 is not None:
if current1.data == current2.data:
return current1
current2 = current2.next
current1 = current1.next
return None
This function finds the first node where two doubly linked lists intersect. It iterates through the nodes of the first list, and for each node, it iterates through the nodes of the second list to find a node with the same data value. When a match is found, it returns the node.
Reversing a sublist within the list:
function reverseSublist(head, start, end):
if head is None:
return None
else:
current = head
for i in range(1, start):
current = current.next
startNode = current
for i in range(start, end):
current = current.next
endNode = current
while endNode is not startNode:
temp = startNode.data
startNode.data = endNode.data
endNode.data = temp
startNode = startNode.next
endNode = endNode.prev
return head
This function reverses a sublist within the doubly linked list. It iterates through the list to find the nodes at the start and end positions, and then iterates through the sublist to swap the data values of the nodes at opposite ends of the sublist. It then returns the head of the list.