写文章
  1. 码农之家首页
  2. 前端教程

JS数据结构之—链表

我心飞翔 • • 前端教程 • 阅读 37

初识链表

什么是链表

链表是由 链表节点 + 指针变量 组成的一种数据结构，它包含 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 作者：Jolyne_

赞 (0)
我心飞翔我心飞翔
0 0
上一篇 2023年5月10日 上午10:05
下一篇 2023年5月10日 上午10:16

相关推荐

发表回复

登录后才能评论