Skip to content

链表结构

· 10 min

链表也是存储元素的集合，数组在内存中是一段 连续 的空间，但是链表在内存中是 非连续 的空间。

image-20250218110039706

链表是由一个一个节点组成。

🙋：链表中每个节点是如何找到下一个节点的？

int[] arr = {1, 2, 3};
arr[2];

在链表中，每个节点就由两个部分组成：

  1. 存储具体值
  2. 下一个节点的内存地址

image-20250218135510975

正因为这个特征，链表在查询、新增、删除方面刚好和数组相反。

并且数组和链表对应的是在内存中真实的存储数据的两种结构方式（物理结构）。

链表常见的形式

  1. 单向链表：每个节点包含下一个节点的地址
  2. 双向链表：每个节点会包含上一个节点和下一个节点的地址

单向链表#

单向链表（Singly Linked List）每个元素都包含 两个部分：数据部分 和 指向下一个元素的指针（通常称为next）。链表的每个节点都包含数据并且指向下一个节点，这样形成了一个链式的结构，方便在任意位置进行插入和删除操作。

单向链表的特点

  1. 线性结构：数据元素是线性排列的，但与数组不同的是，链表的元素并不一定在内存中连续存储。

  2. 动态大小：链表的大小在运行时可以动态变化，元素的插入和删除不会像数组一样造成内存的重新分配。

  3. 插入和删除高效：在已知节点的情况下，插入和删除元素的时间复杂度为 O(1)，但如果要访问某个节点时，需要遍历链表。

// 首先需要一个节点
class Node {
  // 接收该节点要存储的数据
  constructor(data) {
    this.data = data // 当前节点存储的数据
    this.next = null // 下一个节点的地址
  }
}


// 单向链表类
class LinkedList {
  constructor() {
    this.head = null // 链表的头节点
    this.size = 0 // 链表的长度
  }


  // 打印链表数据
  print() {
    // 无外乎就是遍历所有的节点，通过 next 就可以找到下一个节点
    let current = this.head // 一开始从头节点开始
    let result = [] // 存放所有节点的值
    while (current) {
      result.push(current.data)
      current = current.next
    }
    // 出了 while 之后，说明遍历节点结束
    console.log(result.join(' -> ') + ' -> null')
  }
}


module.exports = {
  Node,
  LinkedList,
}
const { Node, LinkedList } = require('./LinkedList.js')
const ll = new LinkedList() // 拿到一个链表的实例对象
// 有3个节点
const n1 = new Node(1)
const n2 = new Node(2)
const n3 = new Node(3)
n1.next = n2
n2.next = n3
ll.head = n1

链表的新增

  1. 新增节点到最后
// 新增一个指定数据的节点
// 放到当前链表的最后
add(data){
  // 首先需要生成一个节点
  const newNode = new Node(data);
  // 需要判断新增的这个节点是不是头节点
  if(!this.head){
    // 如果进入此分支，说明当前的单向链表是空的
    // 当前这个节点应该是头节点
    this.head = newNode;
  } else {
    // 说明当前的单向链表不是空的
    // 将节点添加到最后
    let current = this.head;
    while(current.next){
      current = current.next;
    }
    // 退出上面 while 循环的时候，current 是最后一个节点
    current.next = newNode;
  }
  this.size++;
}
  1. 新增节点放到指定的位置
// 接收两个参数
// 1. 数据
// 2. 添加到哪个位置
addAt(data, index){
  // 安全性处理
  if(index < 0 || index > this.size){
    throw new Error("索引值无效");
  }


  const newNode = new Node(data);// 新创建一个节点
  let current = this.head; // 一开始 current 指向头节点
  let counter = 0; // 计数器，对链表节点进行计数，类似于数组的下标


  // 下面就是插入的操作。插入仍然是分为是否是头节点位置
  if(index === 0){
    // 在头部插入
    // 插入的新节点会成为新的头节点
    newNode.next = this.head;
    this.head = newNode; // 更新头节点的值
  } else {
    // 链表后面部分插入，需要遍历到指定的位置
    while(current){
      if(counter === index - 1){
        // 做插入操作
        newNode.next = current.next;
        current.next = newNode;
        break;
      }
      current = current.next;
      counter++;
    }
  }
  this.size++;
}

