In our first set of data structures, we get into the definition and scope of non-primitive structures. Have a look at the previous read on The Power of Data structures in case you feel a little lost. Right off the batt, we define what it means to be a non-primitive set, and how this can be further broken down.
Let's get right into it. A non-primitive structure is what happens when you combine two or more primitives. What we mean is simple. A char and int, for instance, are primitives. The simplest representations of data.
Broadly speaking, linear non-primitives can be grouped further as below:
Linear non-primitives
- Stacks
- Queues
- LInked lists
- Arrays
Here, as stated before, data is sequential - one after another. Some of these structures might ring a bell, stackify, is that you?
Arrays
These are what we call stores of homogenous (meaning similar) data. So one might have an array like this:
my_array = [1,2,3,4,5,6,7,8,9] ;
vowels = [' a', 'e', 'i' , 'o', 'u' ] ;
Note how my_array has only integers while vowels has char. In both instances, our array has a collection of primitives - one type of primitive per array.
Arrays are of a fixed size. Once declared, the computer knows the amount of memory reserved for items to be stored there. You might ask:
"But what if the type of data I have changes in size greater than the array?"
Well, you might need to consider a different type of structure to store this data.
Use arrays, for instance, to store months of the year. We will not be changing this count anytime.
Above declared, the sizes of the arrays are inferred. Meaning the types, since not defined per se, are 'figured out' based on the values and how we use them.
We might as well have this:
For python.
import array
count_down = array.array('i', [5,4,3,2,1])
Types may go on as:
c for char
f for float
d for double
u for unicode and so forth.
Have a look at the documentation for more insight into this. AS well, take note that the array module has different functions to enable array manipulation.
Rust:
let count_down: [i32; 5] = [5,4,3,2,1];
Important pointer:
Lists and arrays are not the same!
Operations on an array will be based on the index of the array element, with indexing starting from 0. Hence, the first item, in either case, would be:
count_down[0]
The result from the above is 5 (the semi-colon has been left out for brevity but should be used based on the language you are using).
Let's take a look at another structure that looks similar, but is not the same - Linked lists.
Linked lists
Unlike arrays, linked lists store data in a non-contiguous form. This implies one piece of data is not placed side by side to the other as: [1,2,3,4,5], rather it is stored in form of nodes with pointers to the next as so:
[data1, pointer_to_data2] ... [data1, pointer_to_data3] ... and so on
The last item in our linked list, since there is no pointer to the next, would have null.
As well, linked lists are dynamic- their size is not fixed at initialization.
Linked lists will be further broken to:
a) Singular linked lists (used in the elaboration of linked lists above)
b) Circular linked lists
c) Doubly linked lists
Circular linked lists
These have three items in a node: the previous data, the data, and finally, the next data in the sequence.
[null, data1, pointer_to_data2] ... [pointer_to_data_1 ,data1, pointer_to_data3]
The first item (the head), has a null as the previous pointer while the last node has a null on the next pointer.
Doubly linked lists
Similar to circular linked lists, these have two pointers as well. The only difference would be the last node, instead of a null, has a pointer back to the first item in the list. 1 + 1 = circular.
In most of what we implement through code, we have implementations of linked lists. You will hardly get yourself doing this manually, but understand that some of the things we call 'mutable arrays ' are actually implementations or wrappers around more complex structures.
Example:
If navigating through my directory, my computer needs to know where I am, where I'm from, and possibly have the correct link/structure to the nested directory I'm navigating to. So to the top-level directory, I cannot go any higher, no previous node. Likewise to the last directory or file, there is no 'next' option.
PSST: Ring ring ... we can do some File Management too.
Till now, we have come to understand the importance of data structures, the groups they have been placed into, and we have an idea of what some of the linear data structures involved. We could go on and on about the details of each, but that is a tale for another day. A breather for us both at this point. Go read something non-algorithm-like for a moment. We'll still meet here, same time, the same drive.
