灏天阁

JS数据结构之 - 链表

· Yin灏

初识链表

什么是链表

链表是由 链表节点 + 指针变量 组成的一种数据结构，它包含 data（节点的数据）、next（下一个节点的地址）两个属性。每个节点通过 next 属性指向下一个节点。

const linkListNode = {
  data: "a",
  next: {
    data: "b",
    next: null,
  },
};

图解如下：

image.png

链表和数组

链表和数组在形式上差不多，但链表相对于数组的优缺点如下：

  • 优点：
    • 内存空间不是比是连续的， 可以充分利用计算机的内存， 实现灵活的内存动态管理。
    • 在创建链表时，不需要指定链表的长度。
    • 链表在 插入、删除 数据时，时间复杂度为 O(1)，效率高于数组。
  • 缺点：
    • 链表访问任何一个位置的元素时, 都需要从头开始访问（我们这里针对于单向链表）
    • 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的问题

链表的封装

链表的操作

我们来认识下链表的操作：

  • append(data)：在链表末尾追加一个节点
  • insert(position, data)：在链表指定位置插入节点
  • remove(data)：从链表中删除值为 data 的节点
  • indexOf(data)：返回节点在链表中的索引。如果链表中没有该节点则返回-1
  • removeAt(position)：删除链表指定位置的节点
  • isEmpty()：链表是否为空链表
  • size()：返回链表包含的节点个数。与数组的length属性类似
  • toString()：用来打印链表节点顺序的方法

链表实现

初始化链表类

class linkList {
  constructor() {
    this.head = null; //头指针，指向第一个链表节点
    this.length = 0; //链表的长度
  }

  //创建链表节点的方法
  createNode(data) {
    return {
      data,
      next: null,
    };
  }

  //方便查看链表的结构，toString 方法
  toString() {
    // 1.定义两个变量
    let current = this.head;
    let res = "";

    // 2.循环获取链表中所有的元素
    while (current) {
      res += "," + current.data;
      current = current.next;
    }

    // 3.返回最终结果
    return res.slice(1);
  }
}

append

class linkList {
  //...
  append(data) {
    //1. 创建新节点
    const node = this.createNode(data);

    //2. 判断是否是空链表
    if (this.head === null) {
      // 如果是空链表，新节点直接作为头节点
      this.head = node;
    } else {
      // 如果不是空链表，先拿到头指针
      let current = this.head;
      // 从头遍历直到末尾的节点
      while (current.next) {
        current = current.next;
      }

      //找到了末尾节点，插入新节点
      current.next = node;
    }

    //3. 链表长度 + 1
    this.length++;
  }
}

上述插入节点的时候，有两种情况：

image.png

  • 链表为空时，新节点直接作为头节点
  • 链表不为空时，找到尾节点，将其的 next 指向新节点

测试 append 方法

const link = new linkList();
link.append("a");
link.append("b");
link.append("c");
console.log(link.toString()); // a,b,c

insert

insert(position, data) {
    // 1. 越界判断
    if (position < 0 || position > this.length) return false

    // 2.找到正确的位置, 并插入数据
    const newNode = this.createNode(data);
    let current = this.head
    let previous = null
    let index = 0

    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
        newNode.next = current
        this.head = newNode
    } else {
        while (index++ < position) {
            // 记录当前节点
            previous = current
            // 再遍历下一个节点
            current = current.next
        }

        // 插入节点
        newNode.next = current
        previous.next = newNode
    }

    this.length++

    return true
}

插入节点的时候，也分为两种情况：

  • 插入头节点（这个不细说）
  • 插入到中间位置

插入到中间位置时，图解如下：

image.png

把前一个节点 previous 的 next 指向新节点，新节点的 next 指向 current

验证 insert 方法

link.append("a");
link.append("b");
link.append("c");

link.insert(2, "d");
console.log(link.toString()); // a,b,d,c

remove

 remove(data) {
    // 1. current 从头节点开始，previous 记录上一个节点
    let current = this.head
    let previous = null

    // 2. 如果是删除头节点
    if (current.data === data) {
      this.head = current.next
      current.next = null
      this.length--
      return
    }

    // 3. 查找要删除的那个节点
    while (current !== null && current.data !== data) {
      previous = current
      current = current.next
    }

    // 4. 如果没找到要删除的节点
    if (current === null) {
      throw new Error("dont find the node to delete")
    }

    // 5. 找到了，删除节点
    previous.next = current.next ?? null;
    current.next = null

    // 6. 长度减一
    this.length--
}

