javaScript数据结构与算法之单向链表的实现

• 引言
• 希望实现的内容
• 链表原理
• 节点
• 链表创建
• • 初始化方法（构造方法）
  • push和pop
  • 查询和遍历
  • 插入、修改和删除
• javaScript完整代码
• typeScript完整代码
• 结语

引言

最近在学习javaScript的数据结构，链表和javaScript中的数组可以说是起到互补关系，有些复杂的数据结构适合用数组实现（比如栈），而有些更适合用链表来实现（比如队列），今天就来研究在javaScript中实现单向链表

希望实现的内容

单向链表的创建，初始化，基本的增删改查。同时因为本人工作的项目使用到了ts，因此希望实现javaScript和typeScript两个版本，考虑到兼容问题，我的代码里没有使用es6的class语法，而是用function去构造类对象，而ts版本则直接使用了es6的class语法

链表原理

我自认为不是什么太专业的人士，很多文章也都提到过链表的原理，这里我只简答说下。相较于js的数组，链表从存储方式上就有着根本的不同，数组是在堆内开辟了一块连续的内存，也就是在new Array或者[]这个操作时进行。而链表则是离散的内存，每个存储的值已节点的形式存在，通过下一个节点地址指向的方式将这些离散的节点链接在一起就是所谓的链表。

节点

要实现链表，首先需要有链表的节点node，单向链表的节点包含两部分内容，节点值（value）以及指向下一个节点的地址（value），也可以叫做指针，不过js不需要我们操作指针，这里就不多说了，下面是实现node的代码，这里多说一句，Object.create(null)可以创建一个不含有原型链的对象，这里不使用也无所谓，只是个人觉得node不会使用object对象原型上的方法所以这样创建的

// 单向链表节点
function SingleNode(value) {
    let node = Object.create(null);
    node.value = value;  // 节点值
    node.next = null;  // 下一个节点
    return node;
}

链表创建

单向链表实际上我们只需要记住他最后加入的节点，也可以视为当前链表的头（head）。我这里还记录了下链表的长度，并在SingleLinkList原型上添加length方法在外部使用时可以返回链表的长度

function SingleLinkList() {
    this.head = null; // 头部节点
    this.len = 0; // 链表长度
    /**
     * 获取当前链表的长度
     * @returns 长度
     */
    SingleLinkList.prototype.length = function () {
        return this.len;
    }
}

接下来就是给链表添加各种方法，首先先完成初始化方法
注意，单向链表因为只有一个head，节点遵循后进先出的原则，所以只支持对链表头部的操作（相当于对数组的尾部进行操作push、pop等，不支持shift、unshift的操作，这些方法我准备在双向链表时再去实现）

初始化方法（构造方法）

这里是希望能像let array = new Array(1)这样，在new SingleLinkList()时给链表进行初始化，也就是构造方法
目前我实现了三种情况的初始化：没有参数、一个参数、多个参数，这里的参数支持数组、字符串、数字、对象等类型
利用arguments判断参数个数，并分别处理
我在SingleLinkList里添加了两个方法push和insert，为了区别后面挂在SingleLinkList原型上的方法，这里取名为intPush和InitInsert，一个来实现节点创建并添加到head，一个则是区别数组和其他类型并负责循环添加，代码如下：

// 初始化方法里的添加方法
function initPush(param) {
    let node = new SingleNode(param);
    if (this.head) {
        node.next = this.head;
    }
    this.head = node;
    this.len++;
}
// 构造方法的添加方法
function initInsert(param) {
    if (Object.prototype.toString.call(param) === "[object Array]") {
        for (let i = 0; i < param.length; i++) {
            initPush.call(this, param[i]);
        }
    } else {
        initPush.call(this, param);
    }
}

然后添加了自执行的init方法

// 初始化
(function init(params) {
    switch (params.length) {
        case 0:
            break;
        // 节点数组或单个节点
        case 1:
            initInsert.call(this, params);
            break;
        // 可变长参数，多个节点
        default:
            for (let i = 0; i < params.length; i++) {
                initInsert.call(this, params[i]);
            }
            break;
    }
}.bind(this, arguments))();

这样我们的单向链表就具备了初始化的能力，并且可以支持一下方式：
new SingleLinkList(1);
new SingleLinkList(1, 2, 3);
new SingleLinkList([1, 2, 3]);
new SingleLinkList(1, 2, [3, 4, 5]);

push和pop

