📝个人主页：爱吃炫迈
💌系列专栏：数据结构与算法
🧑‍💻座右铭：道阻且长，行则将至💗

链表

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

线性表的顺序存储结构缺点是每一次插入和删除元素，大量元素的移动会导致时间效率低下。为了改进顺序存储结构的缺点，引入链式存储结构，即为链表。

链式存储结构的特点是用一组任意的存储单元来存储线性表中的数据元素。这样在插入和删除元素时，可以通过直接修改指针完成操作，时间效率大大提高。但因为链式存储结构的存储单元不连续，所以需要通过指针来访问它的后续元素。

为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，我们需要存出一个其直接后继的存储位置。我们把存储数据元素信息的域成为数据域，把存储后继位置的域称为指针域，这两部分构成一个节点。

n个节点链接成一个链表，即为线性表的链式存储结构。因为每个节点只有一个指针域，所以又将这样的链表称为单链表。

链表的分类

✨线性表可以分为顺序表和链表 :

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

✨顺序表和链表有以下几点区别：

• 空间开辟方式：顺序表在存储数据之前开辟足够空间，后期无法改变大小（动态数组除外），链表一次只开辟存储一个节点的内存空间。一次开辟大量空间比多次开辟小量空间性能好。
• 空间利用率：链表每次申请一个节点的空间，且位置随机。这种申请存储空间的方式会有很多空间碎片，一定程度上造成了空间浪费。此外，链表每个节点至少需携带一个指针，增加了空间占用。因此，顺序表空间利用率比链表高。
• 时间复杂度：顺序表可以使用下标直接访问元素，它的时间复杂度为O(1)，链表需从头开始，依次遍历，时间复杂度为O(n)。顺序表中插入、删除、移动元素，可能涉及大量元素的整体移动，时间复杂度为O(n)，链表插入、删除、移动元素，只需改变指针指向，时间复杂度为O(1)。

✨链表可以分为以下几类：

• 单向链表：是链表中最简单的，它包含两个域，一个信息域和一个指针域，指针指向链表中的下一个节点，最后一个节点的指针指向一个空值。

• 静态单向链表：用数组描述的单向链表，称为静态单向链表。它的内存地址是连续的，需预先分配大小。
• 动态单向链表：用申请内存的函数动态申请内存，链表长度没有限制，节点内存地址不是连续的，需通过指针来顺序访问。
• 双向链表：每个节点有两个连接，一个指向前一节点，另一个指向后一节点。首、尾节点对应的前、后连接指向空值或空列表。

• 循环链表：首节点、尾节点连接在一起。循环链表第一个节点之前就是最后一个节点；反之亦然。

• 单向循环链表：它的最后一个节点指针不是 NULL，而改为指向头节点，从而整个链表形成一个环。
• 双向循环链表：由单向循环链表可以推断出双向循环链表，它的头节点还会指向尾节点。

这篇文章只介绍单向链表。

创建链表

LinkedList类的骨架

// 判断两个元素是否相等
function defaultEquals(a, b) {
  return a === b
}

// 创建元素节点
class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

// 定义LinkedList类，表示链表
class LinkedList {
  // 可以自定义传入比较元素相等的方法，如果没有使用defaultEquals
  constructor(equalsFn = defaultEquals) {
      this.count = 0; // 存储链表数量
      this.head = undefined; // 第一个元素
      this.equalsFn = equalsFn; // 判断两个元素是否相等
  }
  push(element) {} // 向链表尾部添加一个新元素
  insert(element,position) {} // 向链表特定位置插入一个新元素
  getElementAt(index) {} // 返回链表特定位置的元素
  remove(element) {} // 从链表中移除一个元素
  indexOf() {} // 返回元素在链表中的索引，没有则返回-1
  removeAt(position) {} // 从链表特定位置移除一个元素
  isEmpty() {} // 判断链表是否为空
  size() {} // 返回链表包含的元素个数
  toString() {} // 返回整个链表的字符串
 }

实现链表的方法

• push尾部添加元素
• insert任意处添加元素
• getElementAt查找元素位置
• removeAt从指定位置移除元素
• indexOf查找元素位置
• remove删除指定元素
• isEmpty判断链表是否为空
• toString 将链表转化为字符串
• size返回链表长度

push尾部添加元素

• 新增元素分为两种情况，链表为空和链表不为空。
• 链表为空时，新增的元素作为链表头（直接赋值）；
• 链表不为空时，从链表尾添加，即原链表尾的指针next指向新增元素。

push(element) {
    const node = new Node(element);// 创建新节点
    let current;
    // 头部为空
    if (this.head == null) {
        this.head = node;
        // 头部不为空
    } else {
        current = this.head; // 当前元素
        while(current.next != null) { // 获取最后一项
            current = current.next;
        }
        // 将next赋值为新元素，建立链接
        current.next = node;
    }
    this.count++;
}

insert任意处添加元素

• 根据下标找到目标节点，从目标节点之前插入新元素，
• 插入元素分为两种情况，头部插入和非头部插入。
• 头部插入（下标等于0），即插入的元素作为链表头；
• 非头部插入，找到目标节点和目标节点的前一个节点（我们称之为前节点），使前节点的指针指向插入节点，而插入节点的指针指向目标节点，完成插入。
• 如下图是非头部插入示意图，node2为目标节点，node1为前节点，node3为插入节点，使node1的指针指向node3，而node3的指针指向node2，即完成了插入操作。

insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(element);// 定义一个新结点
        if (index === 0) { // 链表头添加
            const current = this.head;// 先把原链表头赋值给current
            node.next = current;// 链表头的指针指向原链表头，完成插入
            this.head = node;// 插入的新节点作为链表头
        } else { //非链表头添加
            const previous = this.getElementAt(index - 1);
            const current = previous.next;
            node.next = current; // 插入项的指针指向目标项
            previous.next = node;// 目标项的前一项的指针指向插入项
        }
        this.count ++; // 长度加1
        return true;
    }
    return false;
}

getElementAt查找元素位置

getElementAt(index) {
    if (index >= 0 && index < this.count) {
        let node = this.head;//从头部开始查找
        for (let i = 0; i < index && node != null; i++) {// 遍历链表
            node = node.next;
        }
        return node;
    }
    return undefined;
}

removeAt从指定位置移除元素

• 根据下标移除元素也分为两种情况，移除链表头和移除非链表头节点。
• 移除链表头节点（下标等于0），即使原链表头的指针指向的节点作为新链表头；
• 移除非链表头节点，根据下标找到需要移除的目标节点和它的前一个节点，使前结点的指针 指向 目标节点的指针所指向的节点，即完成了移除目标节点。
• 如下图是移除非链表头节点示意图，node1为目标节点，head为前节点，node2为node1指针指向的节点，使head的指针指向node2，即完成了移除node1节点的操作。

// 从链表中移除元素，并返回移除项
removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
        let current = this.head;
        // 移除链表头
        if (index === 0) {
            this.head = current.next;// 使原表头的指针变成新表头
        } else {// 移除非链表头
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;// 跳过当前项，使前一项的指针指向当前项的指针
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

indexOf查找元素位置

从头部开始查找，如果当前查找节点等于目标节点就返回对应的下标，否则继续往后查找；若链表循环结束了还没找到，则返回-1（不存在）。

// 查找元素位置
indexOf(element) {
    let current = this.head;// 从头部开始查找
    for (let i = 0; i < this.count && current != null; i++) {
        if (this.equalsFn(element, current.element)) {// 如果当前节点的值等于目标项
            return i;// 返回对应下标
        }
        current = current.next;// 否则继续往后查找
    }
    return -1;
}

remove删除指定元素

• 调用indexOf(element)方法找到目标项的下标；

• 调用removeAt(position)方法根据目标项的下标移除目标项

// 从链表中移除元素
remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
}

isEmpty判断链表是否为空

isEmpty() {
  return this.size() === 0;
}

toString 将链表转化为字符串

toString() {
  if (this.head == null) {
    return '';
  }
  let objString = `${this.head.element}`;
  let current = this.head.next;
  for (let i = 1; i < this.size() && current != null; i ++) {
    objString = `${objString},${current.element}`;
    current = current.next;
  }
  return objString;
}

size返回链表长度

size() {
  return this.count;
}

测试

const list = new LinkedList();
console.log(list.isEmpty()); //true
list.push(12);
list.push(11);
list.push(10);
list.push(9);
console.log(list); //12 11 10 9
console.log(list.size());//4
console.log(list.isEmpty()); //falae
console.log(list.indexOf(12)); //0
console.log(list.getElementAt(0)); //12
console.log(list.toString()); //12,11,10,9

// insert()添加元素
list.insert(3, 3);
console.log(list);//12 11 10 3 9

// removeAt()：移除指定位置的元素
list.removeAt(2);
console.log(list); //12 11 9

// remove():删除元素
list.remove(11)
console.log(list); //12 10 9

LeetCode例题

LeetCode题目：反转链表
思路 :

改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。如下图所示：

步骤 ：

• pre:指向当前需要反转节点的前一个节点
• node:指向当前需要反转的节点

1. 定义两个指针pre和node：pre在前，node在后
2. 每次让node.next指向pre，实现一次局部反转
3. 局部反转完成之后，pre和node都向前移动一个位置
4. 循环上述过程，直到node到达链表尾部

代码 ：

var reverseList = function (head) {
  let pre = null; //当前需要翻转节点的前一个节点
  let node = head; //当前需要翻转的节点
  while (node) {
    let nextNode = node.next;
    // 翻转指针
    node.next = pre;
    // pre和node都往后移动
    pre = node;
    node = nextNode;
  }
  // 此时pre是新的头结点，所以返回
  return pre;
};

💞总结💞

希望我的文章能对你学习链表的知识有所帮助！