本文源码 这里

概念

1.类似于数组一样存储多个数据的数据结构2.链表中每个元素称为节点，每个节点包含元素内容和指向下一个节点的指针

和数组对比

链表的优点 1.内存空间不是必须连续的。可以实现灵活的内存管理2.链表不必再创建时就确定大小，并且大小可以无限延伸下去3.链表再插入和删除数据时，时间复杂度低，效率高

链表的缺点 1.访问任何一个位置的元素时，都需要从头开始访问(无法跳过第一或任何一个元素) 2.无法通过下标直接访问元素

数组的优点 1.占用内存空间少2.数组内的数据可以随机访问3.数据查找效率较高（内存连续）

数组的缺点 1.插入和删除效率低，因为要移动操作元素之后的所有元素(无法跳过第一或任何一个元素) 2.数组大小固定，不能动态拓展(大多数语言是这样js的是动态的)

封装一个单向链表

function LinkedList() {
  // 链表头
  this.head = null;
  // 链表长度
  this.length = 0;
  // 节点类
  function Node(data) {
    // 存储节点包含的数据
    this.data = data;
    // 存储指向下一个节点的指针(引用)
    this.next = null;
  }
}

封装一些基本方法

只列举插入、添加、删除三个方法，其他方法可以查看源代码 1.append(data)----给链表尾部追加节点方法，参数:节点数据 不返回结果 javascript LinkedList.prototype.append = function (data) { // 1.创建新节点 let node = new Node(data); // 2.判断是否是第一个节点 也可以根据heae是否为空判断 if (this.length === 0) { this.head = node; } else { // 当前第一个节点 let current = this.head; // 通过判断每个节点的next是否为空来找到最后一个元素 while (current.next) { current = current.next; }; // 然后给将最后一个元素的next指向我们新添加的元素 current.next = node; } // 3.更新长度 this.length++; };

不理解的时候画图就好了

2.toString()----打印每个节点data内容 3.insert(position,data)----向特定位置插入节点，参数:位置索引,插入数据 成功返回1，失败返回0

LinkedList.prototype.insert = function (position, data) {
  // 1.对position做越界判断  即插入位置是否存在
  if (position >= 0 && position <= this.length) {
    let node = new Node(data);
    // 2.插入位置是第一个时
    if (position === 0) {
      // 让要插入的节点的指针指向原来的第一个节点
      node.next = this.head;
      // 让head指向要插入的节点
      this.head = node;
    } else {
      // 标识每一个节点的位置  previous保存前一个节点
      let index = 0,
        current = this.head,
        previous;
      // 当index=position时跳出循环
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
    }
    this.length++;
    return true;
  } else {
    return false;
  }
};

4.get(position)-----获取指定位置节点的数据 参数:位置索引 返回获取到的数据或-1 5.indexof(data)-----在链表中查找指定数据 参数:要查找的数据 返回目标数据节点位置 ，没有返回-1 6.update(position,data)-----修改指定位置的数据 参数:位置索引,要修改的数据 成功返回1，失败返回0 7.removeAt(position)-----删除指定位置的节点 参数:位置索引 成功返回删除节点data，失败返回-1

LinkedList.prototype.removeAt = function (position) {
  // 越界判断
  if (position >= 0 && position <= this.length) {
    let index = 0,
      current = this.head,
      previous;
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    // 更新长度
    this.length--;
    return current.data;
  } else {
    return -1;
  }
};

8.remove(data)-----根据data移除该data所在节点 参数:要删除的数据 成功返回删除节点data，失败返回-1 9.size()-----返回链表对的元素个数 10.isEmpty()------判断链表是否为空