Зв'язаний список
Вузли, з'єднані вказівниками з динамічним розміром та O(1) вставкою.
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (node) contains two parts: the data and a reference (or pointer) to the next node in the sequence. It allows for efficient insertion and deletion at any position during execution.
graph LR
Center["Зв'язаний список"]:::main
Rel_graph_data_structure["graph-data-structure"]:::related -.-> Center
click Rel_graph_data_structure "/terms/graph-data-structure"
Rel_tree["tree"]:::related -.-> Center
click Rel_tree "/terms/tree"
Rel_sorting_algorithm["sorting-algorithm"]:::related -.-> Center
click Rel_sorting_algorithm "/terms/sorting-algorithm"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Перевірка знань
🧒 Простими словами
Уяви квест, де кожна підказка говорить тобі, де знайти наступну. Ти не можеш піти відразу до 5-ї підказки, тобі треба пройти всі з 1-ї по 4-ту. Це зв'язаний список!
🤓 Expert Deep Dive
XOR-зв'язані списки економлять пам'ять, зберігаючи XOR адрес попереднього і наступного вузлів. Unrolled linked lists зберігають масиви у кожному вузлі для кращого кешування. Lock-free списки (алгоритм Харріса) дозволяють конкурентний доступ без блокувань. Skip Lists додають 'швидкіс смуги' для пошуку за O(log n).