先添加push和pop两个基本方法，这两个方法都很简单，使用方法也和数组类似，是在链表的头部添加一个节点和返回当前头部节点，push方法需要判断下head是否为空，如果为空则直接添加到head上，如果不为空则将node.next指向当前head，然后将head指向新创建的node，此外因为加了长度，也需要处理长度的变化
上代码

/**
 * 向链表添加一个节点，并放到头部
 * @param {*} value 节点值
 */
SingleLinkList.prototype.push = function (value) {
    let node = new SingleNode(value);
    if (this.head) {
        node.next = this.head;
    }
    this.head = node;
    this.len++;
}
/**
 * 弹出最后加入的节点，链表为空返回null
 * @returns 节点值
 */
SingleLinkList.prototype.pop = function () {
    if (this.head) {
        let node = this.head;
        this.head = node.next;
        this.len--;
        return node.value;
    }
    else {
        return null;
    }
}

查询和遍历

先完成遍历，链表遍历只需要不断获取head节点的next节点，直到next为null时就遍历了一遍链表，可以使用while循环解决，实现代码如下

/**
 * 遍历
 * @param {*} fn 回调函数
 */
SingleLinkList.prototype.finds = function (fn) {
    if (fn && Object.prototype.toString.call(fn) === "[object Function]") {
        let node = this.head;
        while (node) {
            fn(node.value);
            node = node.next;
        }
    } else {
        throw new Error("no callback function");
    }
}

注意，因为遵循后进先出原则，所以遍历顺序并不是你添加的顺序，而是相反，简单来说，new SingleLinkList(1, 2, 3)，对这个链表进行遍历时，返回的顺序是3, 2, 1，而不像数组for循环那样返回1, 2, 3

查询的原理类似，区别只是在每次while循环时判断下value的值是不是我们需要的，因此查询方法需要传入我们要查询的值，并返回查询到的值。这里添加了all参数，是个布尔值，默认false时只返回查询到的第一个，有些时候，我们可能希望直到查询值在链表里出现了几次，所以当all为true时，会一直查询到next为空，并返回一个数组，里面是所有查询到的值

/**
 * 查询
 * @param {*} value 要查询的值
 * @param {*} all 是否查全部，false只查询第一个，true查全部并返回值数组
 * @returns 节点值或节点值数组，未查到返回空值或空数组
 */
SingleLinkList.prototype.find = function (value, all = false) {
    let node = this.head;
    let nodeArr = [];
    while (node) {
        if (node.value === value) {
            if (all) {
                nodeArr.push(node.value);
            } else {
                return node.value;
            }
        }
        node = node.next;
    }
    if (all) {
        return nodeArr;
    } else {
        return null;
    }
}

这样遍历和查询就完成了，结束了吗？当然没有，这里只能支持一些基本类型的查询，比如数字、字符串、布尔值等。但是如果节点的value是对象，查询方法就不好使了，无法简单的通过node.value === value来判断，因为js中所有的对象都不相等，因此还需要处理value是对象的情况，这里我单独添加了一个方法，虽然可以在find里通过参数数量等方式来区别，不过个人感觉不够清晰，最好还是一个方法一个用处，因此处理对象查询的代码如下，这里需要给出对象的一个标识值，比如{name: “jack”}，查询方法支持查询name为"jack"的对象，需要传key为"name"，value为"jack"

/**
 * 查询
 * @param {*} key 节点的标识名
 * @param {*} value 节点的标识值
 * @param {*} all 是否查全部，false只查询第一个，true查全部并返回值数组
 * @returns 节点值或节点值数组，未查到返回空值或空数组
 */
SingleLinkList.prototype.findObj = function (key, value, all = false) {
    let node = this.node;
    let nodeArr = [];
    while (node) {
        if (node.value[key] === value) {
            if (all) {
                node.push(node.value);
            } else {
                return node.value;
            }
        }
        node = node.next;
    }
    if (all) {
        return nodeArr;
    } else {
        return null;
    }
}

插入、修改和删除

这些方法一样，都专门有针对对象的方法，注意插入是在目标节点的next上插入新节点
直接上代码了

/**
 * 编辑（默认编辑查到符合条件的第一个节点）
 * @param {*} oldValue 需要编辑的节点值
 * @param {*} newValue 新的的节点值
 * @param {*} all 是否编辑全部符合条件的节点
 * @returns 编辑是否成功
 */
