Пример связанных списков — Почему они используются?
Я просматривал блок кода о том, как получить информацию об интерфейсе для Unix / iOS / Mac OS X (IP-адрес, имена интерфейсов и т. Д.), И хотел понять, почему используются связанные списки. Я не штатный программист, но я умею программировать и всегда стараюсь учиться. Я понимаю базовый C / C ++, но никогда не имел опыта и не использовал связанные списки.
Я пытаюсь изучить OS X и iOS, пытался получить информацию о сетевом интерфейсе и наткнулся на это:
https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/getifaddrs.3.html
Если я правильно понимаю, похоже, что связанный список используется для связывания нескольких структур вместе для каждого интерфейса. Почему связанный список используется в этой ситуации? Почему структуры не просто создаются и хранятся в массиве?
Спасибо
Решение
[…] и хотел понять, почему используются связанные списки. Я не штатный программист, но я умею программировать и всегда стараюсь учиться. Я понимаю базовый C / C ++, но никогда не имел опыта и не использовал связанные списки.
Связанные списки на самом деле являются чрезвычайно простой структурой данных. Они бывают нескольких разновидностей, но общая концепция состоит в том, чтобы просто выделить узлы и связать их вместе с помощью индексов или указателей, например, так:
Почему связанный список используется в этой ситуации?
Связанные списки обладают некоторыми интересными свойствами, одно из которых отмечено на приведенной выше диаграмме, например постоянное удаление и вставка из / в середину.
Почему структуры не просто создаются и хранятся в массиве?
Они действительно могут быть. На приведенной выше схеме узлы могут быть непосредственно сохранены в массиве. Смысл связывания узлов состоит в том, чтобы позволить такие вещи, как быстрые вставки и удаления. Массив элементов не обеспечивает такой гибкости, но если вы храните массив узлов, которые хранят индексы или указатели на next и, возможно, previous элементы, затем вы можете начать перестраивать структуру и удалять вещи и вставлять вещи в середину все в постоянном времени, просто играя со ссылками.
Наиболее эффективное использование связанных списков часто хранит узлы смежно или частично непрерывно (например, используя свободный список) и просто связывает их вместе, чтобы обеспечить быстрые вставки и удаления. Вы можете просто хранить узлы в большом массиве, например vector, а затем связать вещи и отсоединить их через индексы. Еще одним интересным свойством связанных списков является то, что вы можете быстро перенести элементы из середины одного списка в другой, просто изменив пару указателей.
У них также есть свойство, которое делает их очень эффективными для непрерывного хранения, когда заботе уделяется их распределению в том, что каждый узел имеет одинаковый размер. Например, может быть сложно эффективно представить группу блоков переменного размера, если они все используют свой собственный контейнероподобный контейнер, поскольку каждый из них хотел бы выделить различный объем памяти. Однако, если они просто хранят индекс / указатель на узел списка, они могут легко хранить все узлы в одном гигантском массиве для всех сегментов.
Тем не менее, в C ++ связанные списки часто используются неправильно. Несмотря на их алгоритмические преимущества, многое из этого фактически не приводит к превосходной производительности, если узлы не распределены таким образом, который обеспечивает пространственную локальность. В противном случае вы можете столкнуться с отсутствием кэша и, возможно, с ошибками страниц при доступе к каждому узлу.
Тем не менее, с осторожностью относиться к тому, куда узлы попадают в память, они могут быть чрезвычайно полезны. Вот один пример использования:
В этом случае у нас может быть симуляция частиц, где каждая отдельная частица движется вокруг каждого кадра с обнаружением столкновений, когда мы разделяем экран на ячейки сетки. Это позволяет нам избежать обнаружения столкновений квадратичной сложности, поскольку частице нужно только проверять столкновение с другими частицами в той же ячейке. Реальная версия может хранить ячейки сетки 100×100 (10000 ячеек сетки).
Однако, если мы использовали структуру данных на основе массива, как std::vector для всех 10 000 ячеек сетки это было бы взрывоопасно в памяти. Кроме того, перенос каждой частицы из одной ячейки в другую будет дорогостоящей операцией с линейным временем. Используя здесь связанный список (и тот, который просто использует целые числа в массиве для ссылок), мы можем просто изменить несколько индексов (указателей) здесь и там, чтобы переносить частицу из одной ячейки в другую по мере ее перемещения, пока память использование довольно дешево (10 000 ячеек сетки означают 10 000 32-разрядных целых чисел, что соответствует примерно 39 килобайтам с 4 байтами служебной информации на одну частицу для ссылки).
При тщательном использовании связанные списки представляют собой чрезвычайно полезную структуру. Однако их часто можно использовать не по назначению, поскольку наивная реализация, которая хочет распределить каждый отдельный узел отдельно от распределителя памяти общего назначения, имеет тенденцию вызывать большие пропуски кэша, поскольку узлы будут очень фрагментированы в памяти. Полезность связанных списков, как правило, забыта в последнее время, особенно в C ++, поскольку std::list реализация, если она не используется с пользовательским распределителем, находится в этой категории «наивный кэш». Однако то, как они используются в операционных системах, имеет тенденцию быть очень эффективным, используя эти алгоритмические преимущества, упомянутые выше, без потери локальности.
Другие решения
Алгоритмы связанного списка очень хороши, когда вы не знаете, сколько элементов будет в списке, когда начнете, или если вы можете добавлять или удалять элементы со временем. Связанные списки особенно эффективны, если вы хотите добавлять или удалять элементы в любом месте, кроме конца списка. Связанные списки очень распространены в Unix. Наверное, лучшее место для исследования Википедия, которые обсуждают преимущества, недостатки и другие детали. Но основной урок состоит в том, что связанные списки очень хороши для динамических структур данных, в то время как массивы имеют тенденцию быть лучше, когда все статично.
Сетевые интерфейсы могут выглядеть очень статично, если вы думаете о них как о «сетевых картах», но они используются для многих других вещей, таких как VPN-соединения, и могут меняться довольно часто.
Существуют различные способы хранения данных. В C ++ первым выбором обычно является std::vector, но есть std::list и другие контейнеры — выбор будет зависеть от нескольких факторов, таких как, как часто и где вы хотите вставить / удалить вещи (вектор отлично подходит для удаления / добавления в конце, но вставка в середине плохая — связанные списки занимают гораздо меньше вставлять в середину, но будет не так хорошо перебирать).
Тем не менее, API для этой функции — классический C (а не C ++), поэтому у нас должен быть «контейнер переменной длины», и, конечно, мы можем реализовать что-то в C, похожее на std::vector (значение, которое содержит количество элементов и указатель на фактические элементы). Я не уверен, почему дизайнеры не сделали этого в этом случае, но связанный список имеет большое преимущество в том, что это почти нулевая стоимость, чтобы расширить его еще одним элементом. Если вы не знаете заранее, сколько их будет, это хорошая выгода. И я предполагаю, что этих объектов не так много, и они беспокоятся о производительности как таковой (вызывающий всегда может перестроить ее в более подходящую форму позже).
Связанные списки являются очень совершенными структурами данных для хранения очень большого количества данных, число элементов которых неизвестно. Это очень гибкая структура данных, которая расширяется и сжимается во время выполнения. Это также уменьшает дополнительное выделение памяти или трату, потому что они используют динамическую память для хранения данных. Когда мы заканчиваем использовать данные, он удаляет данные, а также это распределение памяти.
Я согласен со всеми здесь о преимуществах связанного списка над массивом для динамической длины данных, но мне нужно кое-что добавить
если выделенные структуры ifaddrs идентичны по длине … нет никакого преимущества в использовании связанного списка над массивом … и если это так, я могу считать это «плохим дизайном»
но если нет (и может быть, это так .. пожалуйста, обратите внимание «Структура ifaddrs содержит по крайней мере следующие записи» … массив не будет надлежащим представлением для структур переменной длины
рассмотрим этот пример
struct ifaddrs
{
struct ifaddrs *ifa_next; /* Pointer to next struct */
char *ifa_name; /* Interface name */
u_int ifa_flags; /* Interface flags */
struct sockaddr *ifa_addr; /* Interface address */
struct sockaddr *ifa_netmask; /* Interface netmask */
struct sockaddr *ifa_dstaddr; /* P2P interface destination */
void *ifa_data; /* Address specific data */
};
struct ifaddrs_ofothertype
{
struct ifaddrs ifaddrs; /* embed the original structure */
char balhblah[256]; /* some other variable */
};
упомянутая функция может возвращать список смешанной структуры, такой как (ifaddrs_ofothertype * приведенный к ifaddrs *) и (ifaddrs *), не беспокоясь о длине структуры для каждого элемента
Если вы хотите изучать iOS, вы должны изучить знания указателей и распределения памяти с самого начала. Хотя Objective-C является языком программирования следующего поколения языка программирования C, но имеет небольшую разницу в синтаксисе, особенно в вызове и определении методов. Прежде чем вы перейдете на iOS / Mac OSX, вы должны понимать знания Pointers, знания MVC, а также понимать основную информацию iOS Frameworks, чтобы стать профессиональным разработчиком iOS.
Для этого визита RayWenderLich iOS Tutiorials