JavaScript数据结构和算法-链表

数组 vs 链表

数组

• 连续的存储空间

• 下标从 0 开始

• 访问元素的速度快，直接通过下标进行访问

• 插入或者删除操作慢，需要移动其他元素的位置

• 存储的元素类型相同（但是 JS 中没有做这个限制 -> 可以使用 TS 来进行约束）

链表

• 不连续的存储

• 插入或者删除操作快，只需要移动指针

• 访问元素的速度慢需要从表头开始遍历

数据结构

单向链表

首先我们需要明确链表需要实现的方法：

1. size

2. append(element)

3. insert(position, element)

4. removeAt(position)

5. remove(element)

6. indexOf(element)

7. isEmpty

8. toString

9. getHead

其次，我们需要一个辅助类来表示链表上的每一个节点（存储该节点的元素和一个指向下一个节点的指针）

function LinkList() {
  // 辅助类，表示链表中的每一个节点
  function Node(element) {
    this.element = element;
    this.next = null;
  }
  // 记录链表长度
  let length = 0;
  // 头节点
  let head = null;
  this.append = function(element) {
    const node = new Node(element);
    let current;
    if (head === null) {
      head = node;
    } else {
      current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
  };
  this.removeAt = function(position) {
    if (position > -1 && position < length) {
      let index = 0,
        previous,
        current = head;
      if (position === 0) {
        head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        return current.element;
      }
      length--;
    } else {
      return null;
    }
  };
  this.insert = function(position, element) {
    if (position > -1 && position <= length) {
      const node = new Node(element);
      let index = 0,
        previous,
        current = head;
      if (position === 0) {
        node.next = current;
        head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = node;
        node.next = current;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };
  this.toString = function() {
    let current = head;
    let string = "";
    while (current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };

  this.size = function() {
    return length;
  };

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

  this.indexOf = function(element) {
    let index = 0;
    let current = head;
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };

  this.remove = function(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  };

  this.getHead = function() {
    return head;
  };
}

双向链表

双向链表和普通链表的区别就是：它的每一个节点有两个指针，分别指向它的下一个节点和前一个节点

双向链表相对于单向链表的优点：双向链表中我们可以访问某一个节点的前一个节点/后一个节点；但是在单向链表中，我们一旦错过了某一个节点就需要重头开始查找。

双向链表的结构相对于普通链表是有新增的

function DoublyLinkedList() {
  function Node(element) {
    this.element = element;
    this.next = null;
    // highlight-next-line
    this.prev = null; // 新增
  }
  let head = null;
  // highlight-next-line
  let tail = null; // 新增
  let length = 0;
}

function DoublyLinkedList() {
  function Node(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
  let length = 0;
  let head = null;
  let tail = null;
  this.append = function(element) {
    const node = new Node(element);
    let current;
    if (head === null) {
      head = tail = node;
    } else {
      current = tail;
      current.next = node;
      node.prev = current;
      tail = node;
    }
    length++;
  };
  this.insert = function(element, position) {
    if (position > -1 && position <= length) {
      const node = new Node(element);
      let previous,
        current,
        index = 0;
      if (position === 0) {
        if (head === null) {
          head = tail = node;
        } else {
          current = head;
          node.next = current;
          current.prev = node;
          head = node;
        }
      } else if (position === length) {
        current = tail;
        node.prev = current;
        current.next = node;
        tail = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = node;
        node.next = current;
        current.prev = node;
        node.prev = previous;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };

  this.removeAt = function(position) {
    if (position > -1 && position < length) {
      let current,
        previous,
        index = 0;
      if (position === 0) {
        current = head;
        head = current.next;
        if (length === 1) {
          tail = null;
        } else {
          head.prev = null;
        }
      } else if (position === length - 1) {
        current = tail;
        tail = current.prev;
        tail.next = null;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        current.next.prev = previous;
      }
      length--;
      return current.element;
    } else {
      return null;
    }
  };
  this.indexOf = function(element) {
    let index = 0;
    let current = head;
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  this.remove = function(element) {
    const index = this.indexOf(element);
    return this.removeAt(element);
  };
  this.isEmpty = function() {
    return length === 0;
  };
  this.size = function() {
    return length;
  };
  this.getHead = function() {
    return head;
  };
  this.getTail = function() {
    return tail;
  };
  this.toString = function() {
    let string = "",
      current = head;
    while (current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };
}

循环链表

• 单向循环链表：最后一个元素的 next 指针指向 head

• 双向循环链表：tail.next -> head && head.prev -> tail