Уничтожается ли выделение памяти с помощью malloc() внутри цикла при выходе из цикла?

Ладно, есть над чем подумать конструктивно. У вас есть основная идея, всего несколько вещей, которые помогут прояснить ситуацию в вашей голове.

Узел

«Узел» должен быть очень простым классом. Идея сеттеров и геттеров хороша, но они обычно нужны вам только тогда, когда их изменение требует включения функциональности, влияющей на другие части класса. В случае узла в связанном списке сам узел не должен быть общедоступным, поэтому никакие сеттеры или геттеры действительно не нужны:

struct node
{
  int    value;
  node * next;
};

Но если вы действительно хотите добавить сеттеры и геттеры, также рекомендуется быть осторожным со своим словарным запасом. «Адрес» — это значение, хранящееся в указателе. Вы не сохраняете какой-либо старый адрес, вы сохраняете адрес следующего узла, который мы можем сократить до «nextNode» (или нет: «nextNode» тоже подойдет).

В любом случае старайтесь придерживаться одного и того же словарного слова при обращении с предметом:

class node
{
  int    _value;
  node * _next;

public:
  int    getValue() const { return _value; }
  void   setValue( int value ) { _value = value; }
  node * getNext() const { return _next; }
  void   setNext( node * next ) { _next = next; }
};

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

Имена

Обратите также внимание, что я не написал имя класса с заглавной буквы. Можно, конечно, но тогда будьте последовательны: (Node и LinkedList) или (node и linkedList).

^{⟶ I personally prefer snake_case: linked_list, but most people seem to prefer camelCase or PascalCase. Meh.}

Кроме того, вы заметите, что я добавил начальное подчеркивание к закрытым переменным-членам. Вам не обязательно это делать, но многие люди любят украшать их таким образом — это помогает вам (программисту) помнить, что это частное поле, и доступ к нему следует осуществлять только теми методами, у которых есть веские основания для прикосновения. их напрямую. Другие распространенные способы их украшения включают m_value и value_.

^{⟶ Keep in mind that leading underscores are not valid for global object names.}

Связанный список

Двусвязный список бывает двух видов:

• Указатели на головной и хвостовой узлы ссылаются на фактические головные и хвостовые узлы списка.
• Головной и хвостовой узлы (фактические объекты узлов) пусты и используются для заключения фактического списка в скобки. То есть значение head игнорируется, а его следующий указатель указывает на фактический первый узел в списке. Это происходит за счет использования большего пространства для каждого списка (за счет двух узлов с неиспользуемыми значениями), но значительно упрощает жизнь при написании кода для вставки и удаления узлов из списка.

У вас односвязный список, но ситуация меняется лишь немного. Голова по-прежнему работает так же, как и в двусвязном списке (какой бы вариант вы ни выбрали), но хвост теперь полезен только для быстрого добавления данных в список и, следовательно, всегда должен быть просто указателем на фактический последний узел. в списке независимо от того, является ли head указателем.

^{⟶ Many singly-linked lists do not have a tail pointer, since their needs only require adding a node to the head and rarely the tail. Again, use case matters!}

контейнер против хвостового/последнего узла

Поскольку указатель хвоста всегда должен указывать на фактический хвостовой узел списка, выделять container нет необходимости. Опять же, словарный запас здесь имеет значение. Ожидается, что слово «контейнер» будет относиться к структуре, управляющей всей коллекцией. (Вы уже назвали этот «linkedList».)

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

sizeOfNode - это...?

Будьте осторожны и не используйте переменные для хранения значений, которые легко получить от компилятора. Все это лишь запутывает то, что происходит на самом деле. Следовательно:

int sizeOfNode = sizeof(Node);

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

итеру не принадлежит

Слово «iter» относится к итератору, который является указателем (или притворяется им). Кроме того, сама переменная используется только в функции. Опять же, не объявляйте ничего, что не является строго необходимым для хранения данных в определении класса. Подобные переменные следует объявлять в функции, в которой они используются, как можно ближе к тому месту, где они используются.

Для простого целочисленного индекса в массиве часто используются такие имена переменных, как i и j и k и n.

Пересмотренный список

