【C++】双向链表_c++双向链表

---

前言：

前面我们实现了 单向链表 ，也发现了它的一些局限性。

比如说：
$\bullet$ 查找方向只能是单向的，每次只能从头查到尾
$\bullet$ 对于删除操作，它必须借助辅助节点帮助进行删除

所以为了克服这些缺点，我们引出了双向链表。

---

一.基本介绍

双向链表它的方向是双向的，相对于单向链表它可以实现自我删除。

双向链表的节点包含三个量，首先一个还是节点信息data，还有指向下一个节点地址的next指针，最后添加了指向前一个节点地址的pre指针。

---

实现思路：

$\bullet$ 还是使用之前单链表使用的学生类进行举例，只是在Node节点类新增了pre指针。

$\bullet$ 实现操作包括增删查改以及正反打印链表、返回链表长度等

$\bullet$ 新增函数注意前后进行链接，查找、修改函数不变，删除函数可以自身进行删除，操作如下：node->pre->next=node->next,node->next->pre=node->pre;

$\bullet$其他函数实现见下面具体代码。

二.代码实现

#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;

//学生节点
class Node
{
    private:
        //将信息设置为私有变量更加安全，需要专门接口函数进行查询
        string id;  //学号
        string name;  //姓名
    public:
        Node* next;
        Node* pre;
        //构造函数
        Node(string id1,string name1,Node* nextval=NULL,Node* preval=NULL)
        {
            id=id1;
            name=name1;
            next=nextval;
            pre=preval;
        }
        Node(Node* nextval=NULL,Node* preval=NULL)
        {
            next=nextval;
            pre=preval;
        }
        string getId()
        {
            return this->id;
        }
        string getName()
        {
            return this->name;
        }
        void setName(string s)
        {
            this->name=s;
        }
        void print()
        {
            cout<<"Node{id = "<<this->id<<",  name = "<<this->name<<"}"<<endl;
        }
};

//链表类
class DoubleLink
{
    private:
        //头结点
        Node* Head = new Node();
    public:
        //添加节点
        void add(Node* node)
        {
            Node* temp = Head;
            while(true)
            {
                if(temp->next==NULL)
                {
                    break;
                }
                temp = temp->next;
            } 
            //双向链接
            temp->next=node;
            node->pre=temp;
        }

        //删除指定学号学生
        void del(string s)
        {
            Node* temp=Head->next;
            if(temp->next==NULL)
            {
                cout<<"The list is empty!"<<endl;
                return ;
            }

            int flag=0;
            while(true)
            {
                if(temp==NULL)
                {
                    break;
                }
                if(temp->getId()==s)
                {
                    flag=1;
                    break;                    
                }
                temp=temp->next;
            }

            if(!flag)
            {
                cout<<"No match found!"<<endl;
                return ;
            }

            //如果temp是不是最后一个，才可以执行该操作
            if(temp->next!=NULL)
            {
                temp->next->pre=temp->pre;
            }
            temp->pre->next=temp->next;
        }

        //查找指定学号学生
        void find(string s)
        {
            if(Head->next==NULL)
            {
                cout<<"The list is empty!"<<endl;
                return ;
            }
            Node* temp=Head;
            int flag = 0;
            while(temp)
            {
                if(temp->next==NULL)
                {
                    break;
                }
                if(temp->next->getId()==s)
                {
                    flag=1;
                    break;
                }
                temp=temp->next;
            }
            if(!flag)
            {
                cout<<"This student is not exist!"<<endl;
                return ;
            }
            cout<<"This student is exist! His/Her name is "<<temp->getName()<<endl;
        }

        //修改指定学生信息
        void update(Node* newnode)
        {
            if(Head->next==NULL)
            {
                cout<<"The list is empty!"<<endl;
                return ;
            }
            Node* temp=Head;
            int flag = 0;
            while(temp)
            {
                if(temp->next==NULL)
                {
                    break;
                }
                if(temp->next->getId()==newnode->getId())
                {
                    flag=1;
                    break;
                }
                temp=temp->next;
            }
            if(!flag)
            {
                cout<<"This student is not exist!"<<endl;
                return ;
            }
            temp->next->setName(newnode->getName());
        }
        //正向打印链表所有节点信息
        void list()
        {
            if(Head->next==NULL)
            {
                cout<<"The list is empty!"<<endl;
                return ;
            }
            Node * temp=Head->next;
            cout<<"list:"<<endl;
            while(temp)
            {
                temp->print();
                temp=temp->next;
            }
        }
        //反向打印链表所有节点信息
        void traverseList()
        {
            if(Head->next==NULL)
            {
                cout<<"The list is empty!"<<endl;
                return ;
            }
            Node * temp=Head->next;
            cout<<"traverseList:"<<endl;
            //找到最后一个节点
            while(1)
            {
                if(temp->next==NULL)
                {
                    break;
                }
                temp=temp->next;
            }
            //反向打印
            while(temp!=Head)
            {
                temp->print();
                temp=temp->pre;
            }
        }

};

int main()
{
    Node* stu1 = new Node("202100","amy");
    Node* stu2 = new Node("202101","Jone");
    Node* stu3 = new Node("202102","Mike");
    Node* stu4 = new Node("202103","Hone");
    Node* newnode = new Node("202103","timi");

    DoubleLink link=DoubleLink();
    link.add(stu1);
    link.add(stu2);
    link.add(stu3);
    link.add(stu4);
    link.del("202100");
    link.find("202102");
    link.update(newnode);

    link.list();
    link.traverseList();

    system("pause");
    return 0;

}
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239

三.结果展示