javascript 数据结构系列 (一) 单向链表

Singly linked list

本章主要介绍单向链表,具体讲解实现之前,首先说一下,单向链表实现相关列 node 具体结构技术实现

node 包含下一个节点与上一个节点引用,代码实现如下:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}

其次,看一下Singly linked list 类实现过程
构造函数

  constructor() {
    this.first = null; // head/root element
  }

addLast 添加元素到链表末端

  addLast(value) {
    const node = new Node(value);

    if (this.first) {
      let currentNode = this.first;
      while (currentNode && currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    } else {
      this.first = node;
    }
  }

removeLast 移除最后一个元素

  removeLast() {
    let current = this.first;
    let target;

    if (current && current.next) {
      while (current && current.next && current.next.next) {
        current = current.next;
      }
      target = current.next;
      current.next = null;
    } else {
      this.first = null;
      target = current;
    }

    if (target) {
      return target.value;
    }
  }

addFirst 添加第一个元素

  addFirst(value) {
    const node = new Node(value);
    node.next = this.first;
    this.first = node;
  }

removeFist 移除第一个元素

  removeFirst() {
    const first = this.first;

    if (first) {
      this.first = first.next;
      return first.value;
    }
  }

contains 查找链表中包含的元素,并且返回该元素位置

  contains(value) {
    for (let current = this.first, index = 0; current; index++, current = current.next) {
      if (current.value === value) {
        return index;
      }
    }
  }

removeAt 删除指定位置元素

  removeAt(nth) {
    if (nth === 0) {
      return this.removeFirst();
    }

    for (let current = this.first, index = 0; current; index++, current = current.next) {
      if (index === nth) {
        if (!current.next) { // if it doesn't have next it means that it is the last
          return this.removeLast();
        }
        current.previous = current.next;
        return current.value;
      }
    }
  }

评论

暂无评论