Reading 05

Memory Allocation: Linked Lists vs Arrays

Linked lists are dynamic data structures while arrays are considered static data structures. What’s the difference?

• Static Data Structure - all it’s resources (memory) are allocated on creation
  • If structure grows or shrinks, it would still require a given amount of memory.
  • If more memory is required, a copy of the data of the array would be made with more memory
• Dynamic Data Structure - able to change memory size as the structure grows and shrinks
  • No set amount of memory
  • Responsive memory allocation according to size of data set

How does a Linked List Have Memory Scattered Everywhere?

Linked lists are made of nodes. Each node has two parts: data and a reference to the next node. Nodes point to the next data element in the list, but do not know anything about that data. Nodes do not know how long the list is, where it starts, or necessarily where it ends. Since each node has an address for the memory containing the data of the next node, the memory doesn’t need to live next to one another in a long, contiguous memory block.

Source:

https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d