Skip to content

Commit f255dce

Browse files
taokexiataokexia
committed
add LinkedList
1 parent 8a2cac1 commit f255dce

3 files changed

Lines changed: 363 additions & 0 deletions

File tree

‎JavaScript/LinkedList/DoubleLinkedList.js‎

Lines changed: 185 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,185 @@
1+
/*
2+
* 定义节点
3+
*/
4+
function Node(element) {
5+
this.element = element;
6+
this.next = null;
7+
this.prev = null;
8+
}
9+
10+
/*
11+
* 定义双向链表
12+
*/
13+
module.exports = function DoubleLinkedList() {
14+
// 定义属性
15+
this.head = null;
16+
this.tail = null;
17+
this.length = 0;
18+
19+
// 尾部添加元素
20+
DoubleLinkedList.prototype.append = function(element) {
21+
// 创建节点
22+
var newNode = new Node(element);
23+
24+
// 插入元素
25+
if(this.head === null) {
26+
this.head = newNode;
27+
this.tail = newNode;
28+
} else {
29+
this.tail.next = newNode;
30+
newNode.prev = this.tail;
31+
this.tail = newNode;
32+
}
33+
// 最后更新长度
34+
this.length++;
35+
}
36+
37+
// 在任意位置上插入数据
38+
DoubleLinkedList.prototype.insert = function(position, element) {
39+
// 判断越界的问题
40+
if (position < 0 || position > this.length) return false
41+
42+
// 创建节点
43+
var newNode = new Node(element);
44+
45+
if(position === 0) {
46+
// 判断头结点是否为空
47+
if(this.head === null) {
48+
this.head = newNode;
49+
this.tail = newNode;
50+
} else {
51+
this.head.prev = newNode;
52+
newNode.next = this.head;
53+
this.head = newNode;
54+
}
55+
} else if(position === this.length ){
56+
// 当前插入到链表最后
57+
// 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
58+
this.tail.next = newNode;
59+
newNode.prev = this.tail;
60+
this.tail = newNode;
61+
} else {
62+
// 在中间插入数据
63+
var index = 0;
64+
var current = this.head;
65+
var previous = null;
66+
67+
while(index++ < position) {
68+
previous = current;
69+
current = current.next;
70+
}
71+
72+
// 插入节点
73+
newNode.next = current;
74+
current.prev = newNode;
75+
previous.next = newNode;
76+
newNode.prev = previous;
77+
}
78+
// 更新长度
79+
this.length++;
80+
return true;
81+
}
82+
83+
// 根据位置删除对应的元素
84+
DoubleLinkedList.prototype.removeAt = function (position) {
85+
// 判断越界的问题
86+
if (position < 0 || position >= this.length) return null;
87+
// 判断移除的位置
88+
var current = this.head;
89+
if (position === 0) {
90+
if (this.length === 1) {
91+
this.head = null;
92+
this.tail = null;
93+
} else {
94+
this.head = this.head.next;
95+
this.head.prev = null;
96+
}
97+
} else if (position === this.length -1) {
98+
current = this.tail;
99+
this.tail = this.tail.prev;
100+
this.tail.next = null;
101+
} else {
102+
var index = 0;
103+
var previous = null;
104+
while (index++ < position) {
105+
previous = current;
106+
current = current.next;
107+
}
108+
previous.next = current.next;
109+
current.next.prev = previous;
110+
}
111+
// 更新长度
112+
this.length--;
113+
return current.element;
114+
}
115+
116+
// 根据元素获取在链表中的位置
117+
DoubleLinkedList.prototype.indexOf = function (element) {
118+
// 定义变量保存信息
119+
var current = this.head;
120+
var index = 0;
121+
// 查找正确的信息
122+
while (current) {
123+
if (current.element === element) {
124+
return index;
125+
}
126+
index++;
127+
current = current.next;
128+
}
129+
// 来到这个位置, 说明没有找到, 则返回-1
130+
return -1;
131+
}
132+
133+
// 根据元素删除
134+
DoubleLinkedList.prototype.remove = function (element) {
135+
var index = this.indexOf(element);
136+
return this.removeAt(index);
137+
}
138+
139+
// 判断是否为空
140+
DoubleLinkedList.prototype.isEmpty = function () {
141+
return this.length === 0;
142+
}
143+
144+
// 获取链表长度
145+
DoubleLinkedList.prototype.size = function () {
146+
return this.length;
147+
}
148+
149+
// 获取第一个元素
150+
DoubleLinkedList.prototype.getHead = function () {
151+
return this.head.element;
152+
}
153+
154+
// 获取最后一个元素
155+
DoubleLinkedList.prototype.getTail = function () {
156+
return this.tail.element;
157+
}
158+
159+
// 遍历方法的实现
160+
// 正向遍历的方法
161+
DoubleLinkedList.prototype.forwardString = function () {
162+
var current = this.head;
163+
var forwardStr = "";
164+
while (current) {
165+
forwardStr += ", " + current.element;
166+
current = current.next;
167+
}
168+
return forwardStr.slice(1);
169+
}
170+
// 反向遍历的方法
171+
DoubleLinkedList.prototype.reverseString = function () {
172+
var current = this.tail;
173+
var reverseStr = "";
174+
while (current) {
175+
reverseStr += ", " + current.element;
176+
current = current.prev;
177+
}
178+
return reverseStr.slice(1);
179+
}
180+
181+
// 实现toString方法
182+
DoubleLinkedList.prototype.toString = function () {
183+
return this.forwardString();
184+
}
185+
}

