Implement Linked List Operations - Implement Linked List Operations

Curriculum Help
1

Tell us what’s happening:

Hello :waving_hand: :grinning_face_with_smiling_eyes:

My implementation is failing the tests for insertAt() despite seemingly working perfectly.

My first implementation failed tests 13, 14, 15, and 16, despite seemingly fulfilling the requirements (can insert at arbitrary valid index, including start, end, middle. and in empty list).

I eventually reset the whole thing, and tried this implementation, using the previous functions like add() to implement parts of insertAt(). This also seemingly fulfills all the requirements, but it still fails 13 and 14.

Are the tests bugged or am I missing something?

Thanks!

Your code so far

function initList() {
  return {
    head: null,
    length: 0
  };
}

function isEmpty(list) {
  return list.length === 0;
}

function add(list, element) {
  const node = { element, next: null };

  if (isEmpty(list)) {
    list.head = node;
  } else {
    let current = list.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = node;
  }

  list.length++;
}

function remove(list, element) {
  let previous = null;
  let current = list.head;

  while (current !== null && current.element !== element) {
    previous = current;
    current = current.next;
  }

  if (current === null) return;

  if (previous !== null) {
    previous.next = current.next;
  } else {
    list.head = current.next;
  }

  list.length--;
}

function contains(list, element) {
  if (isEmpty(list)) {
    return false;
  }

  let current = list.head;
  while (current !== null) {
    if (current.element === element) {
      return true;
    } else {
      current = current.next;
    }
  }
  
  return false;
}

function getAt(list, index) {
  if (isEmpty(list) || index < 0 || index >= list.length) {
    return undefined;
  }

  let current = list.head;

  for (let i = 0; i < index; i++) {
    current = current.next;
  }

  return current.element;
}

// Same as getAt(), but returns the node instead of the element within it
function getNodeAt(list, index) {
  if (isEmpty(list) || index < 0 || index >= list.length) {
    return undefined;
  }

  let current = list.head;

  for (let i = 0; i < index; i++) {
    current = current.next;
  }

  return current;
}

function insertAt(list, index, element) {
  if (index < 0 || index > list.length) {
    return;
  }

  if (isEmpty(list) || index === list.length) {
    add(list, element);
    return;
  } 

  const node = { element, next: null };

  if (index === 0) {
    node.next = list.head;
    list.head = node;
    return;
  }

  const beforeIndex = getNodeAt(list, index - 1);
  const atIndex = getNodeAt(list, index);

  node.next = atIndex;
  beforeIndex.next = node;
  return;

}

function removeAt(list, index) {
  remove(list, getAt(list, index));
}

function clear(list) {
  list.head = null;
  list.length = 0;
}

const myList = initList();
add(myList, 0);
add(myList, 1);
add(myList, 2);
add(myList, 3);
add(myList, 4);
insertAt(myList, 2, "input");
console.log(JSON.stringify(myList, null, 2));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:151.0) Gecko/20100101 Firefox/151.0

Challenge Information:

Implement Linked List Operations - Implement Linked List Operations

GitHub Link: freeCodeCamp/curriculum/challenges/english/blocks/lab-linked-list-operations/69708d59833ceded7d00541f.md at main · freeCodeCamp/freeCodeCamp · GitHub

2

I figured it out. My implementation of insertAt() wasn’t incrementing list.length after insertion. :man_facepalming: