JavaScriptAlgorithms/Linked list/DoubleLoopLinkedList.html at master · biaodigit/JavaScriptAlgorithms · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 双向循环链表
    function Node(val) {
        this.val = val
        this.next = null
        this.previous = null
    }

    class DoubleLoopList {
        constructor() {
            this.head = null
            this.tail = null
            this.length = null
        }

        append(element) {
            let node = new Node(element),
                previous,
                current;
            if (!this.head) {
                this.head = node
                this.tail = node
                this.head.previous = this.tail
                this.tail.next = this.head
            } else {
                current = this.head
                while (current.next !== this.head) {
                    previous = current
                    current = current.next
                }
                current.next = node
                node.next = this.head
                node.previous = current
                this.tail = node
                this.head.previous = node
            }
            this.length++
        }

        insert(position, element) {
            if (position > -1) {
                let node = new Node(element),
                    current = this.head,
                    previous,
                    index = 0;
                if (!current) {
                    this.head = node
                    this.tail = node
                    this.head.next = this.tail
                    this.tail.previous = this.head
                    this.loop()
                } else {
                    if (position === 0) {
                        node.next = current
                        current.previous = node
                        node.previous = this.tail
                        this.head = node
                        this.tail.next = this.head
                    } else if (position !== 0 && position < this.length) {
                        while (index++ < position) {
                            previous = current
                            current = current.next
                        }
                        node.next = current
                        current.previous = node
                        previous.next = node
                        node.previous = previous
                    } else {
                        previous = this.tail
                        previous.next = node
                        node.previous = previous
                        node.next = this.head
                        this.head.previous = node
                        this.tail = node
                    }
                }
            }
            this.length++
        }

        remove(element) {
            let node = this.find(element),
                current = this.head,
                previous,
                tail = this.tail;
            if (node.val !== element) {
                return false
            }
            if (node === current) {
                this.head = node.next
                this.loop()
            } else if (node === tail) {
                this.tail = node.previous
                this.loop()
            } else {
                while (current.val !== element) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next
                current.next.previous = previous
            }

            this.length--
        }

        removeAt(element) {
            let current = this.head,
                index = 0,
                previous;
            if (index === element) {
                if (this.length === 1) {
                    this.head = null
                    this.tail = null
                } else {
                    this.head = current.next
                    this.loop()
                }
            } else if (element === this.length - 1) {
                previous = this.tail.previous
                this.tail = previous
                this.loop()
            } else {
                while (index++ < element) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next
                current.next.previous = previous
            }
            this.length--
        }

        find(item) {
            let current = this.head
            while (current.val !== item && current.next) {
                current = current.next
            }
            return current
        }

        loop() {
            this.head.previous = this.tail
            this.tail.next = this.head
        }
    }

    let list = new DoubleLoopList()
    list.append(1)
    list.append(2)
    list.append(3)
    //    list.append(4)
    //    list.remove(3)
    list.removeAt(1)
    list.append(4)
    console.log(list)
</script>
</body>
</html>