Given an unsorted linked list, find the element with the largest value. (JavaScript)

Question

I'm new to coding and learning Linked List problems. I found a solution but don't really understand what they do. what does (!node.next) mean? Is it the same as node.next != null?

Also, I don't understand this line return (node.value > biggestValueInRest ? node.value : biggestValueInRest);

Does it mean that if node.value is greater than biggestValueInRest, then node.value = biggestValueInRest?

Here is the solution

function findMax(node) {
  if (!node.next) {
    return node.value;
  } else {
    const biggestValueInRest = findMax(node.next);

    return (node.value > biggestValueInRest ? node.value
      : biggestValueInRest);
  }
}

`!node.next` checks for any falsy value, it returns `true` if it's `null`, `false` or any other [falsy value](https://developer.mozilla.org/en-US/docs/Glossary/Falsy) — Cid, Jan 06 '22 at 06:06
*"Does it mean that if node.value is greater than biggestValueInRest, then node.value = biggestValueInRest?"* kind of, it returns the value (so it indeed sets `biggestValueInRest` thanks to the recursive return) rather than setting `node.value`, it's a [ternary expression](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Conditional_Operator) — Cid, Jan 06 '22 at 06:06

MrFrenzoid · Answer 1 · 2022-01-06T06:31:42.423

what does (!node.next) mean? Is it the same as node.next != null?

The ! is the negation operator, it negates the value placed in front of it.

for example !node.next is the same as node.next == false.

In this case, !node.next will return true if node.next is a falsy value like false or null or undefined.

In the if statement of your code, it will return the current node's value if there's no next node linked to that node since, in linked lists, nodes contain a value and a link to the next node.

Also, I don't understand this line return (node.value > biggestValueInRest ? node.value : biggestValueInRest);

Does it mean that if node.value is greater than biggestValueInRest, then node.value = biggestValueInRest?

That's a ternary operator, it's like a shortened if that returns a value.

return (node.value > biggestValueInRest ? node.value : biggestValueInRest);

would be the same as:

if (node.value > biggestValueInRest)
  return node.value;
else
  return biggestValueInRest;

The syntax of the ternary operator is basically:

"condition" ? "value to return if true" : "value to return if false"

And to fully answer your question.

I found a solution but don't really understand what they do.

The solution provided is a recursive one, it will call itself for each node in the linked lists until it reaches the final one ( the one which's node.next is empty ), and once that's done, it will return the biggest value of each comparison from there.

Recursive functions aren't always a good practice, since their time complexity can escalate depending on how the developer implemented it.

In this case, it would be O(n) which means that it's linear, which is not too bad for a recursive function.

This means that the time the function will take to finish is affected in proportion to the number of items n the linked list has.

So if it takes 1s per node, then 100 nodes would be 100s for the function to finish.

score 0 · Answer 2 · answered Jan 06 '22 at 06:21

It would have been simpler in python but what you can do is create a function that is looks something like this, will explain later

assuming the list consist only of numeric values

Function(ListItems) {
 Let biggest_val = 0;

 For (let i = 0; i < ListItems.length; i++) {
   If (LisItems[i] > biggest_val) {
  biggest_val = ListItems[i]
}
 }
}

We are first initialising a variable to hold the biggest value of the list for us, and then creating a for loop to loop through the list and check if the current value is greater than our current biggest value if so update the value of our biggest val.

the node.value > biggestValueInRest ? node.value : biggestValueInRest is called a [turnary operator][1] it is a short hand if statement but since you're just beginning it is better to stick with the traditional one

[1] : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Conditional_Operator

Given an unsorted linked list, find the element with the largest value. (JavaScript)

2 Answers2