JS数据结构之---链表

站长

2023年07月03日 15:54 · 阅读数 38

初识链表

什么是链表

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

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

图解如下：

JS数据结构之---链表

链表和数组

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

优点：
- 内存空间不是比是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
- 在创建链表时，不需要指定链表的长度。
- 链表在 插入、删除 数据时，时间复杂度为 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++;
  }
}

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

JS数据结构之---链表

链表为空时，新节点直接作为头节点
链表不为空时，找到尾节点，将其的 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
}

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

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

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

JS数据结构之---链表

把前一个节点 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--
}

图解如下：

JS数据结构之---链表

验证：

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
  }
}

结语

以上内容如有错误，欢迎留言指出，一起进步💪，也欢迎大家一起讨论下一期说 JS数据结构---双向链表

转载自:https://juejin.cn/post/7231097076061831228