链表

• 链表是一种非线性数据结构，用于存储一组有序的元素。
• 链表的元素通过指针相互连接，每个元素包含一个值和一个指向下一个元素的指针。
• 链表有多种类型，包括单向链表、双向链表和循环链表。
• 链表的操作包括插入、删除、查找等。

单向链表

function LinkedList() {
  function Node(data) {
    this.data = data;
    this.next = null;
  }

  this.head = null;
  this.length = 0;

  // 1.向链表尾部追加数据
  LinkedList.prototype.append = function (data) {
    var newNode = new Node(data);
    // 若链表为空
    if (this.length === 0) {
      // 将head指向第一个节点
      this.head = newNode;
    } else {
      var current = this.head;
      // 当current.next为null 的时候会退出循环
      while (current.next) {
        // 指针后移
        current = current.next;
      }
      // 当指到最后一个node时，给next append newNode
      current.next = newNode;
    }
    // 注意：append后长度要+1
    this.length += 1;
  };

  // 3.插入
  LinkedList.prototype.insert = function (position, data) {
    // 1.对position进行边界情况判断
    if (position < 0 || position > this.length) return false;

    var newNode = new Node(data);
    // 2.当在第一个位置插入的时候
    if (position === 0) {
      // 将要新节点的next与原链表相连
      newNode.next = this.head;
      // 改变head的指向到新的节点，有点移花接木的意思了哈～
      this.head = newNode;
    } else {
      // 3.这里要找到合适的插入位置
      var index = 0;
      var current = this.head;
      var previous = null;

      // 3.1 遍历的找到要插入的节点位置
      while (index++ < position) {
        previous = current; // 保存前一个节点
        current = current.next; // 保持当前节点
      }

      // 3.2 同样是移花接木
      newNode.next = current;
      previous.next = newNode;
    }

    this.length += 1;
    return true;
  };

  // 4.获取对应位置的数据
  LinkedList.prototype.get = function (position) {
    if (position < 0 || position >= this.length) return false;
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    return current.data;
  };

  // 5.返回数据当前位置
  LinkedList.prototype.indexOf = function (data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data === data) return index;
      current = current.next;
      index += 1;
    }
    return -1;
  };

  // 6.更新对应位置对数据
  LinkedList.prototype.update = function (position, newData) {
    if (position < 0 || position >= this.length) return false;
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.data = newData;
    return true;
  };

  // 7.根据位置删除数据
  LinkedList.prototype.removeAt = function (position) {
    if (position < 0 || position >= this.length) return null;
    var current = this.head;

    if (position === 0) {
      this.head = this.head.next;
    } else {
      var previous = null;
      var index = 0;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      // 将前一个节点的next执行下一个节点
      previous.next = current.next;
    }
    this.length -= 1;
    return current.data; // 返回删除的数据
  };

  // 8.删除数据
  LinkedList.prototype.remove = function (data) {
    var position = this.indexOf(data);
    return this.removeAt(position);
  };

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

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

  // 2.方便测试，先完成toString方法
  LinkedList.prototype.toString = function () {
    var current = this.head;
    var resultString = "";
    while (current) {
      resultString += current.data + " ";
      current = current.next;
    }
    return resultString;
  };
}

// 测试
var linked = new LinkedList();
linked.append("10");
linked.append("20");
linked.append("30");
console.log(linked.toString()); // 10 20 30

linked.insert(0, "00");
linked.insert(2, "22");
linked.insert(5, "55");
console.log(linked.toString()); // 00 10 22 20 30 55
console.log(linked.get(0)); // 00
console.log(linked.get(2)); // 22
console.log(linked.get(5)); // 55

console.log(linked.indexOf("00")); // 0
console.log(linked.indexOf("22")); // 2
console.log(linked.indexOf("123123")); // -1

linked.update(0, "000");
console.log(linked.get(0)); // 000

console.log(linked.removeAt(0)); // 000
console.log(linked.removeAt(4)); // 55
console.log(linked.toString()); // 10 22 20 30

console.log(linked.remove("10")); // 10
console.log(linked.toString()); // 22 20 30

算法-反转链表

var reverseList = function (head) {
  var p1 = head;
  var p2 = null;

  while (p1) {
    var temp = p1.next;
    p1.next = p2;
    p2 = p1;
    p1 = temp;
  }

  return p2;
};
// test

算法-环形链表

var hasCycle = function (head) {
  var p1 = head;
  var p2 = head;

  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 === p2) {
      return true;
    }
  }

  return false;
};

双向链表

