Linked list

Directions

Implement classes Node and Linked Lists See 'directions' document

Try it first#

Copy the stub, make the 29 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.

JSexercises/linkedlist/index.js

class Node {} class LinkedList {} module.exports = { Node, LinkedList };class Node {}

class LinkedList {}

module.exports = { Node, LinkedList };

Solution#

JScompleted_exercises/linkedlist/index.js

class Node {  constructor(data, next = null) {    this.data = data;    this.next = next;  }} class LinkedList {  constructor() {    this.head = null;  }   insertFirst(data) {    this.head = new Node(data, this.head);  }   size() {    let counter = 0;    let node = this.head;     while (node) {      counter++;      node = node.next;    }     return counter;  }   getFirst() {    return this.head;  }   getLast() {    if (!this.head) {      return null;    }     let node = this.head;    while (node) {      if (!node.next) {        return node;      }      node = node.next;    }  }   clear() {    this.head = null;  }   removeFirst() {    if (!this.head) {      return;    }     this.head = this.head.next;  }   removeLast() {    if (!this.head) {      return;    }     if (!this.head.next) {      this.head = null;      return;    }     let previous = this.head;    let node = this.head.next;    while (node.next) {      previous = node;      node = node.next;    }    previous.next = null;  }   insertLast(data) {    const last = this.getLast();     if (last) {      // There are some existing nodes in our chain      last.next = new Node(data);    } else {      // The chain is empty!      this.head = new Node(data);    }  }   getAt(index) {    let counter = 0;    let node = this.head;    while (node) {      if (counter === index) {        return node;      }       counter++;      node = node.next;    }    return null;  }   removeAt(index) {    if (!this.head) {      return;    }     if (index === 0) {      this.head = this.head.next;      return;    }     const previous = this.getAt(index - 1);    if (!previous || !previous.next) {      return;    }    previous.next = previous.next.next;  }   insertAt(data, index) {    if (!this.head) {      this.head = new Node(data);      return;    }     if (index === 0) {      this.head = new Node(data, this.head);      return;    }     const previous = this.getAt(index - 1) || this.getLast();    const node = new Node(data, previous.next);    previous.next = node;  }   forEach(fn) {    let node = this.head;    let counter = 0;    while (node) {      fn(node, counter);      node = node.next;      counter++;    }  }   *[Symbol.iterator]() {    let node = this.head;    while (node) {      yield node;      node = node.next;    }  }} module.exports = { Node, LinkedList };class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertFirst(data) {
    this.head = new Node(data, this.head);
  }

  size() {
    let counter = 0;
    let node = this.head;

    while (node) {
      counter++;
      node = node.next;
    }

    return counter;
  }

  getFirst() {
    return this.head;
  }

  getLast() {
    if (!this.head) {
      return null;
    }

    let node = this.head;
    while (node) {
      if (!node.next) {
        return node;
      }
      node = node.next;
    }
  }

  clear() {
    this.head = null;
  }

  removeFirst() {
    if (!this.head) {
      return;
    }

    this.head = this.head.next;
  }

  removeLast() {
    if (!this.head) {
      return;
    }

    if (!this.head.next) {
      this.head = null;
      return;
    }

    let previous = this.head;
    let node = this.head.next;
    while (node.next) {
      previous = node;
      node = node.next;
    }
    previous.next = null;
  }

  insertLast(data) {
    const last = this.getLast();

    if (last) {
      // There are some existing nodes in our chain
      last.next = new Node(data);
    } else {
      // The chain is empty!
      this.head = new Node(data);
    }
  }

  getAt(index) {
    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }

      counter++;
      node = node.next;
    }
    return null;
  }

  removeAt(index) {
    if (!this.head) {
      return;
    }

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

    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }

  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
      return;
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }

    const previous = this.getAt(index - 1) || this.getLast();
    const node = new Node(data, previous.next);
    previous.next = node;
  }

  forEach(fn) {
    let node = this.head;
    let counter = 0;
    while (node) {
      fn(node, counter);
      node = node.next;
      counter++;
    }
  }

  *[Symbol.iterator]() {
    let node = this.head;
    while (node) {
      yield node;
      node = node.next;
    }
  }
}

