Linear Data Structures
And the humble array
In this article we will begin our detailed exploration into data structures with the simplest kind, linear data structures.
What’s that?
Well, a linear data structure is exactly what it sounds like, it arranges data into a line! Now, how exactly this line is arranged is the subject of this article.
Linear data structures are the most important kind, because they form the very basics of problem solving.
Exciting! What’s the first one?
To start us off, introducing the array!
The humble array has many names, though common synonyms include list and vector. Since I’m used to C++ slang, I’ll probably stick to using vector since the other 2 are less common, but the concept is the same.
A vector is the simplest linear data structure. It’s just a line of items. That’s it! These items can be literally any data type, and any coder would have used this before in some form.
You’ve probably already heard of this one already, so let’s move on to the more advanced structures for now. But remember that this basic structure forms the building blocks of almost all data structures in the future, even non-linear ones.
Let’s move on to something less common
Okay, let’s talk about the 2 cousins, stacks and queues!
Both stacks and queues are exactly what they sound like. Imagine a stack in real life, like stacking books from the previous article. When you add an item to a stack, we say we push something onto the top of the stack. We can also pop the item at the top of the stack. Usually we use the methods stack.push(item) and stack.pop(item) to accomplish this.
Similarly we have the queue. The terminology is similar as above, and yes, a queue is exactly what it sounds like. We can push items into the back of the queue, and pop them from the front.
Notice how the only thing that changes is where we put the new items? In a set, we add and remove from the top. We call this principle last in, first out (LIFO) because the last thing added to the stack is on the top, the first to be removed. In a queue, the we add from the back and remove from the front. The first to enter the queue is also the first to be removed, we call this principle first in, first out (FIFO).
That’s cool! But how can I apply it?
The applications of stacks are queues will be discussed in another article, to avoid making this one too long. Just remember, they are exactly what they sound like. Try using them to solve the example problems later on!
Why not just arrays?
I thought you’d never ask! The answer really depends on the context. For some problems, we want to quickly add and remove items from the front and back of a data structure, and you’ll see example problems of this kind soon. For this specific task, stacks and queues are significantly faster, because they are designed specifically to ignore other items not at the top of the stack or at the ends of the queue.
Anything else I should know?
Well, there is one more thing. The queue is a very versatile data structure we’ll see quite often. There’s actually different types of queues, but they all work the same way as the normal one.
In a priority queue, the queue is always sorted in increasing order.
In a deque, short for double-ended queue, you can access both ends of the queue rather than just the front
We’ll be seeing these other queues later, but the functionality is just the same as the normal.
Oh, is that it?
Well, almost. There’s a few smaller data structures you should probably know about…
A
pairstores exactly 2 valuesA
tuplesome number of values, depending on how you define itA
bitmaskis a vector of ones and zeroes
Of the above, bitmasks are very important! Seriously, there’s a whole article dedicated to them, so we’ll see them later for sure. There is one more data structure, called a set, which I’ll cover some other time because it’ll be good if you know the underlying logic behind it first.
But till then, go ahead and think about how you’d solve this problem, which we’ll go through in a future article:
As well as this more challenging one:
If you’ve read this far, you should know that writing a newsletter is easier with a long queue of subscribers :) (see what I did there?). If you’re not already subscribed, I’d appreciate the gesture!
And If you are, why not stack up more subscribers by sharing this content with a like-minded friend who’d appreciate it? (see what I did there again :))