SingleLinkList.prototype.modify = function (oldValue, newValue, all = false) {
    try {
        if (oldValue && newValue) {
            let isModify = false; // 是否编辑过
            let node = this.head;
            while (node) {
                if (node.value === oldValue) {
                    node.value = newValue;
                    isModify = true;
                    if (!all) return true;
                }
                node = node.next;
            }
            if (isModify && all) return true;
        }
        return false;
    } catch (error) {
        throw new Error(error);
    }
}

/**
 * 编辑（默认编辑查到符合条件的第一个节点）
 * 针对value是对象的节点
 * @param {*} key 节点的标识名
 * @param {*} value 节点的标识值
 * @param {*} newObj 新的节点值
 * @returns 编辑是否成功
 */
SingleLinkList.prototype.modifyObj = function (key, value, newObj, all = false) {
    try {
        if (key && value && newObj) {
            let isModify = false; // 是否编辑过
            let node = this.head;
            while (node) {
                if (node.value[key] === value) {
                    node.value = newObj;
                    isModify = true;
                    if (!all) return true;
                }
                node = node.next;
            }
            if (isModify && all) return true;
        }
        return false;
    } catch (error) {
        throw new Error(error);
    }
}

/**
 * 插入（放到目标节点的next位置）
 * @param {*} positionValue 目标节点值（默认查询到的第一个）
 * @param {*} insertValue 插入的节点值
 * @param {*} all 是否插入到全部符合条件的目标节点next上
 * @returns 是否插入成功
 */
SingleLinkList.prototype.insert = function (positionValue, insertValue, all = false) {
    try {
        if (positionValue && insertValue) {
            let isInsert = false; // 是否插入过
            let node = this.head;
            while (node) {
                if (node.value === positionValue) {
                    let newNode = new SingleNode(insertValue);
                    newNode.next = node.next;
                    node.next = newNode;
                    this.len++;
                    isInsert = true;
                    if (!all) return true;
                }
                node = node.next;
            }
            if (isInsert && all) return true;
        }
        return false;
    } catch (error) {
        throw new Error(error);
    }
}

/**
 * 插入（放到目标节点的next位置）
 * 针对value是对象的节点
 * @param {*} positionValue 目标节点值（默认查询到的第一个）
 * @param {*} insertValue 插入的节点值
 * @param {*} all 是否插入到全部符合条件的目标节点next上
 * @returns 是否插入成功
 */
SingleLinkList.prototype.insertObj = function (key, value, newObj, all = false) {
    try {
        if (key && value && newObj) {
            let isInsert = false; // 是否插入过
            let node = this.head;
            while (node) {
                if (node.value[key] === value) {
                    let newNode = new SingleNode(newObj);
                    newNode.next = node.next;
                    node.next = newNode;
                    this.len++;
                    isInsert = true;
                    if (!all) return true;
                }
                node = node.next;
            }
            if (isInsert && all) return true;
        }
        return false;
    } catch (error) {
        throw new Error(error);
    }
}

/**
 * 删除
 * @param {*} value 要删除的值
 * @param {*} all 是否删除全部  false只删除第一个，true删除全部
 * @returns 单个删除成功返回true，多个删除不返回值，未查询到删除值返回false
 */
SingleLinkList.prototype.delete = function (value, all = false) {
    let node = this.head;
    let isDelete = false;
    if (node.value === value) {
        node = node.next;
        this.head = node;
        this.len--;
        isDelete = true;
        if (!all) return true;
    }
    while (node) {
        if (node.next && node.next.value === value) {
            node.next = node.next.next;
            this.len--;
            isDelete = true;
            if (!all) return true;
        }
        node = node.next;
    }
    if (isDelete && all) return true;
    return false;
}

/**
 * 删除
 * 针对value是对象的节点
 * @param {*} key 节点的标识名
 * @param {*} value 节点的标识值
 * @param {*} all 是否删除全部  false只删除第一个，true删除全部
 * @returns 单个删除成功返回true，多个删除不返回值，未查询到删除值返回false
 */
 SingleLinkList.prototype.delete = function (key, value, all = false) {
    let node = this.head;
    let isDelete = false;
    if (node.value[key] === value) {
        node = node.next;
        this.head = node;
        this.len--;
        isDelete = true;
        if (!all) return true;
    }
    while (node) {
        if (node.next && node.next.value[key] === value) {
            node.next = node.next.next;
            this.len--;
            isDelete = true;
            if (!all) return true;
        }
        node = node.next;
    }
    if (isDelete && all) return true;
    return false;
}

