Repository navigation
Expand file tree
/
Copy pathLinkedList.js
More file actions
142 lines (125 loc) · 3.19 KB
/
Copy pathLinkedList.js
File metadata and controls
142 lines (125 loc) · 3.19 KB
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
/*
* 定义节点类
*/
function Node(element) {
this.element = element;
this.next = null;
}
/*
* 定义链表
*/
var LinkedList = function(){
// 定义链表的头结点和长度属性
this.head = null;
this.length = 0;
}
// 链表尾部追加元素方法
LinkedList.prototype.append = function(element) {
// 根据新元素创建节点
var newNode = new Node(element);
// 判断当前链表是否为空
if(this.head === null) {
this.head = newNode;
} else {
// 当前链表不为空
var current = this.head;
while(current.next) {
current = current.next;
}
// 为最后一个节点赋值
current.next = newNode;
}
// 最后，增加链表长度
this.length++;
}
// 根据下标插入元素
LinkedList.prototype.insert = function(position, element) {
// 检测越界问题: 越界插入失败
if (position < 0 || position > this.length) return false;
var newNode = new Node(element);
var current = this.head;
var previous = null;
var index = 0;
if(position === 0) {
newNode.next = current;
this.head = newNode;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
// 最后增加长度
this.length++;
return true;
}
// 根据位置移除节点
LinkedList.prototype.removeAt = function (position) {
// 检测越界问题: 越界移除失败, 返回null
if (position < 0 || position >= this.length) return null;
// 定义变量, 保存信息
var current = this.head;
var previous = null;
var index = 0;
// 判断是否是移除第一项
if (position === 0) {
this.head = current.next;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
// 链表长度减1
this.length--;
// 返回移除的数据
return current.element;
}
// 查找值所对应的索引
LinkedList.prototype.indexOf = function(element) {
// 定义变量
var current = this.head;
var index = 0;
while(current) {
if(current.element === element) {
return index;
}
index++;
current = current.next;
}
// 如果没有找到，返回-1
return -1;
}
// 根据元素删除信息
LinkedList.prototype.remove = function(element) {
var index = this.indexOf(element);
if(index !== -1)
return this.removeAt(index);
}
// 判断链表是否为空
LinkedList.prototype.isEmpty = function () {
return this.length == 0;
}
// 获取链表的长度
LinkedList.prototype.size = function () {
return this.length;
}
// 获取第一个节点
LinkedList.prototype.getFirst = function () {
return this.head.element;
}
// 链表的toString方法
LinkedList.prototype.toString = function() {
var current = this.head;
var str = "";
while(current) {
str += ", "+current.element;
current = current.next;
}
// 返回字符串
return str.slice(1);
}
module.exports = LinkedList;