图解如下：

image.png

验证：

const link = new linkList();
link.append("a");
link.append("b");
link.append("c");
link.insert(2, "d");

link.remove("c");
console.log(link.toString()); // a,b,d

indexOf

indexOf(data) {
    let current = this.head
    let index = 0

    // 遍历链表
    while (current) {
        if (current.data === data) {
            return index
        }

        index++
        current = current.next
    }

    // 3. 来到这个位置, 说明没有找到, 则返回-1
    return -1
}

验证：

const link = new linkList();
link.append("a");
link.append("b");
link.append("c");
link.insert(2, "d");

console.log(link.indexOf("a")); //0
console.log(link.indexOf("s")); //-1

removeAt

根据 poisition 删除元素

removeAt(position) {
    // 1. 越界判断
    if (position < 0 || position >= this.length) return null

    let current = this.head
    let previous = null
    let index = 0

    // 2. 判断是否是移除第一项
    if (position === 0) {
        this.head = current.next
    } else {
        while (index++ < position) {
            previous = current
            current = current.next
        }

        previous.next = current.next
    }

    this.length--

    // 3. 返回移除的数据
    return current.data
  }

图解和 remove 一样，这里直接验证

const link = new linkList();
link.append("a");
link.append("b");
link.append("c");
link.insert(2, "d");

link.removeAt("3");
console.log(link.toString()); // a,b,d

isEmpty

这就很简单了

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

size

size() {
    return this.length;
}

完整代码

class linkList {
  constructor() {
    this.head = null; //头指针，指向第一个链表节点
    this.length = 0; //链表的长度
  }

  //创建链表节点的方法
  createNode(data) {
    return {
      data,
      next: null,
    };
  }

  toString() {
    // 1.定义两个变量
    let current = this.head;
    let res = "";

    // 2.循环获取链表中所有的元素
    while (current) {
      res += "," + current.data;
      current = current.next;
    }

    // 3.返回最终结果
    return res.slice(1);
  }

  append(data) {
    //1. 创建新节点
    const node = this.createNode(data);

    //2. 判断是否是空链表
    if (this.head === null) {
      // 如果是空链表，新节点直接作为头节点
      this.head = node;
    } else {
      // 如果不是空链表，先拿到头指针
      let current = this.head;
      // 从头遍历直到末尾的节点
      while (current.next) {
        current = current.next;
      }

      //找到了末尾节点，插入新节点
      current.next = node;
    }

    //3. 链表长度 + 1
    this.length++;
  }

  insert(position, data) {
    // 1. 越界判断
    if (position < 0 || position > this.length) return false;

    // 2.找到正确的位置, 并插入数据
    const newNode = this.createNode(data);
    let current = this.head;
    let previous = null;
    let index = 0;

    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
      newNode.next = current;
      this.head = newNode;
    } else {
      while (index++ < position) {
        // 记录当前节点
        previous = current;
        // 再遍历下一个节点
        current = current.next;
      }

      // 插入节点
      newNode.next = current;
      previous.next = newNode;
    }

    this.length++;

    return true;
  }

  remove(data) {
    // 1. current 从头节点开始，previous 记录上一个节点
    let current = this.head;
    let previous = null;

    // 2. 如果是删除头节点
    if (current.data === data) {
      this.head = current.next;
      current.next = null;
      this.length--;
      return;
    }

    // 3. 查找要删除的那个节点
    while (current !== null && current.data !== data) {
      previous = current;
      current = current.next;
    }

    // 4. 如果没找到要删除的节点
    if (current === null) {
      throw new Error("dont find the node to delete");
    }

    // 5. 找到了，删除节点
    previous.next = current.next ?? null;
    current.next = null;

    // 6. 长度减一
    this.length--;
  }

  indexOf(data) {
    let current = this.head;
    let index = 0;

    // 遍历链表
    while (current) {
      if (current.data === data) {
        return index;
      }

      index++;
      current = current.next;
    }

    // 3. 来到这个位置, 说明没有找到, 则返回-1
    return -1;
  }

  removeAt(position) {
    // 1. 越界判断
    if (position < 0 || position >= this.length) return null;

    let current = this.head;
    let previous = null;
    let index = 0;

    // 2. 判断是否是移除第一项
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
    }

    // 4.length-1
    this.length--;

    // 5.返回移除的数据
    return current.data;
  }

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

  size() {
    return this.length;
  }
}

- Book Lists -