bug(linked-list): insert method duplicates value of head in tail

[mg901]

Hi, guys! Thank you for this awesome repository! The other day I found this problem

const list = new List();

list.insert(2, 0);
list.insert(3, 1);
list.insert(4, 2);

returns

{
  "head": {
    "data": 2,
    "next": {
      "data": 3,
      "next": {
        "data": 4,
        "next": null
      }
    }
  },
  "tail": {
    "data": 2,
    "next": {
      "data": 3,
      "next": {
        "data": 4,
        "next": null
      }
    }
  },
}

It solved if you add this code after line 77.

this.tail.next = newNode;
this.tail = newNode;

[xyn22]

@mg901 be careful if you are running insert to the middle, then the solution proposed above would fail, creating infinite loop with the next insert.

Try running the below to see it failing:

    const linkedList = new LinkedList();

    linkedList.insert(4, 3);
    expect(linkedList.head.toString()).toBe('4');
    expect(linkedList.tail.toString()).toBe('4');

    linkedList.insert(3, 2);
    linkedList.insert(2, 1);
    linkedList.insert(1, -7);
    linkedList.insert(10, 9);
    linkedList.insert(7, 5);
    expect(linkedList.toString()).toBe('1,4,2,3,10,7');
    expect(linkedList.head.toString()).toBe('1');
    expect(linkedList.tail.toString()).toBe('7');

[mg901]

@xyn22 Thank you, but I decided to write a simpler and more reliable implementation of the insert method. You can see it here on line 122.

[mg901]

@xyn22 I tried to take into account all test cases.

  describe('insertAt method', () => {
    it('should throw exception if index less than list length', () => {
      expect(() => list.insertAt(1, -1)).toThrow('Index `-1` out of range.');
    });

    it('should throw exception if index greater than list length', () => {
      expect(() => list.insertAt(1, 10)).toThrow('Index `10` out of range.');
    });

    it('should insert at index 0 correctly', () => {
      list.append(1);
      expect(list.toString()).toBe('1');
      expect(list.getSize()).toBe(1);

      list.insertAt(0, 0);
      expect(list.head.toString()).toBe('0');
      expect(list.tail.toString()).toBe('1');
      expect(list.toString()).toBe('0,1');
      expect(list.getSize()).toBe(2);
    });

    it('should insert at index equal to length of list correctly', () => {
      list.append(1);
      expect(list.toString()).toBe('1');
      expect(list.getSize()).toBe(1);

      list.insertAt(2, 1);
      expect(list.head.toString()).toBe('1');
      expect(list.tail.toString()).toBe('2');
      expect(list.toString()).toBe('1,2');
      expect(list.getSize()).toBe(2);
    });

    it('should insert at the beginning of the list correctly', () => {
      list.append(1).append(2).append(3);
      expect(list.toString()).toBe('1,2,3');
      expect(list.getSize()).toBe(3);

      list.insertAt(0, 0);
      expect(list.head.toString()).toBe('0');
      expect(list.tail.toString()).toBe('3');
      expect(list.toString()).toBe('0,1,2,3');
      expect(list.getSize()).toBe(4);
    });

    it('should insert at the end of the list correctly', () => {
      list.append(1).append(2).append(3);
      expect(list.toString()).toBe('1,2,3');
      expect(list.getSize()).toBe(3);

      list.insertAt(4, 3);
      expect(list.head.toString()).toBe('1');
      expect(list.tail.toString()).toBe('4');
      expect(list.toString()).toBe('1,2,3,4');
      expect(list.getSize()).toBe(4);
    });

    it('should insert in the middle of list correctly', () => {
      list.append(1).append(2).append(4);
      expect(list.toString()).toBe('1,2,4');
      expect(list.getSize()).toBe(3);

      list.insertAt(3, 2);
      expect(list.head.toString()).toBe('1');
      expect(list.tail.toString()).toBe('4');
      expect(list.toString()).toBe('1,2,3,4');
      expect(list.getSize()).toBe(4);
    });
  });