Doubly Linked Lists

初识

双向链表原理和单链表时一样的,也是由节点组成,每个节点包含要存储的数据信息和前后节点[单链表只有后面节点的信息]的位置信息,这些节点串连,形成一个链表。

实现
doublyLLst.h
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

//
// Created by shensir on 17-4-25.
//

#ifndef CPPPROJECTS_DOUBLYLLST_H
#define CPPPROJECTS_DOUBLYLLST_H

#include <iostream>

template <class T>
class Node{
public:
T info;
Node* next, *prev;

Node(){
next = prev = 0;
}

Node(const T& el ,Node* n = 0, Node* p = 0){
info = el; next = n; prev = p;
}
};



template <class T>
class DoublyLinkedList{

protected:
Node<T> *head, *tail;

public:
DoublyLinkedList(){
head = tail = 0;
}

void addToDLLTail(const T&);
void addToDLLHead(const T&);
T deleteFromDLLTail();
T deleteFromDLLHead();
void deleteNodeFromEl(T el);
void deleteNodeFromPs(int pos);
void addToDLList(const T& el, int pos);
bool isInList(T el);
void printLinkedLists();


};

template <class T>
void DoublyLinkedList<T>::addToDLLTail(const T &el ) {
if(tail != 0){
tail = new Node<T>(el, 0, tail);
tail->prev->next = tail;
}
else head = tail = new Node<T>(el);
}



template <class T>
void DoublyLinkedList<T>::addToDLLHead(const T &el ) {
if(head != 0){
head = new Node<T>(el, head, 0);
head->next->prev = head;
}
else head = tail = new Node<T>(el);
}



template <class T>
T DoublyLinkedList<T>::deleteFromDLLHead() {
T el = head->info;
if(head == tail){ // if only one node in the list
delete head;
head = tail =0;
}
else{ // if more than one node in the list
head = head->next; // 先将head后移
delete head->prev; // 删除旧head
head->prev = 0; // 新head's prev 设置为0
}
return el;
}




template <class T>
T DoublyLinkedList<T>::deleteFromDLLTail() {
T el = tail->info;
if(head == tail){ // if only one node in the list
delete head;
head = tail =0;
}
else{ // if more than one node in the list
tail = tail->prev;
delete tail->next;
tail->next = 0;
}
return el;
}


template <class T>
void DoublyLinkedList<T>::deleteNodeFromEl(T el) {
if(head != 0){
if(el == head->info && head==tail){
delete head;
head = tail = 0;
}
else if(el == head->info){
deleteFromDLLHead();
}
else{
Node<T>* tmp, *pred;
for(pred = head, tmp = head->next; tmp!=0 && !(tmp->info == el);
pred = pred->next, tmp = tmp->next); // and a non-head node is deleted
if(tmp != 0){
pred->next =tmp->next;
tmp->next->prev = pred;
delete tmp;

}
}
}
}


template <class T>
void DoublyLinkedList<T>::deleteNodeFromPs(int pos) {
if(pos == 1)
deleteFromDLLHead();
else if(pos == -1)
deleteFromDLLTail();
else{
Node<T> *tmp = head->next;
Node<T> *pred = head;
for(int i=0;i < pos - 2;
i++, pred = pred->next, tmp = tmp->next);

pred->next = tmp->next;
if(tmp->next != 0) // 如果删除的不是最后一个节点,那么要与前面的节点连接[只在双向链表有]
tmp->next->prev = pred;

delete tmp;

}

}




template <class T>
void DoublyLinkedList<T>::addToDLList(const T&el, int pos) {
if(pos == 1)
addToDLLHead(el);
else if(pos == -1)
addToDLLTail(el);
else{
Node<T> *tmp = head->next;
Node<T> *pred = head;
for(int i=0;i < pos - 2;
i++, pred = pred->next, tmp = tmp->next);

Node<T>* psNode = new Node<T>(el, tmp, pred);
tmp->prev = psNode;
pred->next = psNode;

}
}


template <class T>
bool DoublyLinkedList<T>::isInList(T el) {
Node<T>* tmp;
for(tmp=head; tmp != 0 && el != tmp->info; tmp = tmp->next);
return tmp != 0;
}


// print the singly linked lists
template <class T>
void DoublyLinkedList<T>::printLinkedLists(){
Node<T>* p = head;
while(p != 0){
printf("%d\n", p->info);
p = p->next;
}
}


#endif //CPPPROJECTS_DOUBLYLLST_H


main.cpp
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

#include <iostream>
#include "doublyLLst.h"

int main(){

DoublyLinkedList<int> list;
list.addToDLLTail(11);
list.addToDLLTail(12);
list.addToDLLTail(13);
list.addToDLLHead(10);


list.printLinkedLists();

list.deleteFromDLLHead();
printf("after the deleting from head...\n");
list.printLinkedLists();

printf("after the deleting from el:12...\n");
list.deleteNodeFromEl(12);
list.printLinkedLists();

printf("after the deleting from ps:2...\n");
list.deleteNodeFromPs(2);
list.printLinkedLists();

printf("after the adding from ps:1...\n");
list.addToDLList(6, 1);
list.printLinkedLists();

bool isin = list.isInList(6);

std::cout<<"Is 6 in list? The answer is: "<<isin<<std::endl;
return 0;
}


输出:

10
11
12
13
after the deleting from head…
11
12
13
after the deleting from el:12…
11
13
after the deleting from ps:2…
11
after the adding from ps:1…
6
11
Is 6 in list? The answer is: 1

注意

此处用到模板,其声明的函数一般要在当前的头文件进行定义。当然,非要分到对应的cpp文件[例如doublyLLst.cpp]也行,只不过,这时候调用这些函数的话,要在main.cpp上面添加一句include "doublyLLst.cpp"

参考

stackoverflow
Data Structures and Algorithms in C++

本文标题:Doubly Linked Lists

文章作者:不秩稚童

发布时间:2017年04月25日 - 13:53:46

最后更新:2017年04月25日 - 14:06:15

原始链接:http://datahonor.com/2017/04/25/Doubly-Linked-Lists/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