JS数据结构第二篇---链表

2023-01-09 13:46:54

一、什么是链表　

链表是一种链式存储的线性表，是由一组节点组成的集合，每一个节点都存储了下一个节点的地址；指向另一个节点的引用叫链；和数组中的元素内存地址是连续的相比，链表中的所有元素的内存地址不一定是连续的。结构模拟如图：

一般来说，说到链表，就要提下数组，一般链表都是和数组进行对比。

在很多编程语言中，数组的长度时固定的，所以数组中的增加和删除比较麻烦，需要频繁的移动数组中的其他元素。

然而，JavaScript中的数组并不存在上述问题，JS中的数组相对其他语言使用上更方便，因为JS中的数组本质是一个类似数组的对象，这就使得JS的数组虽然使用更方便，但比其他语言(C++、Java、C#)的数组效率要低。

所以，在实际应用中如果发现数组很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

二、链表的设计

为了对链表更好的使用，我们设计了类LinkedList, 对链表中节点的增删改查方法进行了封装。结构如图：

其中size和head为LinkedList构造函数私有属性，size记录链表中有多少个节点，head指向链表的头结点。

根据需要对外暴露了以下方法（可以根据需要自定义其他方法）：

单向LinkedList完整设计代码：

/**

 * 自定义链表：对外公开的方法有

 * append(element) 在链表最后追加节点

 * insert(index, element) 根据索引index, 在索引位置插入节点

 * remove(element)  删除节点

 * removeAt(index)  删除指定索引节点

 * removeAll(element) 删除所有匹配的节点

 * set(index, element) 根据索引，修改对应索引的节点值

 * get(index)  根据索引获取节点信息

 * indexOf(element) 获取某个节点的索引位置

 * clear()  清空所有节点

 * length()   返回节点长度

 * print() 打印所有节点信息

 * toString() 打印所有节点信息，同print

 * */

const LinkedList = function(){

    let head = null;

    let size = 0;   //记录链表元素个数

    //Node模型

    function LinkNode(element, next){

        this.element = element;

        this.next = next;

    }

    //元素越界检查, 越界抛出异常

    function outOfBounds(index){

        if (index < 0 || index >= size){

            throw("抱歉，目标位置不存在！");

        }

    }

    //根据索引，获取目标对象

    function node(index){

        outOfBounds(index);

        let obj = head;

        for (let i = 0; i < index; i++){

            obj = obj.next;

        }

        return obj;

    }

    //新增一个元素

     function append(element){

        if (size == 0){

            head = new LinkNode(element, null);

        }

        else{

            let obj = node(size-1);

            obj.next = new LinkNode(element, null);

        }

         size++;

    }

    //插入一个元素

     function insert(index, element){

        if (index == 0){

            head = new LinkNode(element, head);

        }

        else{

            let obj = node(index-1);

            obj.next = new LinkNode(element, obj.next);

        }

         size++;

    }

    //修改元素

    function set(index, element){

        let obj = node(index);

        obj.element = element;

    }

    //根据值移除节点元素

    function remove(element){

        if (size < 1) return null;

        if (head.element == element){

            head = head.next;

            size--;

            return element;

        }

        else{

            let temp = head;

            while(temp.next){

                if (temp.next.element == element){

                    temp.next = temp.next.next;

                    size--;

                    return element;

                }

                else{

                    temp = temp.next;

                }

            }

        }

        return null;

    }

    //根据索引移除节点

     function removeAt(index){

         outOfBounds(index);

         let element = null;

         if (index == 0){

             element = head.element;

             head = head.next;

         }

         else{

             let prev = node(index-1);

             element = prev.next.element;

             prev.next = prev.next.next;

         }

         size--;

        return element;

    }

    //移除链表里面的所有匹配值element的元素

     function removeAll(element){

        let virHead = new LinkNode(null, head); //创建一个虚拟头结点，head为次节点

         let tempNode = virHead, ele = null;

         while(tempNode.next){

             if (tempNode.next.element == element){

                 tempNode.next = tempNode.next.next;

                 size--;

                 ele = element;

             }

             else{

                tempNode = tempNode.next;

             }

         }

         //重新赋值

         head = virHead.next;

        return ele;

    }

    //获取某个元素

    function get(index){

        return node(index).element;

    }

    //获取元素索引

    function indexOf(element){

        let obj = head, index = -1;

        for (let i = 0; i < size; i++){

            if (obj.element == element){

                index = i;

                break;

            }

            obj = obj.next;

        }

        return index;

    }

    //清除所有元素

    function clear(){

        head = null;

        size = 0;

    }

    //属性转字符串

    function getObjString(obj){

        let str = "";

        if (obj instanceof Array){

            str += "[";

            for (let i = 0; i < obj.length; i++){

                str += getObjString(obj[i]);

            }

            str = str.substring(0, str.length - 2);

            str += "], "

        }

        else if (obj instanceof Object){

            str += "{";

            for (var key in obj){

                let item = obj[key];

                str += "\"" + key + "\": " + getObjString(item);

            }

            str = str.substring(0, str.length-2);

            str += "}, "

        }

        else if (typeof obj == "string"){

            str += "\"" + obj + "\"" + ", ";

        }

        else{

            str += obj + ", ";

        }

        return str;

    }

    function toString(){

        let str = "", obj = head;

        for (let i = 0; i < size; i++){

            str += getObjString(obj.element);

            obj = obj.next;

        }

        if (str.length > 0) str = str.substring(0, str.length -2);

        return str;

    }

    //打印所有元素

    function print(){

        console.log(this.toString())

    }

    //对外公开方法

    this.append = append;

    this.insert = insert;

    this.remove = remove;

    this.removeAt = removeAt;

    this.removeAll = removeAll;

    this.set = set;

    this.get = get;

    this.indexOf = indexOf;

    this.length = function(){

        return size;

    }

    this.clear = clear;

    this.print = print;

    this.toString = toString;

}

////测试

// let obj = new LinkedList();

// let obj1 = { title: "全明星比赛", stores: [{name: "张飞vs岳飞", store: "2:3"}, { name: "关羽vs秦琼", store: "5:5"}]};

//

// obj.append(99);

// obj.append("hello")

// obj.append(true)

// obj.insert(3, obj1);

// obj.insert(0, [12, false, "Good", 81]);

// obj.print();

// console.log("obj1.index: ", obj.indexOf(obj1));

// obj.remove(0);

// obj.removeAll(obj1);

// obj.print();

////测试2

console.log("\n\n......test2.....")

var obj2 = new LinkedList();

obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false);

obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);

obj2.print();

obj2.removeAll(8); //删除所有8

obj2.print();

另外，可以在LinkedList中增加一个虚拟节点，即在头结点之前增加一个节点，一直保留，结构如图：

这里代码就不提供了，在上一份链表代码中的removeAll（删除链表中指定值的所有节点）方法中有用到虚拟头结点，下面的练习题中也有应用到虚拟头结点，应用场景还是蛮多的。

三、链表练习题

推荐一个神奇的网站，可以以动画的方式演示各种数据结构增删改查变化，先来张展示链表的增删效果图看看：

网址：https://visualgo.net/zh

接下来做几个链表的练习题，题目来自力扣，可以先自己先做一下，看看自己得分，再对比下官方提供的代码demo

3.1 删除排序链表中的重复元素_第83题

参考demo：

/**

 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

 示例 1:

 输入: 1->1->2

 输出: 1->2

 示例 2:

 输入: 1->1->2->3->3

 输出: 1->2->3

 力扣得分：

 执行用时 :108 ms, 在所有 JavaScript 提交中击败77.12%的用户

 内存消耗 :37.4 MB, 在所有 JavaScript 提交中击败了5.03%的用户

 */

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

function ListNode(val){

    this.val = val;

    this.next = null;

}

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var deleteDuplicates = function(head) {

    let virHead = new ListNode(0); //增加一个虚拟节点

    virHead.next = head;

    let temp = virHead, obj = {};

    while(temp.next){

        if (obj[temp.next.val]){ //表示为重复节点，删除这个节点

            temp.next = temp.next.next;

        }

        else{ //

            obj[temp.next.val] = 1;

            temp = temp.next;

        }

    }

    return virHead.next;

}

//测试

var obj = new ListNode(1);

obj.next = new ListNode(2);

obj.next.next = new ListNode(1);

obj.next.next.next = new ListNode(3);

obj.next.next.next.next = new ListNode(1);

obj.next.next.next.next.next = new ListNode(2);

obj.next.next.next.next.next.next = new ListNode(3);

console.log(obj);

console.log(".>>>>>>删除重复节点：")

console.log(deleteDuplicates(obj));

3.2 判断是否环形链表_第141题

参考demo：

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/**

 * @param {ListNode} head

 * @return {boolean}

 */

var hasCycle = function(head) {

    //快慢指针，快指针每次走两步，慢指针每次走一步

    let obj1 = head, obj2 = head; //obj1快指针，obj2为慢指针

    while(obj2){

      obj2 = obj2.next;

      if (obj1){

          obj1 = obj1.next;

      }

      if (obj1){

          obj1 = obj1.next;

      }

      if (obj2 == obj1 && obj1) return true;

    }

    return false;

};

function ListNode(val){

    this.val = val;

    this.next = null;

}

//测试

console.log(">>>>>>环形链表》》测试》》")

let node1 = new ListNode(1);

let node2 = new ListNode(2);

let node3 = new ListNode(3);

let node4 = new ListNode(4);

node1.next = node2;

node2.next = node3;

