In which tasks is it better to use a list instead of an array?

Using 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.