Два способа реализации связанного списка: что лучше?

Question

Я знаю, как правило, два способа создать общую структуру данных связанных списков в C. И мне интересно, что лучше. Прежде чем задать вопрос, я познакомлю оба методы коротко:

Один из способов заключается в создании функции вокруг структуры, как следующее:

struct list_element { 
    struct list_element *prev; 
    struct list_element *next; 
    void *data; 
}; 

Очевидно, что точки указателя данных в полезную нагрузку. Элемент struct list находится за пределами полезной нагрузки. Это, например, как glib разработал свой объект с двойным списком ссылок: http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html

Другой метод - способ, которым это делается в ядре Linux: http://isis.poly.edu/kulesh/stuff/src/klist/. Нет указателя void для полезной нагрузки в структуре элемента списка. Вместо этот элемент списка структуру входит в полезной структуре:

struct list_element { 
    struct list_element *prev; 
    struct list_element *next; 
}; 

struct person { 
    char name[20]; 
    unsigned int age; 
    struct list_element list_entry; 
}; 

специальный макрос используется для получения указателя на полезную структуру данного указатель на LIST_ENTRY, его имя жгуты на-структуру полезной нагрузки и тип payload struct (макрос list_entry()).

Обратите внимание, что здесь возник вопрос: Какое преимущество заключается в том, что последний из двух методов построения связанного списка? Несколько раз я слышал, как люди говорят, что второе является более «родовым», чем первое, но почему? Я бы даже утверждать, что первый метод более общий, потому что структуры полезной нагрузки являются агностиками реализации списка, что не соответствует второму методу.
Еще один недостаток второго метода заключается в том, что если вы хотите разместить полезную нагрузку в нескольких списках, вы должны иметь элемент struct list_element для каждого списка в структуре полезной нагрузки.

Edit: Резюмируя до сих пор я видел два ответа, которые были важны для меня:

• С первого метода: удаление полезной нагрузки из списка включает в себя цикл через весь список, пока элемент списка не указывает на полезная нагрузка найдена. Вам не нужно делать это со вторым методом. (Ответа на этот вопрос Patrick)
• С помощью первого метода вам нужно сделать два malloc() для каждого элемента: один для полезной нагрузки и один для элемента списка. При втором методе достаточно одного malloc(). (Ответ от Родди)

Answer 1

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

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

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

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

Таким образом, самым простым и простым решением является второе.

Answer 2

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

При использовании второго варианта вы всегда используете пространство (например, 20 символов для имен) независимо от фактического использования.

Answer 3

Это лошади для курсов.

Первый метод менее эффективен, так как для каждого элемента списка обычно требуется два malloc() и free() s и дополнительный указательный указатель для доступа к ним - и, конечно же, место для хранения указателя.

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

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

struct person { 
    struct list_element list_entry; 
    unsigned int age; 
    char name[20]; // now could be variable length. 
}; 

Answer 4

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

Answer 5

Второй метод - «навязчивый»; он требует изменения типа, который помещается в список. Тип в списке (или списках) должен знать, что он находится в списке. Вы должны иметь возможность изменять структуру, чтобы поместить ее в списки.

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

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

Answer 6

Я думаю, что это скорее концептуальная/аналитическая проблема. Является ли сущность, с которой вы работаете, с списком или у вас есть список экземпляров?

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

Как и в большинстве проектных решений, наиболее важные критерии должны быть более ясными и наиболее очевидными.

Answer 7

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

Для простых списков я стараюсь использовать комбинацию из двух.

struct list_node { 
    struct list_node * prev; 
    struct list_node * next; 
}; 

struct some_struct { 
    struct list_node node; 
    ... 
}; 

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

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

Надеюсь, что это поможет.

Редактировать: Исправлена ​​некоторая терминология.