C++ 模板实现—双向链表： doubly linked list

模板类—双向链表： doubly linked list

在循环链表中，从任意一个结点除法可以扫描到其他结点，但要找到其前序结点，则需要遍历整个循环链表。

双向链表

在单链表的基础上设置一个指向其前驱结点的指针域，这样就形成了双链表

1. 其中data为数据域
2. pre为前驱指针域，存放该结点的前驱结点地址
3. next为后继指针域，存放该结点后继结点的地址

顺序表和链表的比较

1. 元素的随机访问：顺序表>链表
2. 元素的插入和删除：链表>顺序表
3. 顺序表需要提前分配空间
4. 链表不需要提前分配空间-只要能够向内存中申请就可以

双链表的声明

//
// Created by HANWENKE on 2022/8/27.
//

#ifndef DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H

#endif //DOUBLY_LINKED_LIST_DOUBLY_LINKED_LIST_H
#include 
#include 
#include 
using  namespace  std;
template <class  _Ty>
struct Node{
    _Ty data;
    Node<_Ty> *next;
    Node<_Ty> *pre;
};
template <class _Ty>
class Doubly_Linked_List{
private:
    Node<_Ty> *head;//链表的头指针
public:
    Doubly_Linked_List();//无参构造
    Doubly_Linked_List(const _Ty *const &a, int n);//有参构造,建立有n个元素的单链表
    ~Doubly_Linked_List();//析构函数
    int length();//求单链表的长度
    Node<_Ty>* Get(int t);//按位置查找，在双链表中查找第i个结点
    int Locate(const _Ty &x);//按值查找。在单链表中查找值为x的元素序号
    void Insert(int i,const _Ty &x);//插入操作，在第i个位置后插入元素值为x的结点
    void Delete(int i);//删除单链表中第i个结点
    void Print();//遍历操作，按序号输出各个元素
};


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

双向链表的实现

//
// Created by HANWENKE on 2022/8/27.
//

#include "doubly_linked_list.h"

template<class _Ty>
Doubly_Linked_List<_Ty>::Doubly_Linked_List() {
    head=new Node<_Ty>;
    head->next= nullptr;
    head->pre= nullptr;
}

template<class _Ty>
//双向链表--头插有参构造
Doubly_Linked_List<_Ty>::Doubly_Linked_List( const _Ty *const &a, int n) {
    head=new Node<_Ty>;
    head->next= nullptr;
    head->pre= nullptr;
    for(int i=0;i<n;i++){
        if(head->next== nullptr){
            auto *s=new Node<_Ty>;
            s->data=a[i];
            s->pre=head;
            s->next=head->next;
            head->next=s;
        }else{
            auto *s=new Node<_Ty>;
            s->data=a[i];
            s->pre=head;
            s->next=head->next;
            head->next->pre=s;
            head->next=s;
        }
    }
}

template<class _Ty>
Doubly_Linked_List<_Ty>::~Doubly_Linked_List() {
    Node<_Ty> *p=head->next;
    Node<_Ty> *q=p;
    while(p){
        q=p->next;
        delete p;
        p=q->next;
    }
    delete head;
    p= nullptr;
    q= nullptr;
    head= nullptr;
}

template<class _Ty>
int Doubly_Linked_List<_Ty>::length() {
    Node<_Ty> *p;
    p=head->next;
    int count=0;
    while (p){
        ++count;
        p=p->next;
    }
    return count;
}
template<class _Ty>
//按位置查找
Node<_Ty>* Doubly_Linked_List<_Ty>::Get(int t) {
    Node<_Ty> *p=head->next;
    int count=1;
    while(p&&count<t){
        p=p->next;
        count++;
    }
    if (p == nullptr){
        cout<<"位置异常"<<endl;
        return nullptr;
    }
    else
        return p;

}
//按值查找--如果找到返回元素的序号，如果查找不成功返回0表示失败
template<class _Ty>
int Doubly_Linked_List<_Ty>::Locate(const _Ty &x) {
    Node<_Ty> *p=head->next;
    int count=1;
    while(p){
        if(p->data==x) return count;
        p=p->next;
        count++;
    }
    return 0;
}

template<class _Ty>
void Doubly_Linked_List<_Ty>::Insert(int i, const _Ty &x) {
    Node<_Ty> *temp= Get(i);
    auto *newNode=new Node<_Ty>;
    newNode->data=x;
    newNode->pre=temp;
    newNode->next=temp->next;
    temp->next->pre=newNode;
    temp->next=newNode;

}

template<class _Ty>
void  Doubly_Linked_List<_Ty>::Delete(int i) {
    if(i<0||i>length()){
        cout<<"删除位置不合法"<<endl;
        return;
    }
    auto temp= Get(i);
    temp->pre->next=temp->next;
    temp->next->pre=temp->pre;
    delete temp;
    temp= nullptr;
}

template<class _Ty>
/*遍历操作：
 * 临时结点指向第一个结点
 * 重复执行以下操作，直到p为空：
 *  输出结点p的数据域
 *  指针后移*/
void Doubly_Linked_List<_Ty>::Print() {
    Node<_Ty> *p=head->next;
    while(p!= nullptr){
        cout<<p->data<<"  ";
        p=p->next;
    }
    cout<<endl;
}
int main(){
    vector<char>res(20);
    for (int i = 0; i < res.size(); i++)
        res[i]=i+'A';

    Doubly_Linked_List<char> l(&res[0],res.size());
    l.Print();
    cout<<l.length()<<endl;

    //cout<data<

    l.Insert(0,'W');
    l.Print();
    l.Delete(3);
    l.Print();
    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