module.exports = { Node, LinkedList };
const L = require('./index');const List = L.LinkedList;const Node = L.Node; test('List is a class', () => {  expect(typeof List.prototype.constructor).toEqual('function');}); test('Node is a class', () => {  expect(typeof Node.prototype.constructor).toEqual('function');}); describe.skip('A Node', () => {  test('has properties "data" and "next"', () => {    const node = new Node('a', 'b');    expect(node.data).toEqual('a');    expect(node.next).toEqual('b');  });}); describe.skip('Insert First', () => {  test('appends a node to the start of the list', () => {    const l = new List();    l.insertFirst(1);    expect(l.head.data).toEqual(1);    l.insertFirst(2);    expect(l.head.data).toEqual(2);  });}); describe.skip('Size', () => {  test('returns the number of items in the linked list', () => {    const l = new List();    expect(l.size()).toEqual(0);    l.insertFirst(1);    l.insertFirst(1);    l.insertFirst(1);    l.insertFirst(1);    expect(l.size()).toEqual(4);  });}); describe.skip('GetFirst', () => {  test('returns the first element', () => {    const l = new List();    l.insertFirst(1);    expect(l.getFirst().data).toEqual(1);    l.insertFirst(2);    expect(l.getFirst().data).toEqual(2);  });}); describe.skip('GetLast', () => {  test('returns the last element', () => {    const l = new List();    l.insertFirst(2);    expect(l.getLast()).toEqual({ data: 2, next: null });    l.insertFirst(1);    expect(l.getLast()).toEqual({ data: 2, next: null });  });}); describe.skip('Clear', () => {  test('empties out the list', () => {    const l = new List();    expect(l.size()).toEqual(0);    l.insertFirst(1);    l.insertFirst(1);    l.insertFirst(1);    l.insertFirst(1);    expect(l.size()).toEqual(4);    l.clear();    expect(l.size()).toEqual(0);  });}); describe.skip('RemoveFirst', () => {  test('removes the first node when the list has a size of one', () => {    const l = new List();    l.insertFirst('a');    l.removeFirst();    expect(l.size()).toEqual(0);    expect(l.getFirst()).toEqual(null);  });   test('removes the first node when the list has a size of three', () => {    const l = new List();    l.insertFirst('c');    l.insertFirst('b');    l.insertFirst('a');    l.removeFirst();    expect(l.size()).toEqual(2);    expect(l.getFirst().data).toEqual('b');    l.removeFirst();    expect(l.size()).toEqual(1);    expect(l.getFirst().data).toEqual('c');  });}); describe.skip('RemoveLast', () => {  test('RemoveLast removes the last node when list is empty', () => {    const l = new List();    expect(() => {      l.removeLast();    }).not.toThrow();  });   test('RemoveLast removes the last node when list is length 1', () => {    const l = new List();    l.insertFirst('a');    l.removeLast();    expect(l.head).toEqual(null);  });   test('RemoveLast removes the last node when list is length 2', () => {    const l = new List();    l.insertFirst('b');    l.insertFirst('a');     l.removeLast();     expect(l.size()).toEqual(1);    expect(l.head.data).toEqual('a');  });   test('RemoveLast removes the last node when list is length 3', () => {    const l = new List();    l.insertFirst('c');    l.insertFirst('b');    l.insertFirst('a');    l.removeLast();     expect(l.size()).toEqual(2);    expect(l.getLast().data).toEqual('b');  });}); describe.skip('InsertLast', () => {  test('adds to the end of the list', () => {    const l = new List();    l.insertFirst('a');     l.insertLast('b');     expect(l.size()).toEqual(2);    expect(l.getLast().data).toEqual('b');  });}); describe.skip('GetAt', () => {  test('returns the node at given index', () => {    const l = new List();    expect(l.getAt(10)).toEqual(null);     l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);     expect(l.getAt(0).data).toEqual(1);    expect(l.getAt(1).data).toEqual(2);    expect(l.getAt(2).data).toEqual(3);    expect(l.getAt(3).data).toEqual(4);  });}); describe.skip('RemoveAt', () => {  test('removeAt doesnt crash on an empty list', () => {    const l = new List();    expect(() => {      l.removeAt(0);      l.removeAt(1);      l.removeAt(2);    }).not.toThrow();  });   test('removeAt doesnt crash on an index out of bounds', () => {    const l = new List();    expect(() => {      const l = new List();      l.insertFirst('a');      l.removeAt(1);    }).not.toThrow();  });   test('removeAt deletes the first node', () => {    const l = new List();    l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);    expect(l.getAt(0).data).toEqual(1);    l.removeAt(0);    expect(l.getAt(0).data).toEqual(2);  });   test('removeAt deletes the node at the given index', () => {    const l = new List();    l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);    expect(l.getAt(1).data).toEqual(2);    l.removeAt(1);    expect(l.getAt(1).data).toEqual(3);  });   test('removeAt works on the last node', () => {    const l = new List();    l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);    expect(l.getAt(3).data).toEqual(4);    l.removeAt(3);    expect(l.getAt(3)).toEqual(null);  });}); describe.skip('InsertAt', () => {  test('inserts a new node with data at the 0 index when the list is empty', () => {    const l = new List();    l.insertAt('hi', 0);    expect(l.getFirst().data).toEqual('hi');  });   test('inserts a new node with data at the 0 index when the list has elements', () => {    const l = new List();    l.insertLast('a');    l.insertLast('b');    l.insertLast('c');    l.insertAt('hi', 0);    expect(l.getAt(0).data).toEqual('hi');    expect(l.getAt(1).data).toEqual('a');    expect(l.getAt(2).data).toEqual('b');    expect(l.getAt(3).data).toEqual('c');  });   test('inserts a new node with data at a middle index', () => {    const l = new List();    l.insertLast('a');    l.insertLast('b');    l.insertLast('c');    l.insertLast('d');    l.insertAt('hi', 2);    expect(l.getAt(0).data).toEqual('a');    expect(l.getAt(1).data).toEqual('b');    expect(l.getAt(2).data).toEqual('hi');    expect(l.getAt(3).data).toEqual('c');    expect(l.getAt(4).data).toEqual('d');  });   test('inserts a new node with data at a last index', () => {    const l = new List();    l.insertLast('a');    l.insertLast('b');    l.insertAt('hi', 2);    expect(l.getAt(0).data).toEqual('a');    expect(l.getAt(1).data).toEqual('b');    expect(l.getAt(2).data).toEqual('hi');  });   test('insert a new node when index is out of bounds', () => {    const l = new List();    l.insertLast('a');    l.insertLast('b');    l.insertAt('hi', 30);     expect(l.getAt(0).data).toEqual('a');    expect(l.getAt(1).data).toEqual('b');    expect(l.getAt(2).data).toEqual('hi');  });}); describe.skip('ForEach', () => {  test('applies a transform to each node', () => {    const l = new List();     l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);     l.forEach(node => {      node.data += 10;    });     expect(l.getAt(0).data).toEqual(11);    expect(l.getAt(1).data).toEqual(12);    expect(l.getAt(2).data).toEqual(13);    expect(l.getAt(3).data).toEqual(14);  });}); describe.skip('for...of loops', () => {  test('works with the linked list', () => {    const l = new List();     l.insertLast(1);    l.insertLast(2);    l.insertLast(3);    l.insertLast(4);     for (let node of l) {      node.data += 10;    }     expect(l.getAt(0).data).toEqual(11);    expect(l.getAt(1).data).toEqual(12);    expect(l.getAt(2).data).toEqual(13);    expect(l.getAt(3).data).toEqual(14);  });   test('for...of works on an empty list', () => {    const l = new List();    expect(() => {      for (let node of l) {      }    }).not.toThrow();  });}); const L = require('./index');
const List = L.LinkedList;
const Node = L.Node;

