how are data structures stored in memory?

Let us understand how data structured are stored in memory by drawing an analogy with apartment units. Consider these apartments units as containers where the data resides. The organization of individual units is similar to how we would like to lay out the data in memory, and of course there are some kind of access and relational rules between the units, just like there is for data structures.

When we store primitive data types like your numbers or characters, the apartment sizes are fixed. Say for example to store an integer, we will need 4 bytes- that is 4 consecutive memory addresses. Well this is the simplest form of apartment units.

What is it with arrays? Arrays are like a single row of identical apartments on the same floor. The storage of elements hence is contiguous, allowing for easy access by specifying their position or index. In Python:

python

numbers = [1, 2, 3, 4] # the numbers here are stored in consecutive memory locations.

Coming to Linked Lists: these are chain of apartment, scattered throughout the building, with an apartment unit containing both the data and address of the next unit. Technically we call it, every node contains the data and a pointer (memory location) of the next node:

python

class Node:
    def __init__(self, data):
        self.data = data #the actual value self.next = None #address of         the next node

Consider a dictionary to hold keys to the apartment units. these keys point or associate themselves to the data contained by the apartment, i.e, how we are able to access.

python

apartment = {"A101": "Alice",
"A102" : "Bob"}

Trees: We all know what's a family tree right. Now say if every family member were to have their own apartment, and yet we wish to retain the information of their lineage or family relationship- how should we do it? the answer is tree. Here every apartment or node will have addresses of all its children apartments. What is a binary tree? Impose a rule that a parent can have at max 2 children- there you go, that's your binary tree

class treeNode:
    def __init__(self, value):
        self.value = value #data in this node
        self.left = None #address of left child
        self.right = None #address of right child 

Memory allocation in Python is particularly interesting since it employs a set of strategies,

1. apartment units already come pre-allocated or reserved for small integers, ranging from value -5 to 256 and short strings.
2. when it comes to larger objects, apartments or spaces are dynamically allocated to them
3. now consider, you had housed to a tenant contracted on a temporary basis only to get an interior done. Once, its done, why will you reserve this space right?- rather this tenant is paid at the end of the job and moves out. Similarly, Python has something called the garbage collector that is in charge of freeing up memory or space by removing objects once the purpose it was required to serve, is fulfilled.

An interesting part is, consider you are a group of say two families put up in adjacent rooms on your tour. In the very next day, two of your friends also show up at the hotel reception with their families. Given all of you would now want to be put up in a similar adjacent setup, may be you'll need to shift floors since its only on the other floor where adjacent ones remain empty.

Similarly, when you append values to a list, whenever it is unable to find contiguous blocks of memory at the existing location, the whole set along with the newly added value will be moved to a space where adjacent blocks of memory is available.

Because of such memory organization and re-organisations, certain operations appear to be relatively faster or slower,

• arrays: faster access, but slow insertion or deletions from the mid position
• linked lists: faster insertions and deletions, but slower access since there's no contiguous or adjacent allocations
• hash tables or dictionary: on average everything here is very fast
• trees: the speed here is balanced- in fact better for hierarchical data

The sole reason why understanding data structures is important? understanding storage and access helps us identify which pattern is best suited for our data.

In our next letter, we will dive into Loops, Comprehension, and what not! don't expect me to spill all the beans right away- eh! :-D

Have a good one! Cheers!!