与单向链表
单向链表
也就是我们之前实现的链表结构。单向链表只能从头遍历到尾或者从尾遍历到头(当然一般都是从头到尾)。换言之，链表链接的过程是单向的。
原理
实现原理是上一个节点有指向下一个节点的引用。
缺点
- 到达下一个节点很容易，但是回到前一个节点就很难
双向链表
即可以从头遍历到尾，也可以从尾遍历到头
原理
一个节点即有向前连接的引用，也有向后连接的引用。
缺点
- 每次插入或删除节点，需要处理四个引用，而不是两个。
- 并且相对于单向链表，因为多了引用，内存空间更大一些。双向链表的长相
- 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