test('List is a class', () => {
  expect(typeof List.prototype.constructor).toEqual('function');
});

test('Node is a class', () => {
  expect(typeof Node.prototype.constructor).toEqual('function');
});

describe.skip('A Node', () => {
  test('has properties "data" and "next"', () => {
    const node = new Node('a', 'b');
    expect(node.data).toEqual('a');
    expect(node.next).toEqual('b');
  });
});

describe.skip('Insert First', () => {
  test('appends a node to the start of the list', () => {
    const l = new List();
    l.insertFirst(1);
    expect(l.head.data).toEqual(1);
    l.insertFirst(2);
    expect(l.head.data).toEqual(2);
  });
});

describe.skip('Size', () => {
  test('returns the number of items in the linked list', () => {
    const l = new List();
    expect(l.size()).toEqual(0);
    l.insertFirst(1);
    l.insertFirst(1);
    l.insertFirst(1);
    l.insertFirst(1);
    expect(l.size()).toEqual(4);
  });
});

describe.skip('GetFirst', () => {
  test('returns the first element', () => {
    const l = new List();
    l.insertFirst(1);
    expect(l.getFirst().data).toEqual(1);
    l.insertFirst(2);
    expect(l.getFirst().data).toEqual(2);
  });
});

describe.skip('GetLast', () => {
  test('returns the last element', () => {
    const l = new List();
    l.insertFirst(2);
    expect(l.getLast()).toEqual({ data: 2, next: null });
    l.insertFirst(1);
    expect(l.getLast()).toEqual({ data: 2, next: null });
  });
});

