c++ - 如何用本地声明的头制作链表？

Question

在使用全局指针作为列表的标题之前，我需要制作一个连接两个链接列表的程序，但是现在我需要在本地进行创建，以便可以向其中的每个元素插入新的元素(节点)，但是我遇到了问题使用双指针，不确定何时使用**，何时使用*和何时使用。我可以找到任何类似的例子。
下面是我现在所拥有的。

#include<stdio.h>
#include<stdlib.h>

typedef struct element_{
    int x;
    struct element_ *next;
}element;


void insert(element **head, int x) {
    element *new_ = new element;
    element *p;
    new_->x = x;
    new_->next = NULL;

    if (head == NULL) {
        *head = new_;
        return;
    }
    else {
        for (p = *head;p->next != NULL;p = p->next) {}
        p->next = new_;
    }

}


int main(){
    element **head = NULL;

    insert(head,1);
    insert(head,3);
    insert(head,3);
    insert(head,4);

    for (element *p = *head;p != NULL;p = p->next){
        printf("%d ", p->x);
    }


}

Answer 1

除了运算符new之外，程序中的C++没有其他功能。因此，如果用运算符new代替malloc的调用，那么您将获得一个纯C程序。

因此，可以将C语言函数insert定义为

void insert(element **head, int x) 
{
    element *new_ = new element;

    new_->x = x;
    new_->next = NULL;

    while ( *head != NULL )
    {
        head = &( *head )->next;
    }

    *head = new_;
}

而且主要你应该写

element *head = NULL;

insert( &head, 1 );
insert( &head, 3 );
insert( &head, 3 );
insert( &head, 4 );

for (element *p = head; p != NULL; p = p->next )
{
    printf("%d ", p->x);
}

可以通过以下方式定义类似于C++函数 insert的内容

void insert( element * &head, int x ) 
{
    element *new_ = new element { x, nullptr };

    element **current = &head;

    while ( *current != NULL )
    {
        current = &( *current )->next;
    }

    *current = new_;
}

而且主要你应该写

element *head = nullptr;

insert( head, 1 );
insert( head, 3 );
insert( head, 3 );
insert( head, 4 );

for (element *p = head; p != nullptr; p = p->next )
{
    std::cout << p->x << ' ';
}

但是要将程序确实称为C++程序，则应将列表定义为一个类。此外，如果将新节点附加到单链接列表的末尾，则应将列表定义为单链接双面列表。

这是一个演示程序。

#include <iostream>
#include <functional>

class List
{
private:    
    struct Node
    {
        int data;
        Node *next;
    } *head = nullptr, *tail = nullptr;

public:
    List() = default;
    List( const List & ) = delete;
    List & operator =( const List & ) = delete;
    ~List()
    {
        clear();
    }

    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }

        tail = head;
    }

    void  push_front( int data ) 
    {
        head = new Node { data, head };
        if ( !tail ) tail = head;
    }       

    void  push_back( int data ) 
    {
        Node *node = new Node { data, nullptr };

        if ( tail )
        {
            tail = tail->next = node;
        }
        else
        {
            head = tail = node;
        }
    }       

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            std::cout << current->data << " -> ";
        }

        return std::cout << "null";
    }
};


int main()
{
    List list;

    list.push_back( 1 );
    list.push_back( 3 );
    list.push_back( 3 );
    list.push_back( 4 );

    std::cout << list << '\n';
} 

它的输出是

1 -> 3 -> 3 -> 4 -> null