Вставка в начало связанного списка?

#c #linked-list #nodes

#c #связанный список #узлы

Вопрос:

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

 typedef struct node
{
  struct node *next;
  int data;
} node;

typedef struct LinkedList
{
  node *head;
  node *tail;
} LinkedList;

LinkedList *create_list(void)
{
  return calloc(1, sizeof(LinkedList));
}

node *create_node(int data)
{
  node *ptr = calloc(1, sizeof(node));
  ptr->data = data;

  return ptr;
}

void head_insert(LinkedList *list, int data) // problem
{
  node *newHead = create_node(data);
  newHead->next = list->head;
}

void print_list_helper(node *head)
{
  if (head == NULL)
    return;
  printf("%d%c", head->data, (head->next == NULL) ? 'n' : ' ');
  print_list_helper(head->next);
}

void print_list(LinkedList *list)
{
  if (list == NULL || list->head == NULL)
    return;
  print_list_helper(list->head);
}

int main(void)
{
  LinkedList *list = create_list();
  head_insert(list, 8);
  print_list(list); // print linked list function

  return 0;
}
  

Итак, я создал новый узел и установил node-> рядом с заголовком списка. Я не уверен, чего еще мне здесь не хватает. У меня есть другая функция, которая печатает списки, поэтому функция недействительна.

Комментарии:

1. node *newHead = create_node(data); newHead->next = list->head; . Как вы думаете, что происходит newHead после завершения функции? Он исчез. Ни одна / переменная больше не имеет на нее ссылки. Вам нужно так или иначе вернуть новый заголовок вызывающему.

2. Как вызываемый код head_insert() узнает о новом узле, который теперь является главой списка? Вы ведь не изменились list->head , не так ли? Тем не менее, вы должны, не так ли? Это очень распространенная проблема с кодом обработки списков. На самом деле это проще решить, поскольку у вас есть LinkedList структура. Часто люди просто используют указатели на node , и тогда вам приходится работать усерднее.

3. Впервые head_insert() list->head возникает проблема, поскольку head == NULL .

4. Вы можете извлечь выгоду из односвязного списка целых чисел (пример)

Ответ №1:

Добавьте эти строки в конец определения вашей head_insert() функции:

 if (list->head == NULL)
{
    list->tail = newHead;
}
list->head = newHead;
  

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

 void head_insert(LinkedList *list, int data)
{
  node *newHead = create_node(data);
  newHead->next = list->head;
  if (list->head == NULL)
  {
    list->tail = newHead;
  }
  list->head = newHead;
}
  

Комментарии:

1. Поскольку node *tail; используется указатель, вы должны проверить, есть ли list->head NULL перед добавлением узла, и установить list->head = list->tail = newHead; в этом случае для инициализации tail указателя.

2. @DavidC.Rankin Спасибо, я этого не заметил. Но хвост не должен постоянно изменяться. Его следует изменять, только если в качестве head / tail не было узлов. Потому что мы вставляем только в первую позицию. После первой вставки хвост всегда будет одинаковым. Я изменил свой код.

3. Я бы написал код как if (list->tail == NULL) list->tail = newHead; , проверяя и присваивая одному и тому же члену, а не тестируя head и присваивая tail . Это кажется более последовательным. Тем не менее, результат тот же.

4. @JonathanLeffler Если мы это сделаем, и каким-то образом хвост станет нулевым, следующая вставка сделает вновь вставленный узел хвостовым и приведет к несогласованности. В противном случае вы должны проверить, имеет ли значение tail значение null, и если это так, вы должны пройти по списку и добавить последний элемент в качестве хвоста.

5. Вы можете думать об этом так. tail Указатель всегда указывает на последний узел в списке. Это позволяет выполнять O (1) вставок в конце без необходимости перебора списка. Когда вставляется первый узел, оба head и tail указывают на один и тот же узел. Когда затем добавляется следующий узел, вы делаете tail->next = newnode; tail = newnode; это при добавлении нового заголовка, если head нет NULL , то newnode->next = head; head = newnode; в этом случае tail он не изменяется. Взгляните на ссылку в моем комментарии под исходным вопросом.