describe.skip('Clear', () => {
  test('empties out the list', () => {
    const l = new List();
    expect(l.size()).toEqual(0);
    l.insertFirst(1);
    l.insertFirst(1);
    l.insertFirst(1);
    l.insertFirst(1);
    expect(l.size()).toEqual(4);
    l.clear();
    expect(l.size()).toEqual(0);
  });
});

describe.skip('RemoveFirst', () => {
  test('removes the first node when the list has a size of one', () => {
    const l = new List();
    l.insertFirst('a');
    l.removeFirst();
    expect(l.size()).toEqual(0);
    expect(l.getFirst()).toEqual(null);
  });

  test('removes the first node when the list has a size of three', () => {
    const l = new List();
    l.insertFirst('c');
    l.insertFirst('b');
    l.insertFirst('a');
    l.removeFirst();
    expect(l.size()).toEqual(2);
    expect(l.getFirst().data).toEqual('b');
    l.removeFirst();
    expect(l.size()).toEqual(1);
    expect(l.getFirst().data).toEqual('c');
  });
});

describe.skip('RemoveLast', () => {
  test('RemoveLast removes the last node when list is empty', () => {
    const l = new List();
    expect(() => {
      l.removeLast();
    }).not.toThrow();
  });

  test('RemoveLast removes the last node when list is length 1', () => {
    const l = new List();
    l.insertFirst('a');
    l.removeLast();
    expect(l.head).toEqual(null);
  });

  test('RemoveLast removes the last node when list is length 2', () => {
    const l = new List();
    l.insertFirst('b');
    l.insertFirst('a');

    l.removeLast();

    expect(l.size()).toEqual(1);
    expect(l.head.data).toEqual('a');
  });

  test('RemoveLast removes the last node when list is length 3', () => {
    const l = new List();
    l.insertFirst('c');
    l.insertFirst('b');
    l.insertFirst('a');
    l.removeLast();

    expect(l.size()).toEqual(2);
    expect(l.getLast().data).toEqual('b');
  });
});

describe.skip('InsertLast', () => {
  test('adds to the end of the list', () => {
    const l = new List();
    l.insertFirst('a');

    l.insertLast('b');

    expect(l.size()).toEqual(2);
    expect(l.getLast().data).toEqual('b');
  });
});

describe.skip('GetAt', () => {
  test('returns the node at given index', () => {
    const l = new List();
    expect(l.getAt(10)).toEqual(null);

    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);

    expect(l.getAt(0).data).toEqual(1);
    expect(l.getAt(1).data).toEqual(2);
    expect(l.getAt(2).data).toEqual(3);
    expect(l.getAt(3).data).toEqual(4);
  });
});