‎JavaScript/LinkedList/LinkedList.js‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
/*
2+
* 定义节点类
3+
*/
4+
function Node(element) {
5+
this.element = element;
6+
this.next = null;
7+
}
8+
9+
/*
10+
* 定义链表
11+
*/
12+
var LinkedList = function(){
13+
// 定义链表的头结点和长度属性
14+
this.head = null;
15+
this.length = 0;
16+
}
17+
// 链表尾部追加元素方法
18+
LinkedList.prototype.append = function(element) {
19+
// 根据新元素创建节点
20+
var newNode = new Node(element);
21+
22+
// 判断当前链表是否为空
23+
if(this.head === null) {
24+
this.head = newNode;
25+
} else {
26+
// 当前链表不为空
27+
var current = this.head;
28+
while(current.next) {
29+
current = current.next;
30+
}
31+
// 为最后一个节点赋值
32+
current.next = newNode;
33+
}
34+
// 最后，增加链表长度
35+
this.length++;
36+
}
37+
38+
// 根据下标插入元素
39+
LinkedList.prototype.insert = function(position, element) {
40+
// 检测越界问题: 越界插入失败
41+
if (position < 0 || position > this.length) return false;
42+
43+
var newNode = new Node(element);
44+
var current = this.head;
45+
var previous = null;
46+
var index = 0;
47+
48+
if(position === 0) {
49+
newNode.next = current;
50+
this.head = newNode;
51+
} else {
52+
while(index++ < position) {
53+
previous = current;
54+
current = current.next;
55+
}
56+
57+
newNode.next = current;
58+
previous.next = newNode;
59+
}
60+
// 最后增加长度
61+
this.length++;
62+
return true;
63+
}
64+
65+
// 根据位置移除节点
66+
LinkedList.prototype.removeAt = function (position) {
67+
// 检测越界问题: 越界移除失败, 返回null
68+
if (position < 0 || position >= this.length) return null;
69+
// 定义变量, 保存信息
70+
var current = this.head;
71+
var previous = null;
72+
var index = 0;
73+
74+
// 判断是否是移除第一项
75+
if (position === 0) {
76+
this.head = current.next;
77+
} else {
78+
while (index++ < position) {
79+
previous = current;
80+
current = current.next;
81+
}
82+
previous.next = current.next;
83+
}
84+
// 链表长度减1
85+
this.length--;
86+
// 返回移除的数据
87+
return current.element;
88+
}
89+
90+
// 查找值所对应的索引
91+
LinkedList.prototype.indexOf = function(element) {
92+
// 定义变量
93+
var current = this.head;
94+
var index = 0;
95+
96+
while(current) {
97+
if(current.element === element) {
98+
return index;
99+
}
100+
index++;
101+
current = current.next;
102+
}
103+
// 如果没有找到，返回-1
104+
return -1;
105+
}
106+
107+
// 根据元素删除信息
108+
LinkedList.prototype.remove = function(element) {
109+
var index = this.indexOf(element);
110+
return this.removeAt(index);
111+
}
112+
113+
// 判断链表是否为空
114+
LinkedList.prototype.isEmpty = function () {
115+
return this.length == 0
116+
}
117+
118+
// 获取链表的长度
119+
LinkedList.prototype.size = function () {
120+
return this.length
121+
}
122+
123+
// 获取第一个节点
124+
LinkedList.prototype.getFirst = function () {
125+
return this.head.element
126+
}
127+
128+
// 链表的toString方法
129+
LinkedList.prototype.toString = function() {
130+
var current = this.head;
131+
var str = "";
132+
while(current) {
133+
str += ", "+current.element;
134+
current = current.next;
135+
}
136+
// 返回字符串
137+
return str.slice(1);
138+
}
139+
140+
141+
module.exports = LinkedList;

‎JavaScript/LinkedList/Test.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
var LinkedList = require('./LinkedList');
2+
var DoubleLinkedList = require('./DoubleLinkedList');
3+
4+
// 测试链表
5+
var list = new LinkedList();
6+
7+
list.append(10);
8+
list.append(20);
9+
list.append(30);
10+
11+
// 输出链表
12+
console.log(list.toString());
13+
14+
list.insert(0, 10);
15+
list.insert(2, 20);
16+
list.insert(4, 30);
17+
18+
list.remove(30);
19+
console.log(list.toString());
20+
21+
// 测试双向链表
22+
var dlist = new DoubleLinkedList();
23+
24+
dlist.append(10);
25+
dlist.append(20);
26+
dlist.append(30);
27+
28+
// 输出链表
29+
console.log(dlist.toString());
30+
31+
dlist.insert(0, 10);
32+
dlist.insert(2, 20);
33+
dlist.insert(4, 30);
34+
35+
dlist.remove(30);
36+
// 逆序输出
37+
console.log(dlist.reverseString());

0 commit comments

Comments
 (0)