Почему первый узел связанного списка объявлен как указатель?

Question

Теперь я знаю, почему указатели используются для определения связанных списков. Просто потому, что структура не может иметь рекурсивного определения, и если бы не было указателей, компилятор не сможет вычислить размер структуры узла.

struct list{ 
     int data; 
     struct list* next; // this is fine 
}; 

Но путаница подкрадывается, когда я объявляю первый узел связанного списка, как:

struct list* head; 

Почему это должен быть указателем? Нельзя ли его просто объявить как

struct list head; 

и адрес этого для использования в дальнейшем? Пожалуйста, уточните мои сомнения.

Answer 1

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

У вас есть два варианта:

1. список без "фиктивной" элемента головки. В этом случае пустой список представлен нулевым в head указатель

   struct list* head = NULL; 
   

   Так это и есть ответ на ваш вопрос: мы объявим его как указатель, чтобы иметь возможность представлять пустой список, установка head указатель на нуль.

2. Список с элементом «фиктивный» элемент. В этом случае первый элемент списка не используется для хранения фактических пользовательских данных: он просто служит в качестве исходного «фиктивного» элемента списка.Он объявлен как

   struct list head = { 0 }; 
   

   выше представляет собой пустой список, так как head.next является недействительным и head самого объекта «не считается».

   I.e. вы можете заявить об этом, если хотите. Просто имейте в виду, что head на самом деле не элемент списка. Фактические элементы начинаются после head.

И, как всегда, имейте в виде, что при использовании не-динамически выделенные объектов, срок службы этих объектов регулируются обзорным правило. Если вы хотите переопределить эти правила и управлять временем жизни объектов вручную, тогда у вас нет другого выбора, кроме как распределить их динамически и, следовательно, использовать указатели.

Answer 2

Вы можете объявить список таким образом

struct list head = {}; 

Но будут какие-то трудности в реализации функций, которые имеют доступ к списку. Они должны учитывать, что первый узел не используется, поскольку другие узлы списка и элемент данных первого узла data также не используются.

Обычно список объявляется следующим образом

struct List 
{ 
    // some other stuff as for example constructors and member functions 
    struct node 
    { 
     int data; 
     struct node* next; // this is fine 
    } head; 
}; 

и

List list = {}; 

Или в C++ можно написать просто

struct List 
{ 
    // some other stuff as for example constructors and member functions 
    struct node 
    { 
     int data; 
     struct node* next; // this is fine 
    } head = nullptr; 
}; 

List list; 

Конечно, вы могли бы определить конструктор по умолчанию Перечислите себя.

В этом случае, например, проверить, является ли список пуст, достаточно, чтобы определить следующую функцию члена

struct List 
{ 
    bool empty() const { return head == nullptr; } 

    // some other stuff as for example constructors and member functions 

    struct node 
    { 
     int data; 
     struct node* next; // this is fine 
    } head; 
}; 

Answer 3

Простыми словами, если ваша голова является начальным узлом связанного списка, тогда он будет содержать только адрес первого узла, из которого будет запущен связанный список. Это делается для того, чтобы избежать путаницы для обычного программиста. Поскольку голова будет содержать только адрес, следовательно, она объявляется как указатель. Но способ, которым вы хотите объявить, также прекрасен, просто код соответственно. Совет. Если позже вы захотите внести некоторые изменения в свой связанный список, например операции удаления или вставки в начале связанного списка, вы столкнетесь с проблемами, так как вам потребуется другая переменная указателя. Поэтому лучше объявить первый узел в качестве указателя.