describe.skip('RemoveAt', () => {
  test('removeAt doesnt crash on an empty list', () => {
    const l = new List();
    expect(() => {
      l.removeAt(0);
      l.removeAt(1);
      l.removeAt(2);
    }).not.toThrow();
  });

  test('removeAt doesnt crash on an index out of bounds', () => {
    const l = new List();
    expect(() => {
      const l = new List();
      l.insertFirst('a');
      l.removeAt(1);
    }).not.toThrow();
  });

  test('removeAt deletes the first node', () => {
    const l = new List();
    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);
    expect(l.getAt(0).data).toEqual(1);
    l.removeAt(0);
    expect(l.getAt(0).data).toEqual(2);
  });

  test('removeAt deletes the node at the given index', () => {
    const l = new List();
    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);
    expect(l.getAt(1).data).toEqual(2);
    l.removeAt(1);
    expect(l.getAt(1).data).toEqual(3);
  });

  test('removeAt works on the last node', () => {
    const l = new List();
    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);
    expect(l.getAt(3).data).toEqual(4);
    l.removeAt(3);
    expect(l.getAt(3)).toEqual(null);
  });
});

describe.skip('InsertAt', () => {
  test('inserts a new node with data at the 0 index when the list is empty', () => {
    const l = new List();
    l.insertAt('hi', 0);
    expect(l.getFirst().data).toEqual('hi');
  });

  test('inserts a new node with data at the 0 index when the list has elements', () => {
    const l = new List();
    l.insertLast('a');
    l.insertLast('b');
    l.insertLast('c');
    l.insertAt('hi', 0);
    expect(l.getAt(0).data).toEqual('hi');
    expect(l.getAt(1).data).toEqual('a');
    expect(l.getAt(2).data).toEqual('b');
    expect(l.getAt(3).data).toEqual('c');
  });

  test('inserts a new node with data at a middle index', () => {
    const l = new List();
    l.insertLast('a');
    l.insertLast('b');
    l.insertLast('c');
    l.insertLast('d');
    l.insertAt('hi', 2);
    expect(l.getAt(0).data).toEqual('a');
    expect(l.getAt(1).data).toEqual('b');
    expect(l.getAt(2).data).toEqual('hi');
    expect(l.getAt(3).data).toEqual('c');
    expect(l.getAt(4).data).toEqual('d');
  });

  test('inserts a new node with data at a last index', () => {
    const l = new List();
    l.insertLast('a');
    l.insertLast('b');
    l.insertAt('hi', 2);
    expect(l.getAt(0).data).toEqual('a');
    expect(l.getAt(1).data).toEqual('b');
    expect(l.getAt(2).data).toEqual('hi');
  });

  test('insert a new node when index is out of bounds', () => {
    const l = new List();
    l.insertLast('a');
    l.insertLast('b');
    l.insertAt('hi', 30);

    expect(l.getAt(0).data).toEqual('a');
    expect(l.getAt(1).data).toEqual('b');
    expect(l.getAt(2).data).toEqual('hi');
  });
});

describe.skip('ForEach', () => {
  test('applies a transform to each node', () => {
    const l = new List();

    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);

    l.forEach(node => {
      node.data += 10;
    });

    expect(l.getAt(0).data).toEqual(11);
    expect(l.getAt(1).data).toEqual(12);
    expect(l.getAt(2).data).toEqual(13);
    expect(l.getAt(3).data).toEqual(14);
  });
});