链表的删除

  1. 删除指定数据的节点

    // 接收1个参数
    // 要删除的节点对应数据是什么
    remove(data){
      let current = this.head; // 一开始指向头节点
      let previous = null; // 暂存上一个节点
    

      while(current !== null){
        if(current.data === data){
          // 说明当前的这个 current 所对应的节点是要删除的节点
          if(previous === null){
            // 说明删除的节点是头节点
            this.head = current.next;
          } else {
            // 不是头节点
            previous.next = current.next;
          }
          this.size--;
          return current.data;
        }
        previous = current; // 先暂存该节点
        current = current.next; // 跳入下一个节点
      }
    }

  2. 删除指定位置的节点

    // 接收1个参数，指定的位置
    removeAt(index){
      if(index < 0 || index >= this.size){
        throw new Error("索引值无效");
      }
      let current = this.head; // 一开始指向头节点
      let previous = null; // 暂存上一个节点
      if(index === 0){
        // 说明要删除的是头节点
        this.head = current.next;
      } else {
        // 说明不是头节点，需要遍历到指定的位置
        for(let i = 0; i < index; i++){
          previous = current;
          current = current.next;
        }
        // 跳出 for 循环的时候，current 是当前要删除的这个节点
        // previous 是当前要删除的节点的前一个节点
        previous.next = current.next;
      }
      this.size--;
      return current.data;
    }

链表的反转

reverse(){
  if(!this.head) return; // 如果是空链表，直接返回


  // 没有进入上面的 if，说明链表有东西，进行反转操作
  let current = this.head;
  let previous = null; // 保存上一个节点
  let next = null; // 保存下一个节点


  while(current !== null){
    // 进行反转操作
    next = current.next; // 将当前节点原本的下一个节点暂存
    current.next = previous;
    previous = current;
    current = next;
  }


  // 重置头节点
  this.head = previous;
}
1 --> 2 --> 3
3 --> 2 --> 1 --> null
current: null
previous: 3
next: null
this.head = 3

链表的置换

交换链表里面的两个节点

// 接收参数
// 要交换的两个节点的下标，下标是从 0 开始
swap(index1, index2){
  if(index1 === index2) return false; // 如果索引相等，不需要交换
  if(index1 < 0 || index1 >= this.size || index2 < 0 || index2 >= this.size){
    throw new Error("索引无效");
  }


  // 代码走到这一步，说明索引是没有问题的
  // 开始进行交换
  let current = this.head; // 一开始指向头节点
  let counter = 0; // 计数器，靠它找到对应下标的节点
  let node1 = null; // 存储index1对应的节点
  let node2 = null; // 存储 index2 对应的节点


  // 这个while循环主要是寻找节点
  while(current !== null){
    if(counter === index1) node1 = current;
    if(counter === index2) node2 = current;
    if(node1 && node2) break; // 两个节点都找到了，就退出
    current = current.next;
    counter++;
  }


  if(node1 && node2){
    // 交换两个节点的数据
    let temp = node1.data;
    node1.data = node2.data;
    node2.data = temp;
    return true;
  }


  return false;
}

React 从 16 版本开始，引入了一个 Fiber 的架构，Fiber就是一个节点，所有的 Fiber 节点就是使用单向链表连接起来的。

function FiberNode(tag, pendingProps, key, mode) {
  // ...


  // 周围的 Fiber Node 通过链表的形式进行关联
  this.return = null // 指向父节点
  this.child = null // 指向子节点
  this.sibling = null // 指向兄弟节点
  this.index = 0


  // ...
}

假设有如下的 html 结构：

<div>
  <p></p>
  <ul>
    <li></li>
    <li></li>
    <li></li>
  </ul>
</div>

对应的 Fiber 数链表结构如下图：

image-20250218142656519

-EOF-