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

Question

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

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

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

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

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

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, его имя в структуре полезной нагрузки и типструктуры полезной нагрузки (макрос list_entry ()).

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

Редактировать: Подводя итог, я увидел два важных для меня ответа:

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Следовательно, самое простое и простое решение - второе.

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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