describe.skip('for...of loops', () => {
  test('works with the linked list', () => {
    const l = new List();

    l.insertLast(1);
    l.insertLast(2);
    l.insertLast(3);
    l.insertLast(4);

    for (let node of l) {
      node.data += 10;
    }

    expect(l.getAt(0).data).toEqual(11);
    expect(l.getAt(1).data).toEqual(12);
    expect(l.getAt(2).data).toEqual(13);
    expect(l.getAt(3).data).toEqual(14);
  });

  test('for...of works on an empty list', () => {
    const l = new List();
    expect(() => {
      for (let node of l) {
      }
    }).not.toThrow();
  });
});
<head>  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" ></link>  <style>    pre, code {      white-space: pre-line;      min-width: 400px;    }  </style></head><body>  <h1>Node Class API</h1>  <table class="table">    <thead>      <tr>        <td>Function</td>        <td>Arguments</td>        <td>Returns</td>        <td>Directions</td>        <td>Example</td>      </tr>    </thead>    <tbody>      <tr>        <td>Node.constructor</td>        <td>(Data, Node)</td>        <td>Node</td>        <td>          Creates a class instance to represent a node.  The node should          have two properties, 'data' and 'next'.  Accept both          of these as arguments to the 'Node' constructor, then          assign them to the instance as properties 'data' and 'next'.          If 'next' is not provided to the constructor, then default its          value to be 'null'.        </td>        <td>          <pre>            const n = new Node('There');            n.data // 'Hi'            n.next // null            const n2 = new Node('Hi', n);            n.next // returns n          </pre>        </td>      </tr>    </tbody>  </table>   <h1>LinkedList Class API</h1>  <table class="table">    <thead>      <tr>        <td>Function</td>        <td>Arguments</td>        <td>Returns</td>        <td>Directions</td>        <td>Example</td>      </tr>    </thead>    <tbody>      <tr>        <td>constructor</td>        <td>-</td>        <td>(LinkedList)</td>        <td>          Create a class to represent a linked list.  When created,          a linked list should have *no* head node associated with it.          The LinkedList instance will have one property, 'head', which          is a reference to the first node of the linked list.  By default          'head' should be 'null'.        </td>        <td>          <pre>            const list = new LinkedList();            list.head // null          </pre>        </td>      </tr>      <tr>        <td>insertFirst</td>        <td>(data)</td>        <td>-</td>        <td>          Creates a new Node from argument 'data' and assigns the resulting          node to the 'head' property.  Make sure to handle the case in which          the linked list already has a node assigned to the 'head' property.        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('Hi There'); // List has one node          </pre>        </td>      </tr>      <tr>        <td>size</td>        <td>-</td>        <td>(integer)</td>        <td>          Returns the number of nodes in the linked list.        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.insertFirst('c');            list.size(); // returns 3          </pre>        </td>      </tr>      <tr>        <td>getFirst</td>        <td>-</td>        <td>(Node)</td>        <td>          Returns the first node of the linked list.        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.getFirst(); // returns Node instance with data 'a'          </pre>        </td>      </tr>      <tr>        <td>          getLast        </td>        <td>          -        </td>        <td>          (Node)        </td>        <td>          Returns the last node of the linked list        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.getLast(); // returns node with data 'a'          </pre>        </td>      </tr>      <tr>        <td>          clear        </td>        <td>          -        </td>        <td>          -        </td>        <td>          Empties the linked list of any nodes.        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.clear();            list.size(); // returns 0          </pre>        </td>      </tr>      <tr>        <td>          removeFirst        </td>        <td>          -        </td>        <td>          -        </td>        <td>          Removes only the first node of the linked list.  The list's head should          now be the second element.        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.removeFirst();            list.getFirst(); // returns node with data 'a'          </pre>        </td>      </tr>      <tr>        <td>          removeLast        </td>        <td>          -        </td>        <td>          -        </td>        <td>          Removes the last node of the chain        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.removeLast();            list.size(); // returns 1            list.getLast(); // returns node with data of 'b'          </pre>        </td>      </tr>      <tr>        <td>          insertLast        </td>        <td>          (Data)        </td>        <td>          -        </td>        <td>          Inserts a new node with provided data at the end of the chain        </td>        <td>          <pre>            const list = new LinkedList();            list.insertFirst('a');            list.insertFirst('b');            list.insertLast('c');            list.getLast(); // returns node with data 'C'          </pre>        </td>      </tr>      <tr>        <td>          getAt        </td>        <td>          (integer)        </td>        <td>          (Node)        </td>        <td>          Returns the node at the provided index        </td>        <td>          <pre>            const list = new List();            list.insertFirst('a');            list.insertFirst('b');            list.insertFirst('c');            list.getAt(1); // returns node with data 'b'          </pre>        </td>      </tr>      <tr>        <td>          removeAt        </td>        <td>          (integer)        </td>        <td>          -        </td>        <td>          Removes node at the provided index        </td>        <td>          <pre>            const list = new List();            list.insertFirst('a');            list.insertFirst('b');            list.insertFirst('c');            list.removeAt(1);            list.getAt(1); // returns node with data 'a'          </pre>        </td>      </tr>      <tr>        <td>          insertAt        </td>        <td>          (Data, integer)        </td>        <td>          -        </td>        <td>          Create an insert a new node at provided index.          If index is out of bounds, add the node to the end          of the list.        </td>        <td>          <pre>            const list = new List();            list.insertFirst('a');            list.insertFirst('b');            list.insertFirst('c');            list.insertAt('Hi', 1)            list.getAt(1); // returns node with data 'Hi'          </pre>        </td>      </tr>      <tr>        <td>          forEach        </td>        <td>          (function)        </td>        <td>          -        </td>        <td>          Calls the provided function with every node of the chain        </td>        <td>          <pre>            const list = new List();             list.insertLast(1);            list.insertLast(2);            list.insertLast(3);            list.insertLast(4);             list.forEach(node => {              node.data += 10;            });            list.getAt(0); // Returns node with data '11'          </pre>        </td>      </tr>      <tr>        <td>          for...of Loop        </td>        <td>          -        </td>        <td>          -        </td>        <td>          Linked list should be compatible as the subject of a 'for...of' loop        </td>        <td>          <pre>            const list = new List();             list.insertLast(1);            list.insertLast(2);            list.insertLast(3);            list.insertLast(4);             for (let node of list) {              node.data += 10;            }             node.getAt(1); // returns node with data 11          </pre>        </td>      </tr>    </tbody>  </table></body> <head>
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" ></link>
  <style>
    pre, code {
      white-space: pre-line;
      min-width: 400px;
    }
  </style>
