The ABC of Data Structure

You know how it’s really difficult for one to understand a concept you are not familiar with, most especially in computing. I actually took a course on Coursera which was titled learning how to learn. I think the course really helped me to understand how my brain works in trying to grasp a new skill.

Recently, I partook in a tech assessment exercise and basically the whole interview was centred around some of the major programming concepts such as scalability, performance optimization, algorithms and data structures. Yeah, data structures, I almost didn’t answer the questions asked during the interview on data structures correctly. Why because I didn’t have much interest in it then. For instance, an ArrayList. Why do I still need to know how an arrayList works when Java has already done most of the work. But I realised that in order for you to write good algorithms, you actually need a good knowledge of data structures. Having this knowledge allows your algorithm to be able to manipulate data more efficiently.

So I set out on this journey to understand data types and their applications using the knowledge I got from learning how to learn course I did. The course actually pointed out some key things about knowing your diffuse mode of thinking, which is sort of a more relax way of learning a new concept or a skill. So here we go:

Firstly of all, you want to have a theoretical understanding of the subject and this could be called the declarative stage.

By definition, data structures are simply ways of storing data in such a way that the data can be used efficiently. Most software applications basically use data structures, ranging from arrays, graphs, queues, LinkedList, hash tables e.t.c.

I will be talking about a few of these data structures.

Arrays

An array is an area of memory consisting of equal size elements indexed by integers. It is also a placeholder for storing more than one variables. Arrays are represented differently across programming languages. In Java, we have

int[] mFruits = new int[5];

Arrays are arranged in memory in a contiguous manner. For example, an integer is equal to 4 bytes in memory, and each integer is linked to a memory address.

Arrays can be one dimensional, such as that above, multi-dimensional(either two or three).

Why is array important?

It is very important because of the advantage it has in storing data more efficiently than variables.

Operations that can be performed on an array include:

1. Adding to an array using the push()
2. Removing from an array using pop();

NB: You might also want to learn about array addresses.

Real life applications of Array

It might surprise you to know that arrays can be used in multiplication. check out this link: Array applications.

Other examples of real life applications of array can be seen in chess/checker boards, book pages e.t.c

Stacks

Which could also mean LIFO(Last in, First out). You know when you are piling up a list of books, the topmost book is actually the first one you take out.

Operations that can be performed on stacks include:

1. Adding to a stack(push())
2. Removing from a stack(pop());
3. peeking at the top most element which is the last element in an array(peek());

Real life applications of Stack.

A very simple example of this is the back button of the web browser which is explained in this Quora question. Other applications include;

i. reverse of a word.

ii. “undo” mechanism in text editors.

NB: Time complexity is very important when executing data structures. Stacks operate in the Big O of 1 i.e O(1). Read more about Big O or Asymptotic notation here.

Queue

A queue is almost like Stack except it uses FIFO(First in first out). A practical example of a queue is waiting in line to register for an event.

Operations that can be performed using Queue include:

1. enqueue(key) which means adding to the collection

2. dequeue(key) which means removing from a collection.

One major difference between Stack and Queue is that for Stack, both insertion and deletion takes place at the same end, while for Queue, the insertion and deletion take place on different ends.

Linked List

We know arrays have limitations in the sense that, when you try to expand an array, you do not know to what extent the array should accommodate variables, thereby leading to wastage of memory. In order to handle this, LinkedList is used.

Unlike an array, which constitutes a contiguous block of memory for the items, a linked-list works by giving one memory address at a time to each item. This is quite efficient because it will be easier to expand the list, and also prevent wastage of memory.

Each element is linked to the next element using the memory address.

Operations that can be done on a linkedList include:

1. PushFront(key) — adding to the front of the LinkedList
2. key TopFront() — return front item
3. popFRont() — remove front item
4. pushback — add to the back

Real life applications of linked list

1. A chain with each element linked together
2. A train having it’s coaches linked to each other.

Trees

Linked lists, arrays, stacks and queues are examples of Linear data structure. This is because they are arranged in sequential or logical order, and also because they have a start and an end. A tree is a hierarchical data structure that represents data in a hierarchy.

Here is a mathematical problem using a tree data structure:

Important terms to know about trees include; Nodes, Children, Parents, Siblings, Roots, Descendants, Ancestors, Leaves.

Real life applications of Tree

1. It can be used for geographical hierarchy.
2. It can also help to analyse code.

A more comprehensive real life applications can be seen here.

After having a good understanding of the theoretical part of data structures, it’s imperative to practice these concepts by doing some coding challenges because “Practice makes Permanent”. This stage of practising can be called the associative stage. I use Hackerank to practice, which has been very helpful throughout my learning process.

To read more about data structures, you can check out this YouTube video which explains the fundamentals of data structures.