Ваш пересмотренный класс связанного списка может выглядеть так:

class linkedList
{
  node * _firstNode;  // or head or headNode etc
  node * _lastNode;   // or tail or tailNode etc
  int    _lengthOfList;

public:

  linkedList() : _firstNode{nullptr}, _lastNode{nullptr}, _lengthOfList{0} { }

  linkedList( int length, int * array )
  : _firstNode{nullptr}, _lastNode{nullptr}, _lengthOfList{0}
  {
    ...
  }

  int getLength() const { return _lengthOfList; }
};

Обратите внимание, что у нас есть конструктор по умолчанию (который просто дает вам пустой список) и конструктор, который принимает массив целых чисел для построения списка. Символ : указывает на «список инициализаторов членов», который позволяет нам легко присвоить всем объектам-членам класса начальное значение, что и должно быть. (В противном случае вам пришлось бы присвоить начальные значения непосредственно в теле конструкции, что тоже работает, но все равно, что будет плавать в вашей лодке.)

  linkedList()
  {
    _firstNode = nullptr;
    _lastNode = nullptr;
    _lengthOfList = 0;
  }

Обратите также внимание на добавление метода получения для получения текущей длины списка. Сеттера нет. Для изменения длины необходимо добавить или удалить узлы.

^{⟶ Standard C++ containers call this “size”. So you could name _lengthOfList just _size and the getter int size() const { return _size; } and everyone who reads your code will understand that it refers to the number of elements in your linked list.}

Добавление узлов в конец вашего списка

Прежде чем беспокоиться о конструкторе связанного списка массива ⟶, у вас должен быть метод простого добавления одного узла в конец списка. Что-то вроде:

class linkedList
{

public:

  ...

  void append( int value )
  {
    ...
  }

  ...
};

Этот метод должен делать не что иное, как прикреплять новый узел к концу списка. Это необходимо:

• выделите память для нового узла (используя либо malloc(), либо еще лучше, поскольку это C++, используя new)
• установите для вновь выделенного узла _value значение аргумента
• установите _nextNode вновь выделенного узла на nullptr
• установите _lastNode->_nextNode для вашего нового узла (таким образом связывая ваш узел с концом списка)
• установите _lastNode так, чтобы он указывал на новый узел (чтобы _lastNode продолжал указывать на фактический последний узел в списке)
• увеличьте _lengthOfList (чтобы сохранить точность)

Подобные вещи следует нарисовать на листе бумаги. Вам следует использовать бумагу и карандаш каждый раз, когда вы что-то делаете, чтобы связать или разъединить узлы в своем списке.

Предостережения для вашего односвязного списка:

• _firstNode может быть nullptr. Если это так, вы должны установить как его значение, так и значение _lastNode, чтобы они указывали на новый узел.
• Если _firstNode нет nullptr, вам нужно только обновить _lastNode.

Опять же, рисование этого на бумаге поможет вам увидеть эти проблемы!

Теперь, когда у вас есть функция для добавления узлов, написать конструктор связанного списка массива ⟶ очень легко:

  linkedList( int length, int * array )
  : _firstNode{nullptr}, _lastNode{nullptr}, _lengthOfList{0}
  {
    for (int n = 0;  n < length;  n++)
      append( array[n] );
  }

Это было на удивление легко, не так ли?

Последние мысли

Когда вы научитесь использовать C++ и разберетесь с подобными структурами, жизнь станет проще. Помните, всегда можно построить себе модель того, что вы пытаетесь сделать, будь то скрепки или карандаш и бумага (или что-то еще, что кажется полезным).

В данном случае самыми основными блоками связанного списка являются:

• как сохранить структуру
• добавление узла
• удаление узла
• индексирование узла

Все остальное — просто сладкий сахар, который поможет вам сделать эти вещи.

Попробую для вас обобщить:

1. malloc никогда не будет вызывать конструктор вашего класса, поскольку он в основном используется для C, а не для C++.
2. для динамического выделения экземпляров классов в C++ вы должны использовать new вместо malloc
3. выделенная память с помощью malloc или new должна быть освобождена с помощью free или delete соответственно
4. использование free никогда не вызовет деструктор вашего экземпляра

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