</head>
<body>
  <h1>Node Class API</h1>
  <table class="table">
    <thead>
      <tr>
        <td>Function</td>
        <td>Arguments</td>
        <td>Returns</td>
        <td>Directions</td>
        <td>Example</td>
      </tr>
    </thead>
    <tbody>
      <tr>
        <td>Node.constructor</td>
        <td>(Data, Node)</td>
        <td>Node</td>
        <td>
          Creates a class instance to represent a node.  The node should
          have two properties, 'data' and 'next'.  Accept both
          of these as arguments to the 'Node' constructor, then
          assign them to the instance as properties 'data' and 'next'.
          If 'next' is not provided to the constructor, then default its
          value to be 'null'.
        </td>
        <td>
          <pre>
            const n = new Node('There');
            n.data // 'Hi'
            n.next // null
            const n2 = new Node('Hi', n);
            n.next // returns n
          </pre>
        </td>
      </tr>
    </tbody>
  </table>

  <h1>LinkedList Class API</h1>
  <table class="table">
    <thead>
      <tr>
        <td>Function</td>
        <td>Arguments</td>
        <td>Returns</td>
        <td>Directions</td>
        <td>Example</td>
      </tr>
    </thead>
    <tbody>
      <tr>
        <td>constructor</td>
        <td>-</td>
        <td>(LinkedList)</td>
        <td>
          Create a class to represent a linked list.  When created,
          a linked list should have *no* head node associated with it.
          The LinkedList instance will have one property, 'head', which
          is a reference to the first node of the linked list.  By default
          'head' should be 'null'.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.head // null
          </pre>
        </td>
      </tr>
      <tr>
        <td>insertFirst</td>
        <td>(data)</td>
        <td>-</td>
        <td>
          Creates a new Node from argument 'data' and assigns the resulting
          node to the 'head' property.  Make sure to handle the case in which
          the linked list already has a node assigned to the 'head' property.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('Hi There'); // List has one node
          </pre>
        </td>
      </tr>
      <tr>
        <td>size</td>
        <td>-</td>
        <td>(integer)</td>
        <td>
          Returns the number of nodes in the linked list.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.insertFirst('c');
            list.size(); // returns 3
          </pre>
        </td>
      </tr>
      <tr>
        <td>getFirst</td>
        <td>-</td>
        <td>(Node)</td>
        <td>
          Returns the first node of the linked list.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.getFirst(); // returns Node instance with data 'a'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          getLast
        </td>
        <td>
          -
        </td>
        <td>
          (Node)
        </td>
        <td>
          Returns the last node of the linked list
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.getLast(); // returns node with data 'a'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          clear
        </td>
        <td>
          -
        </td>
        <td>
          -
        </td>
        <td>
          Empties the linked list of any nodes.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.clear();
            list.size(); // returns 0
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          removeFirst
        </td>
        <td>
          -
        </td>
        <td>
          -
        </td>
        <td>
          Removes only the first node of the linked list.  The list's head should
          now be the second element.
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.removeFirst();
            list.getFirst(); // returns node with data 'a'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          removeLast
        </td>
        <td>
          -
        </td>
        <td>
          -
        </td>
        <td>
          Removes the last node of the chain
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.removeLast();
            list.size(); // returns 1
            list.getLast(); // returns node with data of 'b'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          insertLast
        </td>
        <td>
          (Data)
        </td>
        <td>
          -
        </td>
        <td>
          Inserts a new node with provided data at the end of the chain
        </td>
        <td>
          <pre>
            const list = new LinkedList();
            list.insertFirst('a');
            list.insertFirst('b');
            list.insertLast('c');
            list.getLast(); // returns node with data 'C'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          getAt
        </td>
        <td>
          (integer)
        </td>
        <td>
          (Node)
        </td>
        <td>
          Returns the node at the provided index
        </td>
        <td>
          <pre>
            const list = new List();
            list.insertFirst('a');
            list.insertFirst('b');
            list.insertFirst('c');
            list.getAt(1); // returns node with data 'b'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          removeAt
        </td>
        <td>
          (integer)
        </td>
        <td>
          -
        </td>
        <td>
          Removes node at the provided index
        </td>
        <td>
          <pre>
            const list = new List();
            list.insertFirst('a');
            list.insertFirst('b');
            list.insertFirst('c');
            list.removeAt(1);
            list.getAt(1); // returns node with data 'a'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          insertAt
        </td>
        <td>
          (Data, integer)
        </td>
        <td>
          -
        </td>
        <td>
          Create an insert a new node at provided index.
          If index is out of bounds, add the node to the end
          of the list.
        </td>
        <td>
          <pre>
            const list = new List();
            list.insertFirst('a');
            list.insertFirst('b');
            list.insertFirst('c');
            list.insertAt('Hi', 1)
            list.getAt(1); // returns node with data 'Hi'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          forEach
        </td>
        <td>
          (function)
        </td>
        <td>
          -
        </td>
        <td>
          Calls the provided function with every node of the chain
        </td>
        <td>
          <pre>
            const list = new List();

            list.insertLast(1);
            list.insertLast(2);
            list.insertLast(3);
            list.insertLast(4);

            list.forEach(node => {
              node.data += 10;
            });
            list.getAt(0); // Returns node with data '11'
          </pre>
        </td>
      </tr>
      <tr>
        <td>
          for...of Loop
        </td>
        <td>
          -
        </td>
        <td>
          -
        </td>
        <td>
          Linked list should be compatible as the subject of a 'for...of' loop
        </td>
        <td>
          <pre>
            const list = new List();

            list.insertLast(1);
            list.insertLast(2);
            list.insertLast(3);
            list.insertLast(4);

            for (let node of list) {
              node.data += 10;
            }

            node.getAt(1); // returns node with data 11
          </pre>
        </td>
      </tr>
    </tbody>
  </table>
</body>

Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest linkedlist inside the fork.

Directions

Try it first#

Solution#hide again

Solution#