JavaScript数据结构——链表的实现与应用

  • 时间:
  • 浏览:1
  • 来源:大发时时彩官网_大发时时彩邀请码_大发时时彩娱乐平台

  链表用来存储有序的元素集合,与数组不同,链表中的元素我太久 保所处连续的存储空间内,每个元素由另另一个 存储元素一种的节点和另另一个 指向下另另一个 元素的指针构成。当要移动或删除元素时,只需用修改相应元素上的指针就都可以了。对链表元素的操作要比对数组元素的操作效率更高。下面是链表数据底部形态的示意图:

  要实现链表数据底部形态,关键在于保存head元素(即链表的头元素)以及每另另一个 元素的next指针,有这两每种好多好多 人 就都可以很方便地遍历链表从而操作所有的元素。都可以把链表想象成第一根锁链,锁链中的每另另一个 节点需用相互连接的,好多好多 人 而是我找到锁链的头,整条锁链就都都可以找到了。让好多好多 人 来看一下具体的实现最好的方法。

  首先好多好多 人 需用另另一个 辅助类,用来描述链表中的节点。这俩类很简单,只需用另另一个 属性,另另一个 用来保存节点的值,另另一个 用来保存指向下另另一个 节点的指针。

let Node = function (element) {
    this.element = element;
    this.next = null;
};

  下面是好多好多 人 链表类的基本骨架:

class LinkedList {
    constructor() {
        this.length = 0;
        this.head = null;
    }

    append (element) {} // 向链表中加进去去节点

    insert (position, element) {} // 在链表的指定位置插入节点

    removeAt (position) {} // 删除链表中指定位置的元素,并返回这俩元素的值

    remove (element) {} // 删除链表中对应的元素

    indexOf (element) {} // 在链表中查找给定元素的索引

    getElementAt (position) {} // 返回链表中索引所对应的元素

    isEmpty () {} // 判断链表否有为空

    size () {} // 返回链表的长度

    getHead () {} // 返回链表的头元素

    clear () {} // 清空链表

    toString () {} // 辅助最好的方法,按指定格式输出链表中的所有元素,方便测试验证结果
}

  让好多好多 人 从查找链表元素的最好的方法getElementAt()而是我结束了了英文英文,机会顶端好多好多 人 会多次用到它。

getElementAt (position) {
    if (position < 0 || position >= this.length) return null;

    let current = this.head;
    for (let i = 0; i < position; i++) {
        current = current.next;
    }
    return current;
}

   首先判断参数position的边界值,机会值超出了索引的范围(小于0机会大于length - 1),则返回null。好多好多 人 从链表的head而是我结束了了英文英文,遍历整个链表直到找到对应索引位置的节点,而是我 返回这俩节点。是需用很简单?和所有有序数据集合一样,链表的索引默认从0而是我结束了了英文英文,而是我找到了链表的头(好多好多 好多好多 人 需用在LinkedList类中保存head值),而是我 就都可以遍历找到索引所在位置的元素。

  有了getElementAt()最好的方法,接下来好多好多 人 就都可以很方便地实现append()最好的方法,用来在链表的尾部加进去去新节点。

append (element) {
    let node = new Node(element);

    // 机会当前链表为空,则将head指向node
    if (this.head === null) this.head = node;
    else {
        // 而是我

,找到链表尾部的元素,而是我

加进去去新元素
        let current = this.getElementAt(this.length - 1);
        current.next = node;
    }

    this.length++;
}

   机会链表的head为null(这俩状态表示链表为空),则直接将head指向新加进去去的元素。而是我 ,通过getElementAt()最好的方法找到链表的最后另另一个 节点,将该节点的next指针指向新加进去去的元素。新加进去去的元素的next指针默认为null,链表最后另另一个 元素的next值为null。将节点挂到链表上而是我,我太久 忘记将链表的长度加1,好多好多 人 需用通过length属性来记录链表的长度。

  接下来好多好多 人 要实现insert()最好的方法,都可以在链表的任意位置加进去去节点。

