Posted on by Kalkicode
Code Doubly linked list

Find the largest node in Doubly linked list

The problem at hand is to find the largest node value in a doubly linked list. A doubly linked list is a data structure composed of nodes, each containing a value, a reference to the next node, and a reference to the previous node. The goal is to identify the maximum value among all the node values present in the linked list.

Find the largest node

Problem Statement

Given a doubly linked list, we are tasked with finding the largest value among the values stored in its nodes.

Example

Let's consider an example to illustrate the problem. Suppose we have a doubly linked list with the following values: 14, 31, 12, 15, 11, 25. The largest value in this list is 31.

Idea to Solve

To find the largest node value in a doubly linked list, we need to traverse the entire list while keeping track of the maximum value encountered. We start by initializing a variable to store the maximum value with the value of the first node. We then iterate through the list, comparing each node's value with the maximum value. If the current node's value is greater than the current maximum value, we update the maximum value. After traversing the entire list, the maximum value will represent the largest value among all nodes.

Pseudocode

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

function maximum():
    if head is null:
        return 0
    result = head.data
    current = head
    while current is not null:
        if current.data > result:
            result = current.data
        current = current.next
    return result

Algorithm Explanation

  • If the head of the linked list is null (meaning the list is empty), we return 0 as there are no elements to find the maximum from.
  • We initialize a result variable with the value of the head node. This variable will store the maximum value encountered during traversal.
  • We initialize a current pointer with the head of the linked list.
  • We enter a loop that iterates as long as the current pointer is not null.
  • Inside the loop, we compare the value of the current node with the result variable. If the current node's value is greater than result, we update the result variable with the current node's value.
  • We then move the current pointer to the next node.
  • After traversing the entire list, the result variable will contain the maximum value.

Code Solution

Resultant Output Explanation

In the provided Java code, the doubly linked list is created, and nodes with values 14, 31, 12, 15, 11, and 25 are inserted. The maximum() function is then called to determine the largest value in the linked list, which is 31. The output statement then prints the maximum value, resulting in the output "Maximum: 31".

Time Complexity

  • The algorithm traverses through the entire linked list once.
  • The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.

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