devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构之双链表详解_c++双向链表

作者：盐析白兔 | 2024-05-01 01:17:02

赞

踩

c++双向链表

这里头节点是不存储数据的，且单向链表的操作，双向链表都可以做到，这里讲一下双向链表的特点。

如果想看一些基础的增删改查工作，直接查看单链表即可

C++数据结构之单链表


废话不多说，直接上干货

1. 双向链表的结构定义
//定义链表
typedef struct Node{
    int data;//存放数据
    Node* pre; //指向上一个节点
    Node* next;//指向下一个节点
    Node(): data(0),pre(NULL),next(NULL){};
    Node(int x, Node* node): data(x),pre(node),next(NULL){};
    Node(int x, Node* node, Node* node2): data(x),pre(node),next(node2){};
}*ListNode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

上述定义了一个双向链表的节点，包含数据，前驱指针和后继指针。

  • 这里采用初始化列表的方式初始化Node，不仅仅是因为这样写简洁方便，而是这种方式在有些时候是比在函数体里面初始化更加的高效。
  • 使用typedef的方式在下方定义的*ListNode是一个结构体类型而不是一个变量。

这里采用了三种构造函数，包括有参的重载。

2. 建立一个线性链表

因为这里我们写了链表的一个有参构造，这样初始化链表就变得非常简单

template<typename T>
void CreateList(ListNode &link_list, T arr, int len){
    Node* p = link_list;
    for(int i=0; i<len; i++){
        p->next = new Node(arr[i], p);  //每一步都设置前驱节点
        p = p->next;
    }
}

