Удаление пользовательского двусвязного списка

Question

Свойство списка: один указатель указывает на следующий узел, а другой - на любой произвольный узел в списке.

Состав

struct node
{
    int val;
    node* link[2];
    node(int x);
    ~node();
};
node :: node(int x)
{
    val = x;
    link[0] = NULL;
    link[1] = NULL;
}
node :: ~node()
    {
        delete(link[0]);
        delete(link[1]);
    }

Учебный класс

class List
{
    node *head, *cloneHead;
    node *stack[100];
    int childIndex[2][100];
    int stptr;
public:
    List();
    ~List();
    void createList(int[] , int[][2], int );
    int createListStruct(node*);
    void createCloneList();
    void clone();
    void printClone();
};

Создание списка

void List::createList(int a[], int child[][2], int size)
{
    node* linkedList[size];
    for(int i=0;i<size;i++)
    {
        linkedList[i] = new node(a[i]);
    }
    head = linkedList[0];
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<2;j++)
        {
            if(child[i][j]!=-1)
            {
                linkedList[i]->link[j] = linkedList[child[i][j]];
            }
        }
    }
}

Главный

int main()
{
    int a[]={10,1,3,7,2,8,20};
    int child[][2] = {{1,4},{1,2},{3,-1},{6,5},{6,5},{-1,0},{5,5}};
    int size = sizeof(a)/sizeof(a[0]);
    List L;
    L.createList(a,child,size);
    L.clone();
    L.printClone();
    return 0;
}

в нормальных условиях деструктор работает отлично, но для списка с вышеупомянутым свойством List его сбой

например:

Узел: 1

Ссылка 1: Узел 2

Ссылка 2: Узел 3

Узел: 2

Ссылка 1: Узел 3

Ссылка 2: Узел 1

в вышеприведенном случае к тому времени, когда деструктор достигнет Link2 Node2, который указывает на узел 1, узел 1 уже удален, поэтому код выдает ошибку сегментации.

Я придумал: иметь массив уникальных узлов в списке и удалять по одному

Есть ли другой способ сделать это?

Answer 1

2 альтернативы вашему списку идей (которые кажутся нормальными)

1. Для каждого узла ведите список родителей. Когда узел удаляется, установите для всех родителей указатели на этот узел, чтобы nullptr, Вы можете безопасно удалить nullptr так часто, как вам нравится.

2. Если ваш график представляет собой дерево (т.е. без циклов), вы можете использовать подсчет ссылок, используя либо общие указатели, либо unique_pointers

Answer 2

Вы можете использовать shared_ptr, и они освободят память, когда последний указатель будет уничтожен или переназначен. Единственное, что вам нужно помнить, - это избегать циклов, поэтому для произвольного узла используйте вместо этого слабый_птр.

struct node; // forward declaration

struct node
{
    int val;
    shared_ptr<node> next;
    weak_ptr<node> other;
};