Skip to main content

Find the smallest node in doubly linked list

The problem discussed here involves finding the smallest node in a doubly linked list. A doubly linked list is a data structure where each node contains a value and two pointers, one pointing to the next node (in the forward direction) and another pointing to the previous node (in the backward direction). The task is to iterate through the linked list and identify the node with the smallest value.

Problem Statement

Given a doubly linked list, the objective is to find and output the smallest value present in any of the nodes.

Idea to Solve

The idea to solve this problem is to iterate through the linked list, compare the values of each node, and keep track of the minimum value encountered so far.

Pseudocode

Here's the pseudocode that outlines the algorithm to find the smallest node in a doubly linked list:

class LinkNode:
    int data
    LinkNode next
    LinkNode prev

class DoublyLinkedList:
    LinkNode head
    LinkNode tail

    function insert(value):
        Create a new node with the given value
        If head is null:
            Set head and tail to the new node
        Else:
            Set tail's next to the new node
            Set new node's prev to tail
            Update tail to the new node

    function minNumber():
        If head is null:
            Print "Empty Linked List"
        Else:
            Initialize a temp node with head
            Initialize result with temp's data
            While temp is not null:
                If temp's data is less than result:
                    Update result with temp's data
                Move temp to temp's next
            Print "Smallest:", result

Create a DoublyLinkedList object
Insert nodes into the object
Call minNumber function to find and print the smallest value

Algorithm Explanation

  • The insert function adds a new node to the end of the linked list. If the list is empty, it updates both the head and tail pointers. Otherwise, it sets the new node's previous pointer to the current tail, updates the current tail's next pointer to the new node, and then updates the tail pointer to the new node.
  • The minNumber function checks if the list is empty. If it is, it prints "Empty Linked List." Otherwise, it initializes a temp node with the head and a result variable with the data of the first node. It then iterates through the linked list, comparing each node's data with the current minimum value (result). If a smaller value is found, result is updated. Finally, the smallest value (result) is printed.

Program List

Time Complexity

  • Inserting a node at the end of the linked list takes O(1) time.
  • Finding the smallest node in the linked list takes O(N) time since all nodes need to be traversed to determine the minimum.




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment