Для чего внутри связного списка нужен массив?

Question

[chaturanga]

Имеется задача по хранению данных. По заданию данные хранятся в двусвязном (для ускорения поиска последних внесённых данных) списке, в каждой ноде которого создаётся массив из N (по умолчанию 8) элементов.
По реализации вопросов нет, но остался вопрос "зачем"? Какое преимущество даёт создание дополнительного массива по сравнению с хранением в обычном двусвязном списке?

Comments

[Adamos]

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

[chaturanga]

The goal of the task is to write a simple CSS processing engine. As part of the task, you need
to read CSS sections interleaved with command sections from standard input. CSS sections
should be parsed and placed in the appropriate structures, and command sections should be
parsed and executed, printing any results to standard output (after ==).
CSS.
• Processing begins with the reading of CSS declarations. CSS is syntactically correct and
consists of blocks of attributes possibly preceded by selectors. The absence of selectors is
legal (it would mean attributes applied to everything).
• Selectors are separated by commas. Legal selectors for CSS are allowed, but it can be
assumed that they do not contain commas or curly braces.
• The block of attributes is enclosed in curly braces.
• Attributes are separated by semicolons and consist of a name (property) and a value
separated by a colon. A semicolon may or may not follow the last attribute in the block.
• Legal CSS constructions can be used as attribute values, but for simplicity, it can be safely
assumed that any strings are not malicious, i.e. do not contain escaped quotation marks, curly
braces, or semicolons.
• If a specific attribute name appears multiple times in a block, treat it as a single occurrence,
with the last value being significant.
• Both selectors, attribute names, and attribute values do not require semantic interpretation,
i.e. they are treated as values after trimming whitespace. For example, 'margin-left: 8px' and
'margin: 4px 7px 4px 7px' are treated as separate, unrelated attributes with the names 'marginleft' and 'margin' and the values '8px' and '4px 7px 4px 7px', respectively. Similarly, selectors
are treated as values and do not require interpretation, i.e. 'h1' and 'h1.theme' are treated as
separate, unrelated selectors.
• Simplified CSS does not contain comments or @-type selectors, and blocks cannot be
nested.
• For the purposes of all tests, it can be assumed that no selector or attribute is split across
multiple lines (multiple separators and/or attributes can appear in one line).
...
Implementation notes:
Selectors and attributes should be stored as lists. Individual CSS sections should be stored in a
doubly linked list (to efficiently perform the E command). To better utilize memory, the list
should include an array T=8 of structures representing a block (where T is a constant that can
be changed at compile time) and a counter for currently occupied structures (due to potential
element deletions). Counters should be utilized to speed up operations parameterized by the
cell number, i. When allocating a new node, a T-sized array should be created. When adding
elements, if there is free space in the list node, it should be used before allocating new nodes.
If an empty array remains after removing elements, the node should be removed. It is not
necessary to move elements between nodes, merge nodes, etc

Answer 1

[Wataru]

В тексте задания уже есть ответ на ваш вопрос:

To better utilize memory, the list should include an array T=8 of structures representing a block

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

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

Answer 2

[res2001]

Видимо планируется хранить список на медленном устройстве хранения (на диске). Тогда такое построение связного списка вполне оправдано - за одно чтение можно прочитать несколько блоков данных.
Возможно примерно таким же способом хранятся таблицы в СУБД. Называться это может по разному.
Так же в СУБД часто применяют b-tree для хранения индексов, в этом дереве то же хранится несколько элементов данных в одном узле.

Answer 3

[Дмитрий Беляев]

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