insert (position, element) {
    // position只有超出边界值
    if (position < 0 || position > this.length) return false;

    let node = new Node(element);

    if (position === 0) {
        node.next = this.head;
        this.head = node;
    }
    else {
        let previous = this.getElementAt(position - 1);
        node.next = previous.next;
        previous.next = node;
    }

    this.length++;
    return true;
}

  首先也是要判断参数position的边界值,只有越界。当position的值为0时,表示要在链表的头部插入新节点,对应的操作如下图所示。将新插入节点的next指针指向现在的head,而是我 更新head的值为新插入的节点。

  机会要插入的节点在链表的顶端机会尾部,对应的操作如下图。假设链表长度为3,要在位置2插入新节点,好多好多 人 首先找到位置2的前另另一个 节点previous node,将新节点new node的next指针指向previous node的next所对应的节点,而是我 再将previous node的next指针指向new node,好多好多 就把新节点挂到链表中了。考虑一下,当插入的节点在链表的尾部,这俩状态也是适用的。而机会链表为空,即链表的head为null,则参数position会超出边界条件,从而insert()最好的方法会直接返回false。

  最后,别忘了更新length属性的值,将链表的长度加1。

  按照相同的最好的方法,好多好多 人 都可以很容易地写出removeAt()最好的方法,用来删除链表中指定位置的节点。

removeAt (position) {
    // position只有超出边界值
    if (position < 0 || position >= this.length) return null;

    let current = this.head;

    if (position === 0) this.head = current.next;
    else {
        let previous = this.getElementAt(position - 1);
        current = previous.next;
        previous.next = current.next;
    }

    this.length--;
    return current.element;
}

   下面两张示意图说明了从链表头部和其它位置删除节点的状态。

  机会要删除的节点为链表的头部,只需用将head移到下另另一个 节点即可。机会当前链表只有另另一个 节点,这么 下另另一个 节点为null,此时将head指向下另另一个 节点等同于将head设置成null,删除而是我链表为空。机会要删除的节点在链表的顶端每种,好多好多 人 需用找出position所在位置的前另另一个 节点,将它的next指针指向position所在位置的下另另一个 节点。总之,删除节点只需用修改相应节点的指针,使断开位置左右相邻的节点重新连接上。被删除的节点机会再也这么 其它每种的引用而被丢弃在内存中,等待时间垃圾回收器来清除。有关JavaScript垃圾回收器的工作原理,都可以查看这里。

  最后,别忘了将链表的长度减1。

  下面好多好多 人 来看看indexOf()最好的方法,该最好的方法返回给定元素在链表中的索引位置。

indexOf (element) {
    let current = this.head;

    for (let i = 0; i < this.length; i++) {
        if (current.element === element) return i;
        current = current.next;
    }

    return -1;
}

  好多好多 人 从链表的头部而是我结束了了英文英文遍历,直到找到和给定元素相同的元素,而是我 返回对应的索引号。机会这么 找到对应的元素,则返回-1。

  链表类中的其它最好的方法都比较简单,就不再分部讲解了,下面是完正的链表类的代码:

   在isEmpty()最好的方法中,好多好多 人 都可以根据length否有为0来判断链表否有为空,当然也都可以根据head否有为null来进行判断,前提是所有涉及到链表节点加进去去和移除的最好的方法需用正确地更新length和head。toString()最好的方法好多好多 为了方便测试而编写的,好多好多 人 来看看几个测试用例:

let linkedList = new LinkedList();
linkedList.append(10);
linkedList.append(15);
linkedList.append(20);

console.log(linkedList.toString());

linkedList.insert(0, 9);
linkedList.insert(2, 11);
linkedList.insert(5, 25);
console.log(linkedList.toString());

console.log(linkedList.removeAt(0));
console.log(linkedList.removeAt(1));
console.log(linkedList.removeAt(3));
console.log(linkedList.toString());

console.log(linkedList.indexOf(20));

linkedList.remove(20);

console.log(linkedList.toString());

linkedList.clear();
console.log(linkedList.size());

  下面是执行结果:

