JavaScript的数据结构与算法（四） —— 双向链表

Youngdze 发布于2019-08-21 17:13 / 464人阅读

摘要：链表链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。链表又包括单向链表和双向链表双向链表双向链表与单向链表很是相像。但在双向链表中，还有指向上一个节点的链接，是双向的。

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本事的节点和一个指向下一个元素的引用组成。相对于传统的数组，链表的一个好处在于，添加或者删除元素的时候不需要移动其他元素。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

数组和链表的一个不同在于数组可以直接访问任何位置的元素，而想要访问链表中的一个元素，需要从起点开始迭代列表。

链表又包括：单向链表和双向链表；

双向链表

双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。

让我们来简单实现一个双向链表类，并包含如下功能：

append(element): 添加元素到链表尾部

insert(position,element): 向双向链表中某个位置插入元素

removeAt(position): 移除双向链表中某个位置的元素

getHead(): 获取双向链表的头部

getTail(): 获取双向链表的尾部

isEmpty(): 检查双向链表是否为空，为空则返回true

size(): 返回双向链表长度

代码如下：

   function DoublyLinkedList() {
    /**
     * 双向链表中节点的构造函数
     * 
     * @param {any} element 要插入链表的元素
     */
    var Node = function (element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    }

    // 双向链表的长度
    var length = 0;
    // 双向链表的头结点，默认为null
    var head = null;
    // 双向链表的尾结点，默认为null
    var tail = null;
    
    /**
     * 添加元素到双向链表的尾部
     * 
     * @param {any} element 要插入的元素
     */
    this.append = function (element) {
        var node = new Node(element),
            current = head;

        if (head === null) {
            head = node
            tail = node
        } else {
            while (current.next) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;
            tail = node;
        }
        length++;
        return true;
    }


    /**
     * 向双向链表中某个位置插入元素
     * 
     * @param {any} position 要插入的位置
     * @param {any} element 要插入的元素
     * @returns 插入成功或失败
     */
    this.insert = function (position, element) {
        var node = new Node(element),
            current = head,
            previous,
            index = 0;
        // 限制边界
        if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 在链表的头部插入元素
            node.next = head
            head.prev = node
            head = node
        } else if (position === length) {
            // 在链表的尾部插入元素
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        } else {
            // 在链表的中间插入元素
            while (index++ < position) {
                previous = current
                current = current.next;
            }
            // 绑定前一个节点和插入节点的关系
            previous.next = node;
            node.prev = previous;
            // 绑定后一个节点和插入节点的关系
            node.next = current;
            current.prev = node;
        }
        length++;
        return true;
    }

    /**
     * 移除双向链表中某个位置的元素
     * 
     * @param {any} position 要移除元素的位置
     * @returns 移除成功，返回移除的元素
     */
    this.removeAt = function (position) {
        var previous,
            current = head,
            index = 0;
         // 限制边界
         if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 移除链表的头部
            head = current.next;
            head.prev = null;
        } else if(position === length - 1) {
             // 移除链表尾部的元素
             current = tail;
             tail = current.prev;
             tail.next = null;
        } else {
            // 移除链表中间的元素
            while (index++ < position) {
                previous = current
                current = current.next;
            }
            previous.next = current.next;
            current.next.prev = previous;
        }
        length--;
        return current.element;
    }

    this.getHead = function () {
        return head.element;
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.getTail = function () {
        
        return tail.element;
    }

    this.size = function () {
        return length
    }
}

云服务器 GPU云服务器双向链表 java双向链表描述的数据结构与算法链表算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89273.html

学习JavaScript数据结构与算法（二）：链表

摘要：实现移除给定的元素要移除的元素返回值表示移除成功方法说明移除单向链表中某个位置的元素。的前端乐园原文链接寒假前端学习学习数据结构与算法二链表本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第四篇文章：学习JavaScript数据结构与...

lolomaco 2019-08-22 11:00 评论0 收藏0
javascript数据结构与算法（一）单向链表与双向链表

摘要：创建双向链表创建节点继承添加前继指针初始化双向链表对链表最后一个元素进行引用插入操作尾插法任意位置添加元素删除操作删除特定位置的元素查询操作查询元素的位置查询尾部元素修改操作清空双向链表双向链表对象转为字符串线性表（List）：零个或者多个数据元素的有限序列。线性表是一个序列，具有一对一的关系，而不能具备一对多的关系。线性表要求有限性，数据类型也要相同。本文参考的主要是大话数据结构...

William_Sang 2019-08-26 10:48 评论0 收藏0
《Javascript数据结构和算法》笔记-「链表」

摘要：链表数据结构与算法第五章链表数据结构链表不同与数组数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。 JavaScript-链表《Javascript数据结构与算法》第五章 5.1 链表数据结构链表不同与数组数组要插入或者移入一个元素的成本很高，因为所有元素都需要移动位置。链表插入或者移动一个元素时很高效，因为并不需要移动其他的元素位置。链表存储元素的方式...

gclove 2019-08-26 13:22 评论0 收藏0
Javascript数据结构与算法（二）循环链表与有序链表

摘要：循环链表可以像单向链表引用，也可以像双向链表有双向引用。以下就以如何创建栈数据结构为例。循环链表可以像单向链表引用，也可以像双向链表有双向引用。性能上也跟双向链表差不多，如果position大于length/2，那就可以从尾部开始迭代，可以减少迭代的元素。唯一的区别在于最后一个元素指向下一个元素的指针(tail.next)不是undefine，而是第一个元素（head）。接下来来看一...

YacaToy 2019-08-26 10:49 评论0 收藏0
JavaScript 数据结构与算法之美 - 线性表（数组、栈、队列、链表）

摘要：每个线性表上的数据最多只有前和后两个方向。数组链表队列栈等就是线性表结构。非线性表数据之间并不是简单的前后关系。不包含任何元素的栈称为空栈。移除栈顶的元素，同时返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言基础知识就像是一座大楼的地基，它决定了我们的技术高度。我们应该多掌握一些可移值的...

kaka 2019-08-23 18:25 评论0 收藏0