javaScript完整代码

附上完整版的javaScript代码

// 单向链表节点
function SingleNode(value) {
    let node = Object.create(null);
    node.value = value;  // 节点值
    node.next = null;  // 下一个节点
    return node;
}

/**
 * 单向链表
 * 构造函数支持传参
 * 参数类型:单个参数，可变长参数，数组
 * @example new SingleLinkList(1);
 * @example new SingleLinkList(1, 2, 3);
 * @example new SingleLinkList([1, 2, 3]);
 */
function SingleLinkList() {
    this.head = null; // 头部节点
    this.len = 0; // 链表长度

    // 初始化方法里的添加方法
    function initPush(param) {
        let node = new SingleNode(param);
        if (this.head) {
            node.next = this.head;
        }
        this.head = node;
        this.len++;
    }
    // 构造方法的添加方法
    function initInsert(param) {
        if (Object.prototype.toString.call(param) === "[object Array]") {
            for (let i = 0; i < param.length; i++) {
                initPush.call(this, param[i]);
            }
        } else {
            initPush.call(this, param);
        }
    }

    // 初始化
    (function init(params) {
        switch (params.length) {
            case 0:
                break;
            // 节点数组或单个节点
            case 1:
                initInsert.call(this, params);
                break;
            // 可变长参数，多个节点
            default:
                for (let i = 0; i < params.length; i++) {
                    initInsert.call(this, params[i]);
                }
                break;
        }
    }.bind(this, arguments))();


    /**
     * 获取当前链表的长度
     * @returns 长度
     */
    SingleLinkList.prototype.length = function () {
        return this.len;
    }

    /**
     * 向链表添加一个节点，并放到头部
     * @param {*} value 节点值
     */
    SingleLinkList.prototype.push = function (value) {
        let node = new SingleNode(value);
        if (this.head) {
            node.next = this.head;
        }
        this.head = node;
        this.len++;
    }

    /**
     * 弹出最后加入的节点，链表为空返回null
     * @returns 节点值
     */
    SingleLinkList.prototype.pop = function () {
        if (this.head) {
            let node = this.head;
            this.head = node.next;
            this.len--;
            return node.value;
        }
        else {
            return null;
        }
    }

    /**
     * 遍历
     * @param {*} fn 回调函数
     */
    SingleLinkList.prototype.finds = function (fn) {
        if (fn && Object.prototype.toString.call(fn) === "[object Function]") {
            let node = this.head;
            while (node) {
                fn(node.value);
                node = node.next;
            }
        } else {
            throw new Error("no callback function");
        }
    }

    /**
     * 查询
     * @param {*} value 要查询的值
     * @param {*} all 是否查全部，false只查询第一个，true查全部并返回值数组
     * @returns 节点值或节点值数组，未查到返回空值或空数组
     */
    SingleLinkList.prototype.find = function (value, all = false) {
        let node = this.head;
        let nodeArr = [];
        while (node) {
            if (node.value === value) {
                if (all) {
                    nodeArr.push(node.value);
                } else {
                    return node.value;
                }
            }
            node = node.next;
        }
        if (all) {
            return nodeArr;
        } else {
            return null;
        }
    }

    /**
     * 查询
     * @param {*} key 节点的标识名
     * @param {*} value 节点的标识值
     * @param {*} all 是否查全部，false只查询第一个，true查全部并返回值数组
     * @returns 节点值或节点值数组，未查到返回空值或空数组
     */
    SingleLinkList.prototype.findObj = function (key, value, all = false) {
        let node = this.node;
        let nodeArr = [];
        while (node) {
            if (node.value[key] === value) {
                if (all) {
                    node.push(node.value);
                } else {
                    return node.value;
                }
            }
            node = node.next;
        }
        if (all) {
            return nodeArr;
        } else {
            return null;
        }
    }

    /**
     * 编辑（默认编辑查到符合条件的第一个节点）
     * @param {*} oldValue 需要编辑的节点值
     * @param {*} newValue 新的的节点值
     * @param {*} all 是否编辑全部符合条件的节点
     * @returns 编辑是否成功
     */
    SingleLinkList.prototype.modify = function (oldValue, newValue, all = false) {
        try {
            if (oldValue && newValue) {
                let isModify = false; // 是否编辑过
                let node = this.head;
                while (node) {
                    if (node.value === oldValue) {
                        node.value = newValue;
                        isModify = true;
                        if (!all) return true;
                    }
                    node = node.next;
                }
                if (isModify && all) return true;
            }
            return false;
        } catch (error) {
            throw new Error(error);
        }
    }

    /**
     * 编辑（默认编辑查到符合条件的第一个节点）
     * 针对value是对象的节点
     * @param {*} key 节点的标识名
     * @param {*} value 节点的标识值
     * @param {*} newObj 新的节点值
     * @returns 编辑是否成功
     */
    SingleLinkList.prototype.modifyObj = function (key, value, newObj, all = false) {
        try {
            if (key && value && newObj) {
                let isModify = false; // 是否编辑过
                let node = this.head;
                while (node) {
                    if (node.value[key] === value) {
                        node.value = newObj;
                        isModify = true;
                        if (!all) return true;
                    }
                    node = node.next;
                }
                if (isModify && all) return true;
            }
            return false;
        } catch (error) {
            throw new Error(error);
        }
    }

    /**
     * 插入（放到目标节点的next位置）
     * @param {*} positionValue 目标节点值（默认查询到的第一个）
     * @param {*} insertValue 插入的节点值
     * @param {*} all 是否插入到全部符合条件的目标节点next上
     * @returns 是否插入成功
     */
    SingleLinkList.prototype.insert = function (positionValue, insertValue, all = false) {
        try {
            if (positionValue && insertValue) {
                let isInsert = false; // 是否插入过
                let node = this.head;
                while (node) {
                    if (node.value === positionValue) {
                        let newNode = new SingleNode(insertValue);
                        newNode.next = node.next;
                        node.next = newNode;
                        this.len++;
                        isInsert = true;
                        if (!all) return true;
                    }
                    node = node.next;
                }
                if (isInsert && all) return true;
            }
            return false;
        } catch (error) {
            throw new Error(error);
        }
    }

    /**
     * 插入（放到目标节点的next位置）
     * 针对value是对象的节点
     * @param {*} positionValue 目标节点值（默认查询到的第一个）
     * @param {*} insertValue 插入的节点值
     * @param {*} all 是否插入到全部符合条件的目标节点next上
     * @returns 是否插入成功
     */
    SingleLinkList.prototype.insertObj = function (key, value, newObj, all = false) {
        try {
            if (key && value && newObj) {
                let isInsert = false; // 是否插入过
                let node = this.head;
                while (node) {
                    if (node.value[key] === value) {
                        let newNode = new SingleNode(newObj);
                        newNode.next = node.next;
                        node.next = newNode;
                        this.len++;
                        isInsert = true;
                        if (!all) return true;
                    }
                    node = node.next;
                }
                if (isInsert && all) return true;
            }
            return false;
        } catch (error) {
            throw new Error(error);
        }
    }

    /**
     * 删除
     * @param {*} value 要删除的值
     * @param {*} all 是否删除全部  false只删除第一个，true删除全部
     * @returns 单个删除成功返回true，多个删除不返回值，未查询到删除值返回false
     */
    SingleLinkList.prototype.delete = function (value, all = false) {
        let node = this.head;
        let isDelete = false;
        if (node.value === value) {
            node = node.next;
            this.head = node;
            this.len--;
            isDelete = true;
            if (!all) return true;
        }
        while (node) {
            if (node.next && node.next.value === value) {
                node.next = node.next.next;
                this.len--;
                isDelete = true;
                if (!all) return true;
            }
            node = node.next;
        }
        if (isDelete && all) return true;
        return false;
    }

    /**
     * 删除
     * 针对value是对象的节点
     * @param {*} key 节点的标识名
     * @param {*} value 节点的标识值
     * @param {*} all 是否删除全部  false只删除第一个，true删除全部
     * @returns 单个删除成功返回true，多个删除不返回值，未查询到删除值返回false
     */
     SingleLinkList.prototype.delete = function (key, value, all = false) {
        let node = this.head;
        let isDelete = false;
        if (node.value[key] === value) {
            node = node.next;
            this.head = node;
            this.len--;
            isDelete = true;
            if (!all) return true;
        }
        while (node) {
            if (node.next && node.next.value[key] === value) {
                node.next = node.next.next;
                this.len--;
                isDelete = true;
                if (!all) return true;
            }
            node = node.next;
        }
        if (isDelete && all) return true;
        return false;
    }
}

typeScript完整代码

typeScrit版的代码还未完成，这部分后续更新上

在这里插入代码片

结语

感谢大家的阅览，如果哪里写的有问题请大家指正，望与诸位共同进步