数据结构之双向链表

单向链表在之前的文章介绍过,但是单向链表有一个不足之处:只能从头遍历,如果想反过来,从后向前遍历却不容易。如果我们在节点新增一个指针指向前一个节点,就可以向前遍历,这样就实现了双向链表

双向节点

Node类

我们改进一下Node类,增加一个指向前一个节点的指针:

1
2
3
4
5
function Node(data) {
this.data = data;
this.next = null; // 指向下一个节点
this.previous = null; // 指向前一个节点
}

LinkList类

LinkList结构和单向链表一致,但我们需要调整一下相关方法,增加节点指向前一个节点指针的操作。

1
2
3
4
function LinkList() {
this.head = null; // 头结点
this.length = 0; // 记录节点长度
}

追加节点

追加节点是在链表尾部直接加入一个新的节点,当链表没有节点时,先需要创建一个头结点,否则就顺着节点next指针,移动到最后一个节点,将当前链表最后一个节点的next指针指向新的节点,同时将新的节点的privours指针指向当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 在链表最后添加节点
this.append = function(data) {
var node = new Node(data);
if (this.head == null) {
this.head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
node.previous = previous;
}
length++;
}

插入节点

插入节点是在指定位置插入一个新的节点,但是插入位置不能超过当前节点的长度。插入时,要需要先移动到链表指定插入位置:

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
// 指定位置插入节点
this.insert = function(pos, data) {
var node = new Node(data);

if (pos > -1 && pos < length) {
if (pos == 0) {
node.next = head;
head = node;
} else {
var current = head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

// 将上一个节点的next指针指向新节点
previous.next = node;
// 将当前插入位置节点的previous指针指向新节点
current.previous = node;
// 将新节点的next指针指向当前插入位置节点
node.next = current;
// 将新节点的previous指针指向上一个节点
node.previous = previous;
}


length++;
return true;
}
return false;
}

删除节点

删除指定位置的节点,需要先移动到指定位置的上一个节点,将上一个节点的next指针指向当前位置的下一个节点,并将当前位置的下一个节点的previous指针指向当前位置的前一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
this.removeAt = function(pos) {
if (pos > -1 && pos < length) {
var current = this.head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = current.next;
# 删除最后一个节点,则不需要设置previous
if (current.next) {
current.next.previous = previous;
}

this.length--;
return true;
}

return false;
}

完整代码

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
// 双项链表

function Node(data) {
this.data = data;
this.next = null; // 指向下一个节点
this.previous = null; // 指向前一个节点
}

function LinkList() {

head = null;

length = 0;


// 在链表最后添加节点
this.append = function(data) {
var node = new Node(data);
if (head == null) {
head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
node.previous = previous;
}
length++;
}

// 指定位置插入节点
this.insert = function(pos, data) {
var node = new Node(data);

if (pos > -1 && pos < length) {
if (pos == 0) {
node.next = head;
head = node;
} else {
var current = head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

// 将上一个节点的next指针指向新节点
previous.next = node;
// 将当前插入位置节点的previous指针指向新节点
current.previous = node;
// 将新节点的next指针指向当前插入位置节点
node.next = current;
// 将新节点的previous指针指向上一个节点
node.previous = previous;
}


length++;
return true;
}
return false;
}

this.removeAt = function(pos) {
if (pos > -1 && pos < length) {
var current = head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = current.next;

if (current.next) {
current.next.previous = previous;
}


length--;
return true;
}

return false;
}

// 从链表尾部移除节点
this.pop = function() {
var current = head;
var previous;

while (current.next) {
previous = current;
current = current.next;
}

previous.next = null;

length--;
}

// 搜索节点
this.search = function(data) {
if (data) {
var current = head;

while (current) {
if (current.data == data) {
return current;
}
current = current.next;
}

}
return null;
}

// 遍历节点
this.toString = function() {
var str = head.data;
var current = head.next;

while (current) {
str += ','+ current.data;
current = current.next;
}

return str;
}

// 获取链表长度
this.getLength = function() {
return length;
}

}
有用就打赏一下作者吧!