How are Data Structures Stored in Memory

We learned about different types of data structures and different operations that can be performed on them. Before we proceed to next topic let us try to understand how data structures gets stored in memory. This helps to understand the two basic structures and Abstract Data Types (ADT) which are derived from it.

We know, data structure is a collection of data. Each item in the collection is stored as a group of bytes. Byte size vary according to the type of data that we are storing. Example, char - 1 byte, short - 2 bytes, int - 4 bytes, double - 8 bytes.

When a data structure is created, other than storing the data, a connection between each node should be maintained so that when the retrieval happens compiler know which memory location to look into to find the data.

We know that each of the memory location can be accessed using a pointer value (an address) associated with it. When a piece of code creates a data structure, compiler needs a pointer to the created structure to access it for future needs. For a structured data, the program should only be maintaining one pointer and there should be a mechanism to connect all the associated nodes. If the program maintains pointer to each node, we cannot consider it as a data structure. These nodes are only individual primitive data types then.

To address this problem, we can have two solutions.

Arrays and Linked Lists

First option is to allocate a continuous space. By keeping the address of the first node, we can access the rest of the values incrementally. But this type of memory allocation should always have a limit specified, as the number of continuous bytes that needs to be blocked for the structure to hold the data needs to be known well in advance. This type of memory allocation is known as Array Data Structure.

Once an array is created, we can't just increase its size, because the next available memory slot may get allocated for some other process. And that is why arrays in its basic form are not extendable.

Other way is to allocate memory in a non-continuous manner and maintain a link between each node. To connect, each node stores the address of the next node along with the data. This type of data structure is known as a Linked List. For Linked Lists, additional bytes needs to be allocated for each node to maintain the address of the next node.

Comparison

Arrays	Linked Lists
Arrays are stored in continuous memory space.	Linked lists are not stored continuously.
Arrays cannot be extended.	Linked lists can be extended.
Requires lesser space.	More space needed than arrays.
Search and traversal performance is better.	Insert, update, delete operations are faster than arrays.
Arrays have more chance of stack-overflow exception.	Comparatively linked lists have lesser chance, because it can proceed till space for at-least a single node is available.

Arrays and Linked Lists forms the basis of all the other data structures. We can say that other data structures are extended version of either Arrays or Linked Lists.

The steps mentioned above are mostly happening behind the scenes. In some programming languages, array object is mutable and in some a size limit needs to be specified while declaring arrays. The ones that needs the size set are those that allocate memory continuously. Rest may be using Linked Lists behind the scenes. Or an array of fixed size is created initially and when the size exceeds, an new array of bigger size gets created and data is copied. This type of array allocation is known as Dynamic Arrays.

Other datatypes like queues, stacks, lists, etc mostly uses linked lists or dynamic arrays. Some languages have built-in queues and stacks which has the option to specify size limit at the time if declaration. Here continuous memory allocation is possible.

Also note that while some languages have Linked List and Array data types (like Java), some languages like Python misses these. Languages like python has only mutable data structures like Lists which doesn't need a size limit specified at the time of declaration.

This means that while languages like Java provides as the option to choose a data structure of our convenience, core Python doesn't have such flexibility. We have the option to use additional libraries to implement arrays or linked lists.