用c++实现单向链表和双向链表

骑猪看日落 2022-07-24 11:04 200阅读 0赞

链表是一种非常基础的数据结构，本身也比较灵活，突破了数组在一开始就要确定长度的限制，能够做到随时使用随时分配内存。同时还有添加，删除，查找等功能。

总的来说，链表是由几个模块构成的。  
一，单向链表

//链表基本元素

struct Node
    {
        int num;
        Node * next;
    };

//创建节点

Node * current=nullptr;
        Node * head=nullptr;//用以存放第一个节点,有了这么一个首节点后就相当于有了一个基点
        Node * pre=nullptr;
        int n;
        while (cin >> n, n != -1)//输入-1时结束创建链表
        {
            current = new Node;
            current->next = nullptr;
            current->num = n;
            if (head == nullptr)
                head = current;
            else
                pre->next = current;
            pre = current;
        }

//遍历节点

current = head;
        while (current != nullptr)
        {
            cout << current->num << endl;
            current = current->next;
        }

//删除节点

current = head;
        while (current != nullptr)
        {
            Node * temp;//如果先释放了current，那么current将无法指向它的下一个节点
            temp = current;
            delete temp;
            current = current->next;
        }

二，双向链表  
双向链表相对于单向链表来说更为灵活方便，且实现起来也不是很难，在单向链表的基础上加上previous的指针就行了。  
//基本元素

struct Node
    {
    int num;
    Node * next;
    Node * pre;
    };

//具体实现

node * head=nullptr;
    node * current=nullptr;
    node * pre=nullptr;
    while (cin >> n, n != -1)
    {
    current = new node;//先申请一块内存用以存放新的节点
    current->next = nullptr;
    current->pre = nullptr;
    current->num = n;
    if (head == nullptr)
    head = current;//指针本质也不过是一种变量而已
    else
    {
    current->pre = pre;
    pre->next = current;
    }
    pre = current;//这里没有写成 current=current->next（之前就有犯了这种错），否则之后申请了新的内存之后指向就发生错误了
    }
    current->next = head;
    head->pre = current;
    current = head->pre;
    while (current != head)
    {
    cout << current->num << endl;
    current = current->pre;
    }
    
    current = head;
    //int count = 0;
    while (current != nullptr)
    {
    node * temp;
    temp = current;
    current = current->next;
    delete temp;
    //cout << ++count << endl;
    }

以上只是链表的基本实现，关于如何实现其他一些功能，我们以后再谈。