javascript实现链表数据结构 和 反转单链表方法

对于一个切图调接口写vue写久了的前端er来说,这还挺有趣的,也比较初级,算法大佬直接忽略吧。

1 js实现单链表

链表是什么,和数组有什么区别,这个就不展开说明了。 原生js没有链表,所以封装一个简易版的。代码如下,其实一点也不难。

function LinkedList() {
    // 封装一个Node类, 用于保存每个节点信息
    function Node(element) {
        this.element = element
        this.next = null
    }
    // 链表中的属性
    this.length = 0
    this.head = null
    
    // 链表尾部追加元素方法
    LinkedList.prototype.append = function (element) {
        // 1.根据新元素创建节点
        var newNode = new Node(element)
        // 2.判断原来链表是否为空
        if (this.head === null) { // 链表尾空
            this.head = newNode
        } else { // 链表不为空
            // 2.1.定义变量, 保存当前找到的节点
            var current = this.head
            while (current.next) {
                current = current.next
            }
            // 2.2.找到最后一项, 将其next赋值为node
            current.next = newNode
        }
        // 3.链表长度增加1
        this.length++
    }
}

那么这个方法 实现的是什么呢?

    var list = new LinkedList()
    list.append(1)
    list.append(2)
    list.append(3)
    list.append(4)
    console.log(list)

打印结果如下

再进一步展开的话

用js来解释的话,链表是个对象,有length属性以及head属性,同事head也是对象,这个对象有属性element和next

继续展开

链表就像它的名字一样,是一个链条一直链下去,知道最后一个节点的next为null。

2 实现单链表的意义

对于一个前端er来说,数组完全够用了,还有那么多好用的方法,为什么要自己封装一个这个呢?

答: 上面的不了解,没办法做面试题。 面试官问你算法了解吗? 你说知道一些,然后就问你链表的问题了,最最基本的,链表和数组有啥区别,得知道吧,其次链表有什么特点,这个也得知道啊,要不然让你反转个单链表怎么反转啊?

3 如何反转一个单链表

就拿上述的链表为例,怎么实现4-3-2-1-null?实现如下图的结果

其实看似很简单的,想法也很直观,就是把链表最后一个节点作为头节点,第一个节点的指向指null,每个节点的next指向它的前驱节点。道理都懂,代码可能就不是那么好写了。不信前端er们不要往下看,自己试着写写,所以说,面试时候让你手写的反转单链表,是有理由的。

function myReverse (linkedList) {
    // 1 拿到传参链表的head
    var head = linkedList.head
    // 2 边界判断 如果头结点是空 或者只有一个结点 那还反转个啥
    if(head === null || head.next === null) return linkedList
    // 3 用三个指针
    var current = head
    var pre = null 
    var next = null
    while(current != null) {
        next = current.next
        current.next = pre
        pre = current
        current = next
    }
    linkedList.head = pre
}

其实真的不难,主要就是一个思维的转换。这里记录一下自己的理解,反正也是写给我自己看的。
myRevese函数 接受参数 链表 ,首先拿出链表的head。之后做边界判断。
然后重点就是怎么做next指针的替换。第一点,对于链表的遍历,没有数组的for map等。链表的遍历只能人肉的一个节点一个节点的往下找。
所以 这段代码是必须的

    var current = head
    var next = null
    while(current != null) {
        next = current.next
        current = next
    }

只有这样才能保证链表遍历完成。

  • 回到myRevese函数本身,初始化阶段 current = head,pre,next都为空。
  • 第一次循环,next要先保存current的next,不先保存的话,下一步current.next指向就要改为指向它的前一个节点了
  • current.next = pre 反转嘛,当前的节点next肯定得修改,指向他的前驱节点
  • current就要变成current.next了,那变完之后,current的前一个节点就是current本身吧。所以 pre = current
  • current = next ,之前保存的变量用到了
  • 直到最后一个,current为最后一个节点的时候的那次循环,current变成了current.next,也就是current为null了,所以要重新定义链表的head指向,指向的为pre,而不是current。

4 小结

对于一个切图掉接口写vue写久了的前端er来说,这还挺有趣的,算法大佬直接忽略吧。

https://juejin.im/post/5e364ce16fb9a02fe654ba69

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论