Today, we will be discussing some data structures. Now, what are data structures? Well, basically when you store any kind of object in your room, do you want it to be messy, or stuck in pile of god-knows-whatever objects and impossible to dig out until months later by accident? Or do you want it to (or hope it somehow will be) stored properly, where it is easily locatable? Hopefully, everyone picked the latter. Basically, a data structure is a tool that helps organize any incoming data in whatever order is required for that specific data.
First, let’s look at a pretty well known data structure : Arrays. Arrays are a relatively common data structure, familiar to basically anyone with a highschool level understanding of CS. Basically, an array is like a whole group of numbers assigned to a variable. For example, if group of primitive integer variables are defined as :
g = 6
h = 7
y = 9
Instead you can define an array and say
j = {6,7,9}
A specific value in this array is marked with an “index”. Basically, each entry is labelled starting from 0. Here, j[0] would refer to the ‘6’. It gets a little confusing as you would expect j[3] to give ‘9’, but here since you start indices from 0, ‘9’ is actually j[2]. j[3] would be an error (rather an “exception“). To understand an array, just think of a table.
Basically, if you try to put in j[0], the system would go to the first entry, move down however many values the number in the bracket specified, and return the corresponding entry. Arrays are pretty common, but it is reasonably complicated to remove or add elements to an array. Usually, arrays come in set sizes and stay that way.
Also, keep in mind that arrays can only store on dimensional data (basically just a line). If you need to store data for a whole grid, you need something better.
Presenting, two dimensional arrays!
Two dimensional arrays work pretty much the same way, except now you need to specify rows and columns, so j[0][3] refers to the value in row 0, column 3. Try not to think of it as an entirely new structure. A two-dimensional array is basically just an array of arrays, if that makes sense. Think of an array, but instead of each element j[n] referring to one specific number, it refers to a whole other array.
Let’s look at some other data structures. A linked list is a data structure that’s like a train. Each value in the list is a “node”, and all the nodes are joined so that each connects to the next one, and the next one and so on. Linked lists are good if you want to add and remove data quickly, you just have to make sure that the pointers going to the removed data are sorted out properly. Linked lists help you, well, link data. Suppose you have a bunch of nodes that were made at different times, so they are spaced out in the computer’s memory. With a linked list, you can join them all together and not have to worry about any data in between. A link list can either be circular, meaning that when you reach the end, it just points back to the start. Imagine a train going in an infinite circle (one of the most useless modes of transport ever created). It can also be a finite linked list, which ends whenever the node is a “null” or zero value. A doubly linked list is one that can go either front or back, so each value points both ahead and behind.
Let’s take a look at stacks, and queues. These are basically just different types of link lists. Queues are all “first-in-first-out”, basically whichever data arrives first is the one pushed out. Think of all the long queues at amusement parks. If you get there early, good on you! But if you don’t, you wait there politely until you can leave.
A stack is a last-in-first-out structure (all the people who ever had problems with recursion just shuddered). Imagine a pile of socks. Unfortunately, when you put your socks in a stack, the nice clean ones that you put on top end up getting used first, and the ones at the bottom never see the light of day again. Stacks basically work the same way. Any new data is “pushed” onto the stack, and the same data is the first thing “popped” off.
Lastly, let us look at trees. A tree is basically a link list with a left and right side. Most people will know what a tree is, just picture all those awful family trees you had to make for school.
Each tree has “parent” and “child” nodes, which basically define if the current node points to anything else or not. The main node , or ‘8’ here, is known as the “root” node, which is odd considering the top of the tree isn’t really the roots, but sure. Trees come in all kinds, and there are even crazier kinds of trees that rotate to balance the number of nodes on each sides (nature in CS is weird).
Well, that’s pretty much it. Data structures provide a convenient way to store data so you don’t just lose it in a heap of random gibberish. Next week, we’ll look at some more in-depth things about, say, algorithms. Until then, good luck.
Resources :http://www.thecrazyprogrammer.com, http://www.geeksforgeeks.org
Bits and PCs 