void ShowList(const ListNode &link_list){
    Node* p = link_list->next;
    if(NULL == p) return;
    while(NULL != p->next){
        cout << p->data << "\t";
        p = p->next;
    }
    cout<<p->data << endl;
}
int main(void){

    ListNode link_list = new Node();

    vector<int> a = {1,2,3,4,5};
    CreateList(link_list, a, a.size());
    Node *p = link_list->next->next;
    cout<<p->pre->data<<endl;
    ShowList(link_list);

    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

直接调用有参构造就可以了。

添加节点

增删改查操作，单链表能做的，双向链表也能做，不过有一些区别

  • 尾部插入节点：前驱节点的后继指针指向新节点，新节点的前驱指针指向前驱节点，总计2个指针。
  • 增加中间节点：双链表在添加新节点时，如果是中间节点，那么需要修改前一个节点的后继指针，后一个节点的前驱指针，以及新节点的前后指针，总计4个指针。
//插入尾部节点
void InsertRear(ListNode &link_list, int val){
    Node *p = link_list;
    while(NULL != p->next){
        p = p->next;
    }
    p->next = new Node(val, p);
}

//插入中间节点
void InsertInside(ListNode &link_list,int index, int val){
    int count = 0;
    Node *p = link_list;
    while(NULL != p->next){
        if(count == index){
            Node *temp = new Node(val, p); //新节点的前驱指针指向p
            temp->next = p->next; //新节点的后继指针指向后一个节点
            p->next->pre = temp; //后继节点的前驱指针指向新节点
            p->next = temp; //前驱节点的后继指针指向新节点
            return;
        }
        p = p->next;
        count++;
    }
    cout<<"插入失败"<<endl;
}

  • 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
删除节点
  • 删除尾部元素：修改前驱节点的后继指针即可
  • 删除中间元素：删除中间节点，需要修改前一个节点的后继指针，后一个节点的前驱指针，总计2个指针。
void RemoveRear(ListNode &link_list){
    Node *p = link_list->next;
    if(NULL == p){
        cout << "链表为空" << endl;
        return;
    }else if(NULL == p->next){
        delete p;
        link_list->next = NULL;
    }
    while(NULL != p->next->next){
        p = p->next;
    }
    delete p->next;
    p->next = NULL;
}

void RemoveInside(ListNode &link_list, int index){
    
    Node *p = link_list;
    if(NULL == p->next){
        cout << "链表为空" << endl;
        return;
    }
    int count = 0;
    while(NULL != p->next->next){
        if(count == index){
            Node* temp = p->next->next; //得到后继节点
            temp->pre = p; //修改后继节点的前驱指针
            delete p->next; //删除节点
            p->next = temp; //修改前驱节点的后继指针
            return;
        }
        p = p->next;
        count++;
    }
    cout << "index 超出索引" << endl;
}

  • 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

双向链表麻烦的地方就在于指针的指向操纵要更加的复杂一点，但是同样灵活性也更加的好一些。

查看节点
Node* FindNode(const ListNode &link_list, int val){
    Node *p = link_list->next;
    while(NULL != p){
        if(p->data == val) return p;
        p = p->next;
    }
    return NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

这个和单链表是一样的

修改节点
void ChangeNode(ListNode &link_list,int index, int val){
    int count = 0;
    Node *p = link_list->next;
    if(NULL == p){
        cout << "链表为空" << endl;
        return;
    }
    while(NULL != p->next){
        if(count == index){
            p->data = val;
            return;
        }
        p = p->next;
        count++;
    }
    cout<<"修改失败"<<endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
总结

具体的问题需要具体的分析，目前还没遇到过什么问题使用双链表才是妙手的情况，所以这里暂时就介绍基础的操作。


老规矩，有用，希望能送上你的二连，感谢！

附录

全部代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>

using namespace std;

//定义链表
typedef struct Node{
    int data;//存放数据
    Node* pre; //指向上一个节点
    Node* next;//指向下一个节点
    Node(): data(0),pre(NULL),next(NULL){};
    Node(int x, Node* node): data(x),pre(node),next(NULL){};
    Node(int x, Node* node, Node* node2): data(x),pre(node),next(node2){};
}*ListNode;

template<typename T>
void CreateList(ListNode &link_list, T arr, int len){
    Node* p = link_list;
    for(int i=0; i<len; i++){
        p->next = new Node(arr[i], p);
        p = p->next;
    }
}

void ShowList(const ListNode &link_list){
    Node* p = link_list->next;
    if(NULL == p) return;
    while(NULL != p->next){
        cout << p->data << "\t";
        p = p->next;
    }
    cout<<p->data << endl;
}

Node* FindNode(const ListNode &link_list, int val){
    Node *p = link_list->next;
    while(NULL != p){
        if(p->data == val) return p;
        p = p->next;
    }
    return NULL;
}

void InsertRear(ListNode &link_list, int val){
    Node *p = link_list;
    while(NULL != p->next){
        p = p->next;
    }
    p->next = new Node(val, p);
}

void InsertInside(ListNode &link_list,int index, int val){
    int count = 0;
    Node *p = link_list;
    while(NULL != p->next){
        if(count == index){
            Node *temp = new Node(val, p); //新节点的前驱指针指向p
            temp->next = p->next; //新节点的后继指针指向后一个节点
            p->next->pre = temp; //后继节点的前驱指针指向新节点
            p->next = temp; //前驱节点的后继指针指向新节点
            return;
        }
        p = p->next;
        count++;
    }
    cout<<"插入失败"<<endl;
}

void ChangeNode(ListNode &link_list,int index, int val){
    int count = 0;
    Node *p = link_list->next;
    if(NULL == p){
        cout << "链表为空" << endl;
        return;
    }
    while(NULL != p->next){
        if(count == index){
            p->data = val;
            return;
        }
        p = p->next;
        count++;
    }
    cout<<"修改失败"<<endl;
}

void RemoveRear(ListNode &link_list){
    Node *p = link_list->next;
    if(NULL == p){
        cout << "链表为空" << endl;
        return;
    }else if(NULL == p->next){
        delete p;
        link_list->next = NULL;
    }
    while(NULL != p->next->next){
        p = p->next;
    }
    delete p->next;
    p->next = NULL;
}

void RemoveInside(ListNode &link_list, int index){

    Node *p = link_list;
    if(NULL == p->next){
        cout << "链表为空" << endl;
        return;
    }
    int count = 0;
    while(NULL != p->next->next){
        if(count == index){
            Node* temp = p->next->next; //得到后继节点
            temp->pre = p; //修改后继节点的前驱指针
            delete p->next; //删除节点
            p->next = temp; //修改前驱节点的后继指针
            return;
        }
        p = p->next;
        count++;
    }
    cout << "index 超出索引" << endl;
}


int main(void){

    ListNode link_list = new Node();

    vector<int> a = {1,2,3,4,5};
    CreateList(link_list, a, a.size());
    Node *p = link_list->next->next;
    cout<<p->pre->data<<endl;
    ShowList(link_list);

    InsertInside(link_list, 0, 100);
    ShowList(link_list);

    InsertInside(link_list, 6, 100);
    ShowList(link_list);

    InsertRear(link_list, 100);
    ShowList(link_list);

    InsertInside(link_list, 2, 100);
    ShowList(link_list);

    RemoveRear(link_list);
    ShowList(link_list);

    RemoveInside(link_list, 6);
    ShowList(link_list);

    Node *temp = FindNode(link_list, 100);
    cout << temp->data << endl;

    ChangeNode(link_list, 0, 1000);
    ShowList(link_list);

    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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/516246
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号