Table of Contents

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.

Written by

With 10+ years in software engineering, I specialize in blogging and web development. My skills span front-end, back-end, database design, web security, and SEO. Passionate about crafting helpful digital experiences.