亲宝软件园·资讯

展开

JS链表

橘猫吃不胖~ 人气:1

1 数组与链表的优缺点

链表和数组一样,都可以用于存储一系列的元素,但是链表和数组的实现机制完全不同。

一般情况下,要存储多个元素,数组可能是最常用的数据结构。但是使用数组存储有一些缺点:

存储多个元素的另一个选择就是链表,但是不同于数组,链表中的元素在内存中不必是连续的空间,链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用(指针)组成。

那么和数组相比,链表有一些优势:

链表也有一些缺点:

2 什么是链表

链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用(指针)组成。

它类似于火车,火车头就是头节点,火车车厢之间的连接类似于指针,火车上的乘客类似于数据。

接下来我们根据它的特性来手动封装一个链表。

3 封装链表结构

首先我们来封装一个链表类LindedList,用来表示我们的链表结构。LindedList类中应该有两个属性,链表的头节点head和链表的长度length

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
}

LindedList类内部有一个ListNode类,用于创建节点,创建节点时应该为节点传入数据data,并且该节点有指向下一个节点的指针。

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
    function ListNode(data) {
        this.data = data;
        this.next = null;
    }
}

到这里链表的基础结构就完成了,接下来我们来封装链表的方法。

4 向链表尾部添加一个新的项

向链表尾部添加一个新的节点,有两种情况:

根据这个思路,我们可以实现append方法如下:

LinkedList.prototype.append = function (data) { // data是新节点的值
    let node = new ListNode(data); // 创建新的节点
    if (this.length === 0) { // 如果链表为空,则新节点就是头节点
        this.head = node;
    } else { // 如果链表不为空,新节点添加到链表尾部
        let current = this.head; // 将current指向头节点
        // 链表无法直接访问到最后的节点,只能通过一次次遍历来访问
        while (current.next) { // 当达到最后一个节点时,循环结束
            // 当下一个节点存在时,就让current指针移动到下一个节点上
            current = current.next;
        }
        // 最后一个节点指向新节点
        current.next = node;
    }
    this.length += 1; // 链表的长度+1
}

5 向链表某个位置插入一个新的项

在链表的任意位置插入节点时,也分为两种情况:

插入insert方法代码实现如下:

// position为节点要插入的位置,data为节点的值
LinkedList.prototype.insert = function (position, data) {
    // 对position进行越界判断,当该值小于0或者大于链表长度时,不能进行插入操作
    if (position <= 0 || position > this.length) return false;
    let node = new ListNode(data); // 创建新节点
    if (position === 0) { // 如果节点要插入第一个位置
        node.next = this.head; // 新节点指向原来的头节点
        this.head = node; // 头节点修改为新节点
    } else {
        let previous = null; // 指向前一个位置
        let current = this.head; // 指向下一个位置
        let index = 1; // 记录循环的位置
        // 循环结束,previous和current之间就是插入的节点
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        previous.next = node; // 在正确的位置插入元素
        node.next = current;
    }
    this.length += 1; // 长度加1
}

6 获取对应位置的元素

获取某个位置上的元素,也要通过循环链表来找到当前元素,get方法实现如下:

LinkedList.prototype.get = function (position) {
    // 越界判断,如果位置小于0或者大于链表长度,不能获取到元素
    if (position <= 0 || position > this.length) return null;
    let index = 1; // 记录当前位置
    let current = this.head; // current指向头节点
    // 循环结束,current指向该位置上的节点
    while (index < position) {
        current = current.next;
        index++;
    }
    return current.data;
}

7 获取元素在链表中的索引

获取索引时,要循环遍历链表,将链表的每一个节点值都和给定的值比较,如果相等返回当前节点的位置,如果没找到,则返回-1。indexOf方法实现如下:

// 获取某个元素的位置
LinkedList.prototype.indexOf = function (data) {
    let current = this.head;
    let index = 1; // 记录元素的位置
    while (current) { // 循环遍历链表
        if (current.data === data) { // 如果当前节点的值等于元素的值
            return index; // 返回位置
        } else { // 如果不等于,继续循环
            current = current.next;
            index++;
        }
    }
    return -1; // 循环结束了,说明没找到
}

8 修改某个位置的元素

修改某个位置的元素时,循环遍历链表,找到给定的位置,修改该位置上元素的值。update方法实现如下:

