1
\$\begingroup\$

I wrote this algorithm to find the Kth element of a singly linked list and I would like your feedback because I want to know if there is a better version.

In my eyes, this is the most optimized way of doing it and I've covered every edge case (I also assumed that the only possible input is a number, if I removed that assumption, I would add another if block), but I really would appreciate your feedback.

PS: I also only added these two main methods (add and findLast) because I figured that there were the only two required to find a solution, but I'm not sure if I should add more in an interview (i.e. remove, removeAt, addAt, isEmpty, etc.)

function LinkedList() {
  let length = 0;
  let head = null;

  function Node(element) {
    this.element = element;
    this.next = null;
  }

  this.length = function() {
    return length;
  }

  this.head = function() {
    return head;
  }

  this.add = function(element) {
    let node = new Node(element);

    if (head == null) {
      head = node;
    } else {
      currentNode = head;

      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    length++;
  }

  this.findLast = function(index) {
    if(index > length) {
      return false;
    }
    if (index < 0) {
      return false;
    }

    let realIndexes = length-1; // if length = 5, realIndexes = 4
    let realPosition = index-1; // if index = 2, realPosition = 1 
    // We are looking for the real position here.
    let realTarget = realIndexes - realPosition;
    let currentNode = head;
    let counter = 0;

    while (counter < realTarget) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode.element;
  }
}

let congo = new LinkedList();
console.log(congo)
congo.add(5);
congo.add("Homeless");
congo.add("Real eyes realize real lies");
congo.length()
congo.head()

Output: => 5

\$\endgroup\$

migrated from stackoverflow.com Oct 15 '18 at 3:59

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ Okay thank you Mark, wasn't sure if Stack Overflow was right for this \$\endgroup\$ – Abdel Shokair Oct 3 '18 at 20:12
  • 2
    \$\begingroup\$ Are you sure the task is / was not to find the k-th element from the end? \$\endgroup\$ – Stefan Haustein Oct 3 '18 at 20:14
  • 3
    \$\begingroup\$ No, it's not really optimal: don't put the Node constructor inside the LinkedList one, use prototype methods instead of per-instance ones, and for optimisation purposes also store a reference to the last node in the list instance. \$\endgroup\$ – Bergi Oct 3 '18 at 20:23
  • 1
    \$\begingroup\$ realIndexes and realPosition don't make any sense. What was wrong with the normal ones? Notice that realTarget==realIndexes - realPosition==length - index. \$\endgroup\$ – Bergi Oct 3 '18 at 20:27
  • 1
    \$\begingroup\$ "I'm not sure if I should add more in an interview" - that's rather off-topic here. But no, in an interview you should implement only what is necessary for the task to solve. No (good) interviewer would ask you to implement a "complete" LinkedList class. \$\endgroup\$ – Bergi Oct 3 '18 at 20:28
1
\$\begingroup\$

To get the sub-list of the last n elements without computing the length first (see comments):

  • Go ahead with an end pointer until you have skipped n elements.
  • Now go ahead in parallel with a start pointer and the end pointer until the end pointer reaches the end of the list (the start and end pointers will stay n elements apart as you go).
  • Now start points to the desired sub-list.

In an interview, before you implement anything, it's often a good idea to first describe your plan. Counting first works and is no different in terms of the O notation, but I doubt it's what the interviewer wanted to see. Describing your plan can avoid spending time on something the interviewer might not really be interested in.

\$\endgroup\$
0
\$\begingroup\$

Unsafe code

We can only guess what the interviewer is looking for. Usually they just want to know if you can write code in whatever language is required.

So the following is just to point out a danger in the code. Should you change your code? I can't say..

Protect state

Your function is flawed and can easily have its state corrupted. This is because you expose Node.next and don't consider the various problems this will cause. eg

const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
const head = list.head();

Delete second item from the list

head.next = head.next.next;

Now the length you store is incorrect and the result of findLast will either return index - 1, index + 1, or worse throw if you reach the end as you will have assigned null to currentNode in the previous step and currentNode.next will throw Can not read property "next" of null

Or a cyclic link

head.next = head; // now you have a infinit linked list

There function LinkedList.add(data) will not exit.

Don't expose node.next

The solution is simple. Don't expose the link. You can return items in the list wrapped in an object that provides a function next() to move to the next object. Or define the node with a getter for next.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.