-
Notifications
You must be signed in to change notification settings - Fork 0
/
DoubleLinkList.js
123 lines (122 loc) · 3.79 KB
/
DoubleLinkList.js
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
import LinkList from './Linklist'
import DoublyNode from './DoublyNode'
import { defaultEquals } from '../utils/index'
class DoubleLinkList extends LinkList {
constructor(equalsFn = defaultEquals){
super(equalsFn)
this.tail = undefined
}
push(element){
const node = new DoublyNode(element)
if (this.head == null) {
this.head = node
this.tail = node
} else {
node.prev = this.tail
this.tail.next = node
this.tail = node
}
}
insert(element,index){
if (index == this.count) { // 在链表尾部追加
this.push(element)
} else {
const node = new DoublyNode(element)
// 在链表头部追加
if (index == 0) {
if (this.head == null) { // 链表为空
this.head = node
this.tail = node
} else {
const firstNode = this.head
this.head = node
firstNode.prev = node
node.next = firstNode
}
}
// 在链表中间插入值,
const prevItem = this.getElementAt(index -1) // 拿到的前一项
let current = prevItem.next
prevItem.next = node
node.next = current
node.prev = prevItem
current.prev = node
this.count++
return true
// let current = this.head
// let prev
// for (let i = 0; i < index && index < this.count; i++) {
// prev = current
// current = current.next
// }
// prev.next = node
// node.next = current
}
return false
}
indexOf(element){
if (this.head == null) {
return -1
}
let current = this.head
let index = 0
while (current.next != null) {
if (this.equalsFn(current.element , element)) {
return index
}
index ++
current = current.next
}
}
// getElementAt(index){ //查找所在位置的元素,和链表中的方法一样
// if (this.head == null) {
// return undefined
// }
// let current = this.head
// let prev
// for (let i = 0; i < index; i++) {
// current = current.next
// }
// return current
// }
removeAt(index){ // 从任意位置移除元素
if (index >= 0 && index < this.count) {
let current
if (index == 0) { // 移除双向链表头部的元素
current = this.head
this.head = current.next
} else if (index == this.count - 1) { // 移除双向链表尾部的元素
current = this.tail
this.tail = current.prev
this.tail.next = undefined
} else { // 移除链表中间的元素,可用getElementAt()的方法
let current = this.getElementAt(index )
let prevItem = current.prev
prevItem.next = current.next
current.next.prev = prevItem
// let prev
// for (let i = 0; i < index ; i++) {
// prev = current
// current = current.next
// }
// prev.next = current.next
// current.next.prev = prev
}
this.count --
return current.element
}
return undefined
}
getHead(){
return this.head
}
getTail(){
return this.tail
}
clear(){
super.clear()
this.tail = undefined
}
toString(){}
inverseToString(){}
}