function DoublyLinkedList() {
  // 内部类
  function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }

  // 属性
  this.head = null;
  this.tail = null;
  this.length = 0;

  // 1.向链表尾部追加数据
  DoublyLinkedList.prototype.append = function (data) {
    var newNode = new Node(data);
    // 若是第一次添加，直接将head和tail指向新节点即可
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 让tail与新节点的prev建立连接
      newNode.prev = this.tail;
      // tail的next指向新节点
      this.tail.next = newNode;
      // 改变tail指针
      this.tail = newNode;
    }

    this.length += 1;
  };

  // 2.向链表中插入数据
  DoublyLinkedList.prototype.insert = function (position, data) {
    // 1.边界判断
    if (position < 0 || position > this.length) return false;
    var newNode = new Node(data);

    // 2.第一次添加
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      if (position === 0) {
        // 3.1 在头部插入
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      } else if (position === this.length) {
        // 3.2 在尾部插入
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
      } else {
        // 3.3 在中间插入 0 < position < this.length
        var current = this.head;
        var index = 0;
        // 找到要插入的位置
        while (index++ < position) {
          current = current.next;
        }
        // 让新节点的next 指向要插入位置的节点(current)
        newNode.next = current;
        // 让新节点的prev 指向 current的prev
        newNode.prev = current.prev;
        // 将新节点与 当前节点的 前一个节点的 next建立关系
        current.prev.next = newNode;
        // 让newNode成为current的前一个节点
        current.prev = newNode;
      }
    }
    this.length += 1;
    return true;
  };

  // 3.获取对应位置数据
  DoublyLinkedList.prototype.get = function (position) {
    if (position < 0 || position >= this.length) return null;

    if (Math.floor(this.length / 2) > position) {
      // 从前往后遍历
      var index = 0;
      var current = this.head;
      while (index++ < position) {
        current = current.next;
      }
      return current.data;
    } else {
      // 从后往前遍历
      var index = this.length - 1;
      var current = this.tail;
      while (index-- > position) {
        current = current.prev;
      }
      return current.data;
    }
  };

  // 4.获取数据对应的位置
  DoublyLinkedList.prototype.indexOf = function (data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data === data) return index;
      current = current.next;
      index += 1;
    }

    return -1;
  };

  // 5.更新方法
  DoublyLinkedList.prototype.update = function (position, newData) {
    if (position < 0 || position >= this.length) return false;
    if (Math.floor(this.length / 2) > position) {
      // 从前往后 遍历
      var current = this.head;
      var index = 0;
      while (index++ < position) {
        current = current.next;
      }
      current.data = newData;
      return true;
    } else {
      // 从后往前 遍历
      var current = this.tail;
      var index = this.length - 1;
      while (index-- > position) {
        current = current.prev;
      }
      current.data = newData;
      return true;
    }
  };

  // 6.删除指定位置
  DoublyLinkedList.prototype.removeAt = function (position) {
    if (position < 0 || position >= this.length) return null;
    var current = this.head;

    // 1.只有一个节点时
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      // 2.删除 头部节点
      if (position === 0) {
        this.head.next.prev = null;
        this.head = this.head.next;
      } else if (position === this.length - 1) {
        // 3.删除尾部节点
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
        // 如果上面一种不好理解，也可以用下面这种写法
        // current = this.tail;
        // this.tail = this.tail.prev;
        // this.tail.next = null;
      } else {
        // 4.删除中间
        var index = 0;
        while (index++ < position) {
          current = current.next;
        }
        current.next.prev = current.prev;
        current.prev.next = current.next;
      }
    }

    this.length -= 1;
    return current.data;
  };

  // 7.remove
  DoublyLinkedList.prototype.remove = function (data) {
    var position = this.indexOf(data);
    return this.removeAt(position);
  };

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

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

  DoublyLinkedList.prototype.toString = function () {
    return this.forwardString();
  };

  // 返回正向遍历节点字符串形式
  DoublyLinkedList.prototype.forwardString = function () {
    var current = this.head;
    var resultString = "";
    while (current) {
      resultString += current.data + " ";
      current = current.next;
    }
    return resultString;
  };

  // 返回反向遍历的节点的字符串形式
  DoublyLinkedList.prototype.backwardString = function () {
    var current = this.tail;
    var resultString = "";
    while (current) {
      resultString += current.data + " ";
      current = current.prev;
    }
    return resultString;
  };
}

// test
var dll = new DoublyLinkedList();

dll.append("10");
dll.append("20");
dll.append("30");
console.log(dll.toString()); // 10 20 30
console.log(dll.forwardString()); // 10 20 30
console.log(dll.backwardString()); // 30 20 10

dll.insert(0, "000");
dll.insert(2, "222");
dll.insert(5, "555");
console.log(dll.toString()); // 000 10 222 20 30 555

console.log(dll.get(0)); // 000
console.log(dll.get(2)); // 222
console.log(dll.get(3)); // 20
console.log(dll.get(5)); // 555

console.log(dll.indexOf("000")); // 0
console.log(dll.indexOf("222")); // 2

dll.update(1, "111");
dll.update(3, "333");
dll.update(4, "444");
console.log(dll.toString()); // 000 111 222 333 444 555

console.log(dll.removeAt(0)); // 000
console.log(dll.removeAt(1)); // 222
console.log(dll.removeAt(3)); // 555
console.log(dll.toString()); // 111 333 444

console.log(dll.remove("111")); // 111
console.log(dll.toString()); // 333 444