/
DoublyLinkedList.js
161 lines (139 loc) · 3.28 KB
/
DoublyLinkedList.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
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
/**
* 双向链表的构造函数
*/
function DoublyLinkedList() {
/**
* 双向链表中节点的构造函数
* @param {Any} element 要传入链表的元素
*/
var Node = function(element) {
this.element = element;
this.prev = null;
this.next = null;
}
//双向链表的长度
var length = 0;
//双向链表的头结点,初始化为NULL
var head = null;
//双向链表的尾结点,初始化为NULL
var tail = null;
/**
* 向链表尾部添加元素
* @param {Any} element 要加入链表的节点
* @return {Any} 加入链表的节点
*/
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var previous;
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};
/**
* 向链表中插入某个元素
* @param {Number} position 要插入的位置
* @return {Boolean} 插入成功返回true,失败返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var index = 0;
var previous;
var current = head;
if (position === 0) {
if (head === null) {
head = node;
tail = node;
} else {
current.prev = node;
node.next = current;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.prev = previous;
current.prev = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
/**
* 移除链表中某一个元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素,不成功则返回false
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var index = 0;
var previous;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current.prev;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return false;
}
};
/**
* 获取链表的头部
* @return {Any} 链表的头部
*/
this.showHead = function() {
return head;
};
/**
* 获取链表长度
* @return {Number} 链表长度
*/
this.showLength = function() {
return length;
};
/**
* 获取链表尾部
* @return {Any} 链表尾部
*/
this.showTail = function() {
return tail;
}
};