Know Your Algorithms and Data Structures - in Any Language - Part 2

From my previous post, I discussed the importance of knowing simple algorithms every software developer/engineer must grasp as part of their engineering repertoire. In this post, I will be covering topics on common data structures that we normally (or always, should I say) use when implementing our algorithms.

The common ones are the following:

1. Arrays
3. Stacks
4. Queues
5. Hash Tables

Data Structures

a) Arrays

If you’ve ever been doing some programming for a while, you may have run into this term a lot by now if you ever worked with or seen lots of loop iterations in many codebases. If you haven’t, then I’d suggest now it’s time to take a refresher course on the `for` loop constructs. After all, that’s what (and why) arrays are built `for` :).

Arrays are the most prominent and well-known piece of data structure programmers of different programming disciplines have come across with. They are very simple data structures, and you can place any kinds of data types in them from strings to booleans. And they usually have a finite size of holding items. And the most common type of data operations we’ve seen on arrays are manipulating and traversing data hold of items by referencing its indices.

All popular programming languages I know or aware of supports them - such as the following.

PHP

Next, we have a second commonly used data structure called the linked lists. Like arrays, you can also perform data storage and data operations in a similar fashion. The key difference is that its elements are not stored contiguous linearly. Elements are individually linked one after another - and typically the links are called ‘pointers’. For eg

Given the illustration above, the arrows indicated as pointers thus each element’s pointer is always referenced to the next subsequent element. Each pointer typically represents a node in which an element is stored. Thus we normally depict linked list structure to be a visual representation of chaining of nodes - one node after another.

The key difference is, unlike the arrays, its actual data storage is never finite - meaning it’s not fixed. It can dynamically grow (or shrink) as you see fit. You can easily remove and add items to the list by looking at the current node that will hold the pointer reference we’re interested in.

The key concepts when you start working with linked lists are:

• Link - Each link to a linked list can store a data usually called an element or similar.

Here is the list of popular programming languages with their respective linked list implementation.

PHP

Bear in mind, there are other three known types of linked lists we should be aware of as well - which are not within the scope of this post.

• Singly linked list - we perform forward traversal operation in the list along with the nodes as per our example.
• Doubly linked list - we perform both forwards and backwards traversal - using two nodes interlinked instead of one.
• Circularly linked list - a linked list where all the nodes are connected in a circular direction ie the last node of the list has the pointer reference to the head node of the list.

There are simply variations of the original linked list implementation as above. You can find other examples online how they’re accomplished. My point here is for you to get comfortable knowing its basic structure well beforehand. Once you have this knowledge grounded, the rest of them are fairly straightforward to implement.

c) Stacks

Another data structure that is commonly used. And they certainly have their wide array of practical uses.

If you can ever imagine, in the real world, things like a deck of cards or a pile of unwashed dishes in the kitchen are the prime examples of a stack type.

When we shuffle our decks, cards are removed and placed on the top surface of the deck. Or when we start piling up dishes in a stack, the dirty dishes at the top are always the first ones to get washed before moving down rest of the stack. This is the classic characteristic of a stack.

In the programming world, our stack-based operations follow this main principle tightly. Stacks perform insert and removal operations, where we insert items at the end of the list and we remove items at the end of the list. Their respective operations are called “PUSH” and “POP”. Another common terminology to describe this is called “LIFO” or last-in-first-out operations.

We can also perform other operations such as checking if the stack was full or empty (isEmpty) and check the status of the current stack(peek) as well.

Here are the programming languages’ respective stack implementations.

d) Queues

Like stacks, queues also operate similar fashion. But the order of traversal and data operations are slightly different.

Like in real life, before you watch a blockbuster movie, or dine in a popular restaurant or buy a ticket to attend a music concert, you have to line up in a queue like the rest of the crowd do. The people at the front are always served first, people at the back (and others who are late to arrive), will be served last.

Thus queues, in the programming world, are exactly like that.

Queues are operated in “FIFO” fashion ie first-in-first-out fashion. First items at the front of the queue get removed whilst items are the back continue to get longer as more new items are being pushed at the back. We use “dequeue” and “enqueue” for describing the respective operations.

Again, here are the languages’ queue implementations.

e) Hash Table

Lastly, we have our linear data structure using a special table that uses key-value store by reference, called “Hash Table”.

It’s coined such a term because its primary concept revolves around indices. Indices are used to store data so that our ability to readily access such data store will be efficiently quick and easy to look up. Data (stored as value) are referenced or flagged with a particular index (or key) in a table so we can search them up by depending on this key-value associative relationship.

It’s much like the same way how you want to look up for certain keywords or phrases by reaching for the index section of a library book and then locate the actual page numbers containing the same words or phrases you identified. Hashtable is analogous to this.

When making associations between the key values and the required hashed keys in a hash table, we require our hashing techniques to do this.

Any hashing computing methods can be done in several ways to make this hash key-value mapping possible, so long as such hashing functions are efficient computable and should uniformly distribute keys without any possible duplication or collision of keys when inserting into a hash table.

For the purpose of this post, our simplest example of it would be to use a modulo operator. This modulo operator is used to take a range of data values to compute their respective key indices.

For eg, let’s say you have a table size of 10 and you have the following:

Notice, in the example, we do have repeated hashed index values, thus we need to have collision handling techniques to prevent any two or more values that reference the same key. Under such circumstances, we go to our neighbouring array slot to see if the slot is empty. We keep searching for the empty slot until it is found and insert the key value appropriately. Like so.

That’s it.

Finally, their actual implementations are as follows:

PHP

That’s all for common linear-type data structures.

The next type of data structures I want to cover in my upcoming post are tree structures, where data are stored along with the nodes, and all nodes are interconnected by edges. Much like how you have an apple tree that has all apples hanging by the tip of their branches - or nodes in our case.

And also, its common algorithms such as binary search trees and heap; and how useful are they when performing faster-searching operations in larger scale regardless the dynamic size of data space can take.

Till then, Happy Coding!