JavaScript 链表：方法 removeHead() 和 contains() 不起作用

Question

使用ES6风格，任务是建立一个链表并通过npm linter测试。这是我写的代码：

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    // Do not modify anything inside of the constructor
  }
  // Wraps the given value in a node object and adds the node to the tail of the list
  // If the list is empty, the new element is considered the tail as 
well as the head
  // If there is one element in the list before the new element is added, the new element becomes the tail of the list
  addToTail(value) {
    const newNode = {
      value,
      next: null
    };
    if (!(this.head) && !(this.tail)) {
      this.head = newNode;
      this.tail = newNode;
    } else this.tail = newNode;
  }
  // Removes the current head node from the list, replacing it with the next element in the list
  // Returns the value of the removed node
  removeHead() {
    const removedHead = this.head.value;
    this.head = this.head.next;
    return removedHead;
  }
  // Checks the linked list for the given value
  // Returns true if the the value is found in the list, false otherwise
  contains(value) {
    let found = false;
    let checkedNode = this.head;
    while (checkedNode) {
      if (checkedNode.value === value) {
        found = true;
      }
      checkedNode = checkedNode.next;
    } return found;
  }
}

这是 linting 错误：

● LinkedList › should remove head when removeHead is invoked

    TypeError: Cannot read property 'value' of null

      at Object.<anonymous> (tests/linked-list.test.js:48:21)

  LinkedList
    ✓ should have the methods "addToTail", "removeHead", and "contains" (5ms)
    ✓ should update the tail value when a new node is added (2ms)
    ✓ should keep the same head after adding nodes (2ms)
    ✕ should return true from contains if a matching value is found and false otherwise (4ms)
    ✕ should remove head when removeHead is invoked (2ms)
    ✓ should return the head that is removed when removeHead is invoked (1ms)
    ✓ should not contain removed values (1ms)

这是测试它的文件：

/* eslint-disable no-undef, no-prototype-builtins */
const LinkedList = require('../src/linked-list');

let list;

describe('LinkedList', () => {
  beforeEach(() => {
    list = new LinkedList();
  });

  it('should have the methods "addToTail", "removeHead", and "contains"', () => {
    const hasAddToTail = 
Object.getPrototypeOf(list).hasOwnProperty('addToTail');
    const hasRemoveHead = 
Object.getPrototypeOf(list).hasOwnProperty('removeHead');
    const hasContains = 
Object.getPrototypeOf(list).hasOwnProperty('contains');
    expect(hasAddToTail).toBe(true);
    expect(hasRemoveHead).toBe(true);
    expect(hasContains).toBe(true);
  });

  it('should update the tail value when a new node is added', () => {
    list.addToTail(1);
    expect(list.tail.value).toBe(1);
    list.addToTail(2);
    expect(list.tail.value).toBe(2);
  });

  it('should keep the same head after adding nodes', () => {
    list.addToTail(1);
    expect(list.head.value).toBe(1);
    list.addToTail(2);
    expect(list.head.value).toBe(1);
  });

  it('should return true from contains if a matching value is found and false otherwise', () => {
    list.addToTail(1);
    list.addToTail(2);
    list.addToTail('hello');
    list.addToTail(true);
    expect(list.contains('hello')).toBe(true);
    expect(list.contains('asdf')).toBe(false);
  });

  it('should remove head when removeHead is invoked', () => {
    list.addToTail(1);
    list.addToTail(2);
    expect(list.head.value).toBe(1);
    list.removeHead();
    expect(list.head.value).toBe(2);
    list.removeHead();
    expect(list.head).toBe(null);
  });

  it('should return the head that is removed when removeHead is invoked', () => {
    list.addToTail(1);
    expect(list.removeHead()).toBe(1);
  });

  it('should not contain removed values', () => {
    list.addToTail(1);
    list.addToTail(2);
    list.addToTail(3);
    list.addToTail(4);
    list.removeHead();
    expect(list.contains(1)).toBe(false);
  });
});

仅有的两个错误是未移除标头和未返回正确的布尔值。我不知道为什么。

Answer 1

插入新元素时从未设置 next 引用。

试试这个：

if (!(this.head) && !(this.tail)) {
  this.head = newNode;
  this.tail = newNode;
} else {
    this.tail.next = newNode;
    this.tail = newNode;
}

JavaScript 链表：方法 removeHead() 和 contains() 不起作用

JavaScript Linked List: Methods removeHead() and contains() not working

javascript

node.js

npm

linter