Новый подход для добавления нового узла в связанный список

Question

void addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    head = temp;
}

Приведенный выше код является популярной ошибочной версией функции для добавления нового узла в начало связанного списка. Как правило, правильные версии, как,

void addNewNode (struct node **head, int n);
void addNewNode (struct node * &head, int n);

Я разработал еще одну, но простую функцию, которая отлично работала.

struct node* addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    return temp;
}

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

Answer 1

Недостаток в том, что вы полагаетесь на вызывающего, чтобы выполнить последний шаг обновления указателя головы на список.

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

Answer 2

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

val ls = [1, 2, 3, 4]
val newList = 0 :: ls

Синтаксис :: на самом деле является функцией, которая принимает два параметра (0 и ls) и возвращает новый список, в котором 0 является первым элементом. Списки в ML фактически определяются как узлы списков, поэтому :: на самом деле написано очень похоже на предложенную вами функцию addNewNode.

Другими словами: поздравляю, вы создали неизменную реализацию связанного списка в C! Понимание этого на самом деле является довольно важным первым шагом к функциональным языкам, так что это действительно полезно знать.

Answer 3

Ваш подход несовместим с идеей, что addNode - это метод в списке, более часто используемый в языках OO.

Лично я думаю

list.add(element)

намного более интуитивно понятен, чем

list = add(list, element)

Десятки библиотек "коллекций" не могут ошибаться ...

Answer 4

Это не ново. Как указывает quinmars, glib делает это более 10 лет. Это отличная идея, так что поздравляю с этим.

Однако, один кроткий пример вашего кода: не приводите возвращаемое значение malloc() в C и не повторяйте имя типа при использовании sizeof Ваша строка размещения должна выглядеть следующим образом:

struct node* temp = malloc(sizeof *temp);

См? Короче, крепче, легче читать, сложнее испортить. Лучше! :)

Answer 5

Afaik, так работают списки в glib, и я уверен, что gtk не были первыми, кто использовал этот способ, поэтому я бы не назвал это новым подходом. Лично я предпочитаю иметь базовую структуру, которая содержит количество узлов, первый и последний указатель.

Answer 6

Я не вижу проблем ни в одном из упомянутых правильных кодов. Изменять или не менять голову - это вопрос дизайна - и как вернуть измененный список. Хороший интерфейс реализован в std :: list <> в качестве примера, где используется ООП, такой подход свободен от потенциальных проблем. Указатель заголовка скрыт, и вы можете изменить его, как хотите, и поскольку вызывающая сторона не хранит заголовок явно, его ссылка на список всегда правильна.

одна вещь, которая выглядит некрасиво (когда вы используете C ++, а не C) - это malloc, лучше использовать 'new'.