Suggest an editImprove this articleRefine the answer for “In which tasks is it better to use a list instead of an array?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)Using a **linked list** instead of an array pays off where **structural flexibility and frequent data changes** matter, rather than fast access by index. **Key point:** a linked list is better than an array when data changes frequently, the size is unpredictable, memory is fragmented, or fast access for insertions and deletions is needed; an array is preferable when fast access by index and high storage density are needed.Shown above the full answer for quick recall.Answer (EN)ImageUsing a **linked list** instead of an array pays off where **structural flexibility and frequent data changes** matter, rather than fast access by index. Here are specific cases where a list is better than an array. --- ### **1. When elements need to be inserted and removed frequently** A linked list lets you insert and remove elements: - **at the beginning** in O(1); - **in the middle or at the end (if a reference exists)** also in O(1). In an array, these operations require **shifting elements** → O(n). **Example tasks:** - Queues, stacks, message buffers. - Action history (Undo/Redo). - Memory management or task lists where something is frequently added and removed. --- ### **2. When the data size is unknown in advance** An array requires knowing, or at least estimating, the size in advance. If the data grows, the array must be recreated and the elements copied (O(n)). A linked list simply adds new nodes dynamically. **Example tasks:** - Streaming data (incoming events, logging). - Dynamic structures (a print queue, a list of active clients). --- ### **3. When memory savings under fragmentation matter** An array requires a **contiguous block of memory**, which is sometimes impossible due to fragmentation. A list, on the other hand, stores nodes **in different places** and connects them with references. **Example tasks:** - Low-level systems (OS, drivers), where allocating a large memory block is problematic. - Implementing memory allocators, free-block tables. --- ### **4. When a structure is needed where elements are moved around often** If data is frequently reordered, swapped, or inserted into the middle, in a list this is just a rearrangement of references, without copying. **Example tasks:** - Implementing an **LRU cache**, - **Priority queues**, where elements are updated frequently. --- ### **5. When endless or circular traversal is needed** A circular list is convenient to use when the structure needs to "go around in a circle." **Example tasks:** - Games (round after round), - Task schedulers (round-robin scheduling), - Ring buffers. --- ### **6. When fast insertion at the beginning matters** An array adds at the beginning in O(n): all elements are shifted. A list does this in O(1): only `head` is reassigned. **Example tasks:** - Implementing a **stack**, where adding and removing always happens at the "head." --- **Summary:** > A linked list is better than an array when: > > - data changes frequently, > - the size is unpredictable, > - memory is fragmented, > - fast access for insertions and deletions is needed. > > An array is preferable when you need **fast access by index** and **high storage density**.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.