Representations of Data: One Primitive Plus One Primitive Equals Linear Non-Primitives

On 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

int

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 homogeneous (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

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])

# where *i* stands for int (an array of integers).

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

Rust:

let count_down: [i32; 5] = [5,4,3,2,1];

// where *i32* is signed integers, and *5* in *[i32; 5]* is the size of the array. i.e have five integers

Important pointer: Python lists and arrays are not the same!

Operations on an array will be based on the

index

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

null

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

In most of what we implement through code, we have implementations of linked lists. You will hardly get yourself doing this manually, but understanding 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.

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 on 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.

Previously published at: https://thegreencodes.com/data-structures-the-linear-non-primitives