Массированные массивы связанных списков против узлов

Я читаю о развернутых связанных списках и нашел два разных способа их создания. Книга у меня есть реализует один, как это:Массированные массивы связанных списков против узлов

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

// Block of nodes 
typedef struct linkedblock { 
    struct linkedblock *next; 
    Node *head; 
    int nodeCount; 
} LinkedBlock;

однако Википедия показывает, что вместо LinkedBlock имея указатель на Node, он имеет массив. Я думаю, это может быть так, что память смежна и что-то вроде эффективности кеша? Есть ли другие преимущества для этого? Является ли способ, которым моя книга реализует ее менее оптимизированной/хуже? Существует ли обычный или предпочтительный способ?

Я пытаюсь реализовать развернутый связанный список, чтобы я мог узнать, как они работают, но также и в случае, если я буду использовать его в будущем (я странно не могу найти никаких реализаций на GitHub или где-либо еще). В основном я хотел бы знать, какой из двух способов будет более вероятен для использования в реальных приложениях. Кроме того, это структура данных, которую я не должен тратить слишком много времени на изучение? Потому что в моей другой книге алгоритмов (CLRS) я даже не упоминал об этом.

источник

2016-07-16 Austin

Кажется, что одна из тех идей, которые хорошо смотрятся в теории, но на самом деле является болью в -.... Тот факт, что вы не могли найти каких-либо реализаций, является хорошим показателем того, что развернутые списки не имеют практической ценности. – user3386109

Под «развернутыми связанными списками», вы имеете в виду «навязчивые связанные списки»? Потому что если так, то такие списки, безусловно, * DO * имеют практическое значение. –

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

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

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

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

источник

2016-07-16 20:46:09 MrCodeBlok

Массированные массивы связанных списков против узлов

ответ

Смежные вопросы