数据结构-双向链表_双向链表的特点

双向链表

1、双向链表的特点：

1、可以使用一个head和一个tail分别指向头部和尾部的节点
2、每个节点都由三部分组成：
前一个节点的指针prev
保存的元素item
后一个节点的指针next
3、双向链表的第一个节点的prev是null
4、双向链表的最后节点的next是null

2、双向链表常见操作：

1、append(element):
向列表尾部添加一个新的项
2、insert(position, element):
向链表的特定位置插入一个新的项
3、get(position):
获取对应位置的元素
4、indexOf(element):
返回元素在列表中的索引，如果列表中没有该元素则返回-1
5、update(position, element):
修改某个位置的元素
6、removeAt(position):
从列表的特定位置移除一项
7、remove(element):
从列表中移除一项
8、isEmpty():
如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
9、size():
返回链表包含的元素个数，与数组的length属性类似
10、toString():
由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
11、backwordString():
返回从前向后遍历的节点字符串形式
12、forwardString():
返回从后向前遍历的节点字符串形式
13、getHead():
获取链表的第一个元素
14、getTail():
获取链表的最后一个元素

3、封装双向链表

 // 创建双向链表的构造函数
    function DoublyLinkedList() {
   
        // 创建节点构造函数
        function Node(element) {
   
            this.element = element
            this.next = null
            this.prev = null // 新添加的
        }

        // 定义属性
        this.length = 0
        this.head = null
        this.tail = null // 新添加的

        // 定义相关操作方法
        // 1、append 在尾部追加数据
        DoublyLinkedList.prototype.append = function (element) {
   
            // 1.根据元素创建节点
            var newNode = new Node(element)

            // 2.判断列表是否为空列表
            if (this.head == null) {
   
                this.head = newNode
                this.tail = newNode
            } else {
   
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            }

            // 3.length+1
            this.length++
        }

         // 2、实现toString方法
        DoublyLinkedList.prototype.toString = function () {
   
            return this.backwardString()
        }

        // 3、forwardString 向前遍历
        DoublyLinkedList.prototype.forwardString = function () {
   
            var current = this.tail
            var forwardStr = ""

            while (current) {
   
                forwardStr += current.element + " "
                current = current.prev
            }

            return forwardStr
        }

        // 4、backwardString 从前向后遍历
        DoublyLinkedList.prototype.backwardString = function(){
   
            var current 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63