双向链表

  顶端链表中每另另一个 元素只有另另一个 next指针,用来指向下另另一个 节点,好多好多 的链表称之为单向链表,好多好多 人 只有从链表的头部而是我结束了了英文英文遍历整个链表,任何另另一个 节点只有找到它的下另另一个 节点,而只有找到它的上另另一个 节点。双向链表中的每另另一个 元素拥有另另一个 指针,另另一个 用来指向下另另一个 节点,另另一个 用来指向上另另一个 节点。在双向链表中,除了都可以像单向链表一样从头部而是我结束了了英文英文遍历之外,还都可以从尾部进行遍历。下面是双向链表的数据底部形态示意图:

  机会双向链表具有单向链表的所有底部形态,而是我 好多好多 人 的双向链表类都可以继承自前面的单向链表类,不过辅助类Node需用加进去去另另一个 prev属性,用来指向前另另一个 节点。

let Node = function (element) {
    this.element = element;
    this.next = null;
    this.prev = null;
};

  下面是继承自LinkedList类的双向链表类的基本骨架:

class DoubleLinkedList extends LinkedList {
    constructor() {
        super();
        this.tail = null;
    }
}

   先来看看append()最好的方法的实现。当链表为空时,除了要将head指向当前加进去去的节点外,需用将tail也指向当需用加进去去的节点。当链表不为空时,直接将tail的next指向当需用加进去去的节点node,而是我 修改node的prev指向旧的tail,最后修改tail为新加进去去的节点。好多好多 人 不需用从头而是我结束了了英文英文遍历整个链表,而通过tail都可以直接找到链表的尾部,这俩点比单向链表的操作要更方便。最后将length的值加1,修改链表的长度。

append (element) {
    let node = new Node(element);

    // 机会链表为空,则将head和tail都指向当前加进去去的节点
    if (this.head === null) {
        this.head = node;
        this.tail = node;
    }
    else {
        // 而是我

,将当前节点加进去去到链表的尾部
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }

    this.length++;
}

   机会双向链表都可以从链表的尾部往前遍历,好多好多 好多好多 人 修改了getElementAt()最好的方法,对基类中单向链表的最好的方法进行了改写。当要查找的元素的索引号大于链表长度的一时节 ,从链表的尾部而是我结束了了英文英文遍历。

getElementAt (position) {
    if (position < 0 || position >= this.length) return null;

    // 从后往前遍历
    if (position > Math.floor(this.length / 2)) {
        let current = this.tail;
        for (let i = this.length - 1; i > position; i--) {
            current = current.prev;
        }
        return current;
    }
    // 好多好多

往后遍历
    else {
        return super.getElementAt(position);
    }
}

  有一种遍历最好的方法,好多好多 往后遍历调用的是基类单向链表里的最好的方法,从后往前遍历需用用到节点的prev指针,用来查找前另另一个 节点。

  好多好多 人 一起去还需用修改insert()和removeAt()这三个白多 最好的方法。记住,与单向链表唯一的区别好多好多 必一起去维护head和tail,以及每另另一个 节点上的next和prev指针。

insert (position, element) {
    if (position < 0 || position > this.length) return false;

    // 插入到尾部
    if (position === this.length) this.append(element);
    else {
        let node = new Node(element);

        // 插入到头部
        if (position === 0) {
            if (this.head === null) {
                this.head = node;
                this.tail = node;
            }
            else {
                node.next = this.head;
                this.head.prev = node;
                this.head = node;
            }
        }
        // 插入到顶端位置
        else {
            let current = this.getElementAt(position);
            let previous = current.prev;
            node.next = current;
            node.prev = previous;
            previous.next = node;
            current.prev = node;
        }
    }

    this.length++;
    return true;
}

removeAt (position) {
    // position只有超出边界值
    if (position < 0 || position >= this.length) return null;

    let current = this.head;
    let previous;

    // 移除头部元素
    if (position === 0) {
        this.head = current.next;
        this.head.prev = null;
        if (this.length === 1) this.tail = null;
    }
    // 移除尾部元素
    else if (position === this.length - 1) {
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = null;
    }
    // 移除顶端元素
    else {
        current = this.getElementAt(position);
        previous = current.prev;
        previous.next = current.next;
        current.next.prev = previous;
    }

    this.length--;
    return current.element;
}

  操作过程中需用判断好多好多 特殊状态,类式链表的头和尾,以及当前链表否有为空等等,而是我 进程机会会在好多好多 特殊状态下原困 越界和报错。下面是另另一个 完正的双向链表类的代码:

  好多好多 人 重写了toString()最好的方法以方便更加清楚地查看测试结果。下面是好多好多 测试用例:

let doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.append(10);
doubleLinkedList.append(15);
doubleLinkedList.append(20);
doubleLinkedList.append(25);
doubleLinkedList.append(50);
console.log(doubleLinkedList.toString());
console.log(doubleLinkedList.getElementAt(1).element);
console.log(doubleLinkedList.getElementAt(2).element);
console.log(doubleLinkedList.getElementAt(3).element);

doubleLinkedList.insert(0, 9);
doubleLinkedList.insert(4, 24);
doubleLinkedList.insert(7, 35);
console.log(doubleLinkedList.toString());

console.log(doubleLinkedList.removeAt(0));
console.log(doubleLinkedList.removeAt(1));
console.log(doubleLinkedList.removeAt(5));
console.log(doubleLinkedList.toString());

  对应的结果如下:

[element: 10, prev: null, next: 15] [element: 15, prev: 10, next: 20] [element: 20, prev: 15, next: 25] [element: 25, prev: 20, next: 50] [element: 50, prev: 25, next: null] 
15
20
25
[element: 9, prev: null, next: 10] [element: 10, prev: 9, next: 15] [element: 15, prev: 10, next: 20] [element: 20, prev: 15, next: 24] [element: 24, prev: 20, next: 25] [element: 25, prev: 24, next: 50] [element: 50, prev: 25, next: 35] [element: 35, prev: 50, next: null] 
9
15
50
[element: 10, prev: null, next: 20] [element: 20, prev: 10, next: 24] [element: 24, prev: 20, next: 25] [element: 25, prev: 24, next: 35] [element: 35, prev: 25, next: null] 

 循环链表

  顾名思义,循环链表的尾部指向它好多好多 人的头部。循环链表都可以有单向循环链表,也都可以有双向循环链表。下面是单向循环链表和双向循环链表的数据底部形态示意图:

  在实现循环链表时,需用确保最后另另一个 元素的next指针指向head。下面是单向循环链表的完正代码:

  单向循环链表的测试用例:

let circularLinkedList = new CircularLinkedList();
circularLinkedList.append(10);
circularLinkedList.append(15);
circularLinkedList.append(20);

console.log(circularLinkedList.toString());

circularLinkedList.insert(0, 9);
circularLinkedList.insert(3, 25);
console.log(circularLinkedList.toString());

console.log(circularLinkedList.removeAt(0));
console.log(circularLinkedList.toString());

  对应的测试结果:

  下一章好多好多 人 将介绍何如用JavaScript来实现集合这俩数据底部形态。

猜你喜欢

“挖矿”难,难于上青天

“若果价格可以 低得太离谱,我都我应该 赶紧卖掉。”看着堆积在地下室,占用了三分之二面积的近百台矿机,李成帷内心五味杂陈。跟跟我说,去年下多日 ,他辞去一家小贷金融公

2019-12-08

“一棵树”种出特色小镇——全国唯一银杏特色小镇

近日,住房和城乡建设部敲定第二批全国特色小镇名单。江苏邳州市的铁富镇,作为全国唯一银杏特色小镇,位列其中。邳州,自古以来有的是“银杏甲天下”的美称。做大“一棵树”的资源、做优“

2019-12-08

蔡元培墓地遭暴徒惡意破壞 北京大學香港校友會強烈譴責

大公網訊11月14日,著名教育家、已故北京大學校長蔡元培位於香港的墓地遭到暴力分子惡意損壞。北京大學香港校友會隨即發表聲明,對此次卑劣的暴力行徑表示極大憤慨和強烈譴責,對蔡校長

2019-12-07

外媒:摩托罗拉手机正在美国逐步兴起

IT之家7月28日消息 近日,据外媒报道,摩托罗拉手机正在美国逐步兴起;但并能推出旗舰手机来进入高端市场。▲via Phonearena据Phonearena报道,过去几年全球

2019-12-07

摩托罗拉Razr可折叠手机配置曝光:形似翻盖,配骁龙710

IT之家3月15日消息 先前的消息显示,摩托罗拉计划重振Razr品牌,并带来可折叠屏的设计。日前,XDA带来了关于该机的一系列新消息。这款手机代号“Voyager”,搭载骁龙7

2019-12-07