// 修改某个位置的元素
LinkedList.prototype.update = function (position, data) {
    // 越界判断
    if (position <= 0 || position > this.length) return false;
    let current = this.head;
    let index = 1;
    while (index < position) {
        current = current.next;
        index++;
    }
    current.data = data; // 修改数据
    return true;
}

9 从链表中删除某位置节点

删除某个位置上的节点分为两种情况:

删除某位置节点removeAt方法实现如下:

LinkedList.prototype.removeAt = function (position) {
    if (position <= 0 || position > this.length) return false; // 越界判断
    let current = this.head;
    if (position === 1) { // 如果删除第一个位置上的节点(头节点)
        this.head = this.head.next;
    } else { // 删除其他位置的节点
        let index = 1; // 记录当前位置
        let previous = null;
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        // 上一个节点指向当前元素的下一个节点
        previous.next = current.next;
    }
    this.length--;
    return current; // 返回被删除的节点
}

10 全部代码

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
    function ListNode(data) { // 创建新节点类
        this.data = data;
        this.next = null;
    }
    // 添加元素
    LinkedList.prototype.append = function (data) { // data是新节点的值
        let node = new ListNode(data); // 创建新的节点
        if (this.length === 0) { // 如果链表为空,则新节点就是头节点
            this.head = node;
        } else { // 如果链表不为空,新节点添加到链表尾部
            let current = this.head; // 将current指向头节点
            // 链表无法直接访问到最后的节点,只能通过一次次遍历来访问
            while (current.next) { // 当达到最后一个节点时,循环结束
                // 当下一个节点存在时,就让current指针移动到下一个节点上
                current = current.next;
            }
            // 最后一个节点指向新节点
            current.next = node;
        }
        this.length += 1; // 链表的长度+1
    }
    // 插入元素
    // position为节点要插入的位置,data为节点的值
    LinkedList.prototype.insert = function (position, data) {
        // 对position进行越界判断,当该值小于0或者大于链表长度时,不能进行插入操作
        if (position <= 0 || position > this.length) return false;
        let node = new ListNode(data); // 创建新节点
        if (position === 0) { // 如果节点要插入第一个位置
            node.next = this.head; // 新节点指向原来的头节点
            this.head = node; // 头节点修改为新节点
        } else {
            let previous = null; // 指向前一个位置
            let current = this.head; // 指向下一个位置
            let index = 1; // 记录循环的位置
            // 循环结束,previous和current之间就是插入的节点
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = node; // 在正确的位置插入元素
            node.next = current;
        }
        this.length += 1; // 长度加1
    }
    // 获取某个位置上的元素
    LinkedList.prototype.get = function (position) {
        // 越界判断,如果位置小于0或者大于链表长度,不能获取到元素
        if (position <= 0 || position > this.length) return null;
        let index = 1; // 记录当前位置
        let current = this.head; // current指向头节点
        // 循环结束,current指向该位置上的节点
        while (index < position) {
            current = current.next;
            index++;
        }
        return current.data;
    }
    // 获取某个元素的位置
    LinkedList.prototype.indexOf = function (data) {
        let current = this.head;
        let index = 1; // 记录元素的位置
        while (current) { // 循环遍历链表
            if (current.data === data) { // 如果当前节点的值等于元素的值
                return index; // 返回位置
            } else { // 如果不等于,继续循环
                current = current.next;
                index++;
            }
        }
        return -1; // 循环结束了,说明没找到
    }
    // 修改某个位置的元素
    LinkedList.prototype.update = function (position, data) {
        // 越界判断
        if (position <= 0 || position > this.length) return false;
        let current = this.head;
        let index = 1;
        while (index < position) {
            current = current.next;
            index++;
        }
        current.data = data; // 修改数据
        return true;
    }
    LinkedList.prototype.removeAt = function (position) {
        if (position <= 0 || position > this.length) return false; // 越界判断
        let current = this.head;
        if (position === 1) { // 如果删除第一个位置上的节点(头节点)
            this.head = this.head.next;
        } else { // 删除其他位置的节点
            let index = 1; // 记录当前位置
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            // 上一个节点指向当前元素的下一个节点
            previous.next = current.next;
        }
        this.length--;
        return current; // 返回被删除的节点
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论