node3.next = node4;

node4.next = node2;

let res = hasCycle(node1);

console.log("res: ", res);

3.3 移除链表中给定值的所有元素_第203题

参考demo1：

/**

 删除链表中等于给定值 val 的所有节点。

 示例:

 输入: 1->2->6->3->4->5->6, val = 6

 输出: 1->2->3->4->5

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/**

 * 在力扣中得分：耗时160ms, 打败Javascript中17.87%； 内存消耗37.5M, 打败JavaScript中24.79% , 更优化的写法是？

 * @param {ListNode} head

 * @param {number} val

 * @return {ListNode}

 */

var removeElements = function(head, val) {

    let newHead = null, curNode = null;

    while(head){

        if (head.val != val){

            if (curNode){

                curNode.next = new ListNode(head.val);

                curNode = curNode.next;

            }

            else{

                curNode = new ListNode(head.val);

                newHead = curNode;

            }

        }

        head = head.next;

    }

    return newHead;

}

function ListNode(val){

    this.val = val;

    this.next = null;

}

//测试

console.log(">>>>移除链表元素测试》》》")

var node = new ListNode(1);

node.next = new ListNode(2);

// node.next.next = new ListNode(5);

// node.next.next.next = new ListNode(4);

// node.next.next.next.next = new ListNode(6);

// node.next.next.next.next.next = new ListNode(8);

// node.next.next.next.next.next.next = new ListNode(4);

// var newNode = removeElements(node, 6);

// console.log(newNode);

var newNode = removeElements(node, 2);

console.log(newNode);

参考demo2：

/**

 删除链表中等于给定值 val 的所有节点。

 示例:

 输入: 1->2->6->3->4->5->6, val = 6

 输出: 1->2->3->4->5

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

/** 第二种写法

 * 在力扣中得分：耗时112ms, 打败Javascript中90.28%； 内存消耗37.5M, 打败JavaScript中24.79%

 * @param {ListNode} head

 * @param {number} val

 * @return {ListNode}

 */

var removeElements = function(head, val) {

    if (!head) return head;

    let newHead = new ListNode(-1);

    newHead.next = head; //把head作为newHead的下一个

    let tmpNode = newHead;

    while(tmpNode.next){

        if (tmpNode.next.val == val){

            tmpNode.next = tmpNode.next.next;

        }

        else{

            tmpNode = tmpNode.next;

        }

    }

    return newHead.next; //返回newHead的下一个，就是我们想要的结果

}

function ListNode(val){

    this.val = val;

    this.next = null;

}

//测试

console.log(">>>>移除链表元素测试》》》")

var node = new ListNode(1);

node.next = new ListNode(2);

// node.next.next = new ListNode(5);

// node.next.next.next = new ListNode(4);

// node.next.next.next.next = new ListNode(6);

// node.next.next.next.next.next = new ListNode(8);

// node.next.next.next.next.next.next = new ListNode(4);

// var newNode = removeElements(node, 6);

// console.log(newNode);

var newNode = removeElements(node, 2);

console.log(newNode);

3.4 反转链表_第206题

参考demo1_迭代方式：

/*

 反转一个单链表。使用迭代方式实现

 示例:

 输入: 1->2->3->4->5->NULL

 输出: 5->4->3->2->1->NULL

 力扣中测试执行用时 : 76 ms, 在所有 JavaScript 提交中击败了97.74%的用户

 内存消耗 :36 MB, 在所有 JavaScript 提交中击败了6.92%的用户

 * */

function ListNode(val){

    this.val = val;

    this.next = null;

}

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var reverseList = function(head) {

    let newHead = null;

    while(head){

        let tmpNode= newHead;

        newHead = new ListNode(head.val);

        newHead.next = tmpNode;

        head = head.next;

    }

    return newHead;

}

////测试

var node = new ListNode(9);

node.next = new ListNode(99);

node.next.next = new ListNode(999);

node.next.next.next = new ListNode(33);

console.log("原链表：", node);

console.log(".....反转....")

console.log(reverseList(node))

参考demo2_递归方式：

/*

 反转一个单链表。 使用递归方式实现

 示例:

 输入: 1->2->3->4->5->NULL

 输出: 5->4->3->2->1->NULL

 力扣测试得分：

 执行用时 :80 ms, 在所有 JavaScript 提交中击败了95.56%的用户

 内存消耗 :36.3 MB, 在所有 JavaScript 提交中击败了5.03%的用户

* */

function ListNode(val){

    this.val = val;

    this.next = null;

}

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var reverseList = function(head) {

    return getNewNode(head).first;

}

/**

 * 递归，好绕啊：

 * 推演：加入2->3->4->5 递归：

 * @param node

 */

