双向链表[js实现] 【1】

与单向链表

单向链表

也就是我们之前实现的链表结构。单向链表只能从头遍历到尾或者从尾遍历到头(当然一般都是从头到尾)。换言之，链表链接的过程是单向的。

原理

实现原理是上一个节点有指向下一个节点的引用。

缺点

• 到达下一个节点很容易，但是回到前一个节点就很难

双向链表

即可以从头遍历到尾，也可以从尾遍历到头

原理

一个节点即有向前连接的引用，也有向后连接的引用。

缺点

• 每次插入或删除节点，需要处理四个引用，而不是两个。
• 并且相对于单向链表，因为多了引用，内存空间更大一些。双向链表的长相

image.png

• header和tail(与单向链表不同)分别指向头部和尾部。
• 每个节点由三部分组成:prev(前一个节点的指针)、item(报保存的元素)、后一个节点的指针(next)
• 双向链表的第一个节点的prev是null
• 双向链表的最后一个节点的next是null

封装双向链表

• 三个属性:head(头部)、tail(尾部)、length(长度)
• 内部类Node用于创建节点，将data作为参数。节点包括数据data、指向上一个节点的prev、和指向下一个节点的next

 // 封装双向链表
        function TwoWayLinkList() {
            // 属性 
            this.head = null
            this.tail = null
            this.length = 0
            // 用于创建节点的内部类
            function Node(data) {
                this.data = data
                this.prev = null
                this.next = null
            }
        }
复制代码

双向链表常见操作

其他操作

• isEmpty():如果链表中不包含任何元素，返回true，长度大于0返回false。
• size():返回链表的元素个数，对应数组中的length。
• toString():由于列表使用了Node类，就需要重写继承自js对象的默认的toString方法，让其只输出元素的值。
• forwardString():返回正向遍历的节点字符串
• backwardString():返回反向遍历的节点字符串

然后，以下的操作方法。可以按照增删改查的顺序来看：

增

• append(element):向列表尾部插入新的项
• insert(position,element):向列表指定位置插入新的项

删

• removeAt(position):从列表的特定位置移除一项（给的是位置信息） remove(element):从列表中移除给定元素项(给的元素信息)

改

• update(position,element):修改某个位置元素

查

• get(position): 根据位置获得元素
• indexOf(element):根据元素获得位置，没有的话返回 -1