JS 实现单链表

Souleigh ✨
• 阅读 1431

要存储多个元素,数组(或列表)可能是最常用的数据结构。但这种数据结构有一个缺点:(在大多数语言中)数据的大小是固定的,从数组的起点或中间插入或移除项的成本很高。   链表存储有序的集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。   相对于传统的数组,链表的一个好处是,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。   举个例子,我们玩寻宝游戏,你有一条线索,这条线索是指向寻找下一条线索的地点的指针。你沿着这条链接去下一个地点,得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法,就是从起点(第一条线索)顺着列表去寻找。   让我们用JS实现最简单的单链表:

function LinkedList() {

    // Node辅助类,表示要加入列表的项,element是即将添加到列表的值,next是指向列表中下一个节点项的指针
    let Node = function (element) {
        this.element = element
        this.next = null
    }

    let length = 0
    let head = null

    // 向链表尾部追加元素
    this.append = function (element) {
        let node = new Node(element)
        let current
        if (head === null) { // 列表中第一个节点
            head = node
        } else {
            current = head
            while (current.next) {
                current = current.next // 找到最后一项,是null
            }
            current.next = node // 给最后一项赋值
        }
        length++ // 更新列表的长度
    }

    // 从链表中移除指定位置元素
    this.removeAt = function (position) {
        if (position > -1 && position < length) { // 值没有越界
            let current = head
            let previous, index = 0
            if (position === 0) { //  移除第一项
                head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next // 将previous与current的下一项连接起来,跳过current,从而移除
            }
            length-- // 更新列表的长度
            return current.element
        } else {
            return null
        }
    }

    // 在链表任意位置插入一个元素
    this.insert = function (position, element) {
        if (position >= 0 && position <= length) { // 检查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0
            if (position === 0) { // 在第一个位置添加
                node.next = current
                head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current // 在previous与current的下一项之间插入node
                previous.next = node
            }
            length++
            return true
        } else {
            return false
        }
    }

    // 把链表内的值转换成一个字符串
    this.toString = function () {
        let current = head,
            string = ''
        while (current) {
            string += current.element + ' '
            current = current.next
        }
        return string
    }

    // 在链表中查找元素并返回索引值
    this.indexOf = function (element) {
        let current = head,
            index = 0
        while (current) {
            if (element === current.element) {
                return index
            }
            index++
            current = current.next
        }
        return -1
    }

    // 从链表中移除指定元素
    this.remove = function (element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }

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

    this.size = function () {
        return length
    }

    this.getHead = function () {
        return head
    }
}
let list = new LinkedList()
list.append(1)
list.append(2)
console.log(list.toString()) // 1 2
list.insert(0, 'hello')
list.insert(1, 'world')
console.log(list.toString()) // hello world 1 2
list.remove(1)
list.remove(2)
console.log(list.toString()) // hello world 

单链表有一个变种 - 循环链表,最后一个元素指向下一个元素的指针,不是引用null,而是指向第一个元素,只需要修改下最后的next指向为head即可。

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Stella981 Stella981
2年前
Redis的列表(List)类型
列表类型(List)可以存储一个有序的字符串列表,常用的操作就是向列表两端添加元素,或者获取列表中某一个片段。列表类型内部使用双向链表(doublelinkedlist)实现的,所以向列表两端添加或删除元素的速度非常快,越是接近两端的元素就越快,但是,也有弊端,就是通过索引访问元素的速度比较慢。因为使用了双向链表实现存储的,所以在命令上也有
Wesley13 Wesley13
2年前
Java数据结构和算法(四)
日常开发中,数组和集合使用的很多,而数组的无序插入和删除效率都是偏低的,这点在学习ArrayList源码的时候就知道了,因为需要把要插入索引后面的所以元素全部后移一位。而本文会详细讲解链表,可以解决数组的部分问题,相比数组的大小不可更改,链表更加灵活,在学习LinkedList源码对链表有了一个大致的了解。ArrayList和Linked
Wesley13 Wesley13
2年前
Java HashSet集合的子类LinkedHashSet集合
说明HashSet保证元素的唯一性,可是元素存放进去是没有顺序的。在HashSet下面有一个子类java.util.LinkedHashSet,它是链表哈希表(数组链表或者数组红黑树)组合的一个数据结构。即相对HashSet而言,多了一个链表结构。多了的那条链表,用来记录元素的存储顺序,保证元素有序举例Hash
Stella981 Stella981
2年前
HashMap 的底层实现原理
HashMap是一个用于存储KeyValue键值对的集合,每一个键值对也叫做Entry。这些个Entry分散存储在一个数组当中,这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。 !(https://oscimg.oschina.net/oscnet/8495d30fe00a2865dd74088d2
Wesley13 Wesley13
2年前
D1
1\.数据结构  1.1线性结构  (1)最常用的数据结构,特点是数据元素之间存在一对一的线性关系  (2)有两种不同的存储结构,即顺序存储结构和链式存储结构    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
菜园前端 菜园前端
1年前
什么是链表?
原文链接:什么是链表?链表是有序的数据结构,链表中的每个部分称为节点。可以首、尾、中间进行数据存取,链表的元素在内存中不必是连续的空间,每个节点通过next指针指向下一个节点。优点链表的添加和删除不会导致其余元素位移。缺点无法根据索引快速定位元素。数组和链
京东云开发者 京东云开发者
9个月前
分布式系统的主键生成方案对比 | 京东云技术团队
UUID​UUID(通用唯一识别码)是由32个十六进制数组成的无序字符串,通过一定的算法计算出来。为了保证其唯一性,UUID规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。
贾蓁 贾蓁
5个月前
2023全新GO工程师面试总攻略,助力快速斩获offer
2023全新GO工程师面试总攻略,助力快速斩获offerdownload》http://quangneng.com/2319/常见的数据结构包括:数组(Array):存储固定大小的元素序列,在内存中连续存储。链表(LinkedList):元素以节点形式存储
稚然 稚然
4个月前
物联网入门C语言数据结构与算法(全套课程精讲手把手教会)
//下仔のke:https://yeziit.cn/14679/数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。数据结构可以分为线性结构和非线性结构。常见的线性结构包括数组、队列、链表等,常见的非线性结构包括树形结构