function getNewNode(node){

    if (!node) return {first: null, cur: null };

    var cur = new ListNode(node.val);

    ////一直递归递归，拿到原链表最后一个元素开始返回

    var res = getNewNode(node.next);

    if (res.first) {

        res.cur.next = cur; //设置

        return {

            first: res.first, //反转链表的第一个元素

            cur: cur

        }

    }

    console.log("666_node.val: ", node.val);

    /**

     * 原链表最后一个元素会执行到这里，最后一个元素作为反转链表的第一个元素返回

     */

    return {

        first: cur, //反转链表的第一个元素

        cur: cur    //每次递归返回的一个元素

    };

}

//测试

var node = new ListNode(2);

node.next = new ListNode(3);

node.next.next = new ListNode(4);

node.next.next.next = new ListNode(5);

console.log("\n\n*****原链表****")

console.log(node);

console.log("......反转.....")

console.log(reverseList(node));

3.5 查找链表的中间结点_第876题

参考代码demo1_迭代方式：

/**

 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

 如果有两个中间结点，则返回第二个中间结点。

 示例 1：

 输入：[1,2,3,4,5]

 输出：此列表中的结点 3 (序列化形式：[3,4,5])

 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

 注意，我们返回了一个 ListNode 类型的对象 ans，这样：

 ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

 示例 2：

 输入：[1,2,3,4,5,6]

 输出：此列表中的结点 4 (序列化形式：[4,5,6])

 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

  

 提示：

 给定链表的结点数介于 1 和 100 之间。

 力扣得分：

 执行用时 :108 ms, 在所有 JavaScript 提交中击败了19.44%的用户

 内存消耗 :33.6 MB, 在所有 JavaScript 提交中击败了74.60%的用户

 */

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

function ListNode(val){

    this.val = val;

    this.next = null;

}

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var middleNode = function(head) {

    if (!head) return head;

    let arr = [];

    while(head){

        arr.push(head);

        head = head.next;

    }

    let len = arr.length;

    return len % 2 == 0 ? arr[len/2] : arr[(len-1)/2];

};

//测试

var obj = new ListNode(1), temp = obj;

for (let i = 0; i < 6; i++){

    temp.next = new ListNode(2+i);

    temp = temp.next;

}

console.log(obj);

console.log("获取中间节点：")

console.log(middleNode(obj));

参考代码demo2_快慢指针：

/**

 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

 如果有两个中间结点，则返回第二个中间结点。

 示例 1：

 输入：[1,2,3,4,5]

 输出：此列表中的结点 3 (序列化形式：[3,4,5])

 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

 注意，我们返回了一个 ListNode 类型的对象 ans，这样：

 ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

 示例 2：

 输入：[1,2,3,4,5,6]

 输出：此列表中的结点 4 (序列化形式：[4,5,6])

 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

  

 提示：

 给定链表的结点数介于 1 和 100 之间。

 力扣得分：

 执行用时 :120 ms, 在所有 JavaScript 提交中击败了12.22%的用户

 内存消耗 :34.1 MB, 在所有 JavaScript 提交中击败了11.11%的用户

 官方答案，官方这个确实简洁：

 let slow = fast = head;

 while (fast && fast.next) {

        slow = slow.next;

        fast = fast.next.next;

    }

 return slow;

 官方力扣得分：

 执行用时 :64 ms, 在所有 JavaScript 提交中击败了99.44%的用户

 内存消耗 :34.1 MB, 在所有 JavaScript 提交中击败了11.11%的用户

 */

/**

 * Definition for singly-linked list.

 * function ListNode(val) {

 *     this.val = val;

 *     this.next = null;

 * }

 */

function ListNode(val){

    this.val = val;

    this.next = null;

}

/** 用快慢指针来处理下

 * @param {ListNode} head

 * @return {ListNode}

 */

var middleNode = function(head) {

    // let slow = head, fast = head;

    // while(slow){

    //     if (fast){

    //         fast = fast.next;

    //         if (fast){

    //             fast = fast.next;

    //         }

    //         else{

    //             return slow;

    //         }

    //     }

    //     else{

    //         return slow;

    //     }

    //     slow = slow.next;

    // }

    // return head;

    //官方答案：简洁明了

    let slow = fast = head;

    while (fast && fast.next) {

        slow = slow.next;

        fast = fast.next.next;

    }

    return slow;

};

//测试

var obj = new ListNode(1), temp = obj;

for (let i = 0; i < 6; i++){

    temp.next = new ListNode(2+i);

    temp = temp.next;

}

console.log(obj);

console.log("获取中间节点：")

console.log(middleNode(obj));

obj = new ListNode(90), temp = obj;

for (let i = 0; i < 5; i++){

    temp.next = new ListNode(91+i);

    temp = temp.next;

}

console.log(obj);

console.log("获取中间节点：")

console.log(middleNode(obj));

参考Demo地址：https://github.com/xiaotanit/Tan_DataStruct

码农公寓

相关文章