Небольшая путаница со связанными списками в C

Question

Я читаю о связанных списках и их реализации на C в Википедии .Я не воспринял их так быстро, как другие концепции C.

В функции list_add() мне интересно, почему она говорит ...

n->next = *p; /* the previous element (*p) now becomes the "next" element */

Не знаюдействительно понимаю комментарий.Почему предыдущий элемент станет следующим?Разве новый узел не должен становиться следующим на старом узле?

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

Спасибо.

Обновление

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

Answer 1

Поскольку список является односвязным, что означает, что он идет A->B->C->etc, он должен будет перебрать весь список, чтобы добавить новый элемент в конце.

Вместо этого он добавляет новый элемент n в начале и указывает n->next на предыдущий первый элемент p.

Answer 2

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

Answer 3

Функция list_add не обязательно добавляет новый узел в начало списка - она ​​просто добавляет новый узел, который будет расположен до p.

Аргумент p может косвенно указывать на узел в начале списка или любой другой узел в списке.

Этот код затем создает новый узел с полем next, на которое указывает p.

Обновлено:

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

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

..., что означает, что add_node вставит новый узел в начало списка,Но p может также косвенно указывать на другие узлы в списке:

В этом втором примере add_node вставит новый узел между первым и вторым узлами всписок.

Answer 4

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

Общий способ добавления нового узла в начале списка:

// allocate new node pointed by new_node and fill it.

// make new node the first node by making it's next point to current head.
new_node->next = head; 

// head should always point to the beginning of the list.
head = new_node; 

Answer 5

Функция list_add получает p, который является указателем на ссылку (также указатель), который указывает на элемент, перед которым нам нужно вставить новые данные. n - это недавно выделенный узел, поэтому n->next = *p; в основном говорит, что «следующая ссылка нового узла настроена так, чтобы указывать узел, указанный *p».

... [data, next]    >[data, next]   > >[data, next] ...
              |    |        ^ |    | |
               ----         |  ---   |
                            |        |
[p] ------------------------         |
[n] ------> [data, next]             |
                     |               |
                      ---------------

(мы устанавливаем последнюю ссылку, начиная с [n] -> [... далее])

Комментарий в коде определенно сбивает с толку. Лучше было бы «установить следующий элемент списка нового элемента, чтобы он был элементом, на который указала данная ссылка». Что, безусловно, слишком многословно.

Answer 6

list_add функция добавляет элемент в начало списка.Таким образом, этот комментарий означает, что наш новый элемент (n) должен указывать на старый заголовок списка (p):

[p]->[1]->[2] + [n] ==> [n]->[p]->[1]->[2]

Новый узел должен быть следующим застарый узел, если мы добавим элемент в конец списка:

[0]->[1]->[p] + [n] ==> [0]->[1]->[p]->[n]

Answer 7

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

[0] [1] [2] + [n] = [n] [0] [1] [2]

Answer 8

В связанном списке вы можете добавить свой новый узел в любом месте. Предположим, что вы хотите добавить узел в начало связанного списка, вы можете сделать это: n-> next = start; // следующий узел нового узла указывает на первый узел start = n; // новый узел становится первым узлом У вас есть проблема с добавлением нового узла перед данным узлом

Answer 9

Поскольку вы добавляете его в индекс, он толкает «p» вверх на один узел, чтобы новый узел мог вставить его в индекс предыдущего p