A Simple Structure
Published: 2019-08-17 03:01:43

This is the second part of my rambling discussion on stuff I want to build. You can find the first part [here](http://bit.ly/2z1Brum).

# Simple Structures
I’m going to start from some first principles. The odds are good that you’re already familiar with everything I’m about to say, and that’s great. But maybe it's new, or you want a refresher. Either way, I want to make sure we’re on the same page before I move to the next step.

Most data today is in the form of a record. This is just a fancy term for grouping data together. For instance, I could group names and ages.
```
	(Mary, 32)
	(Paula, 21)
	(Andrew, 35)
```

(Oh, you didn’t think I’d put my _real_ age there, did you? 😉)

Within a record, there are either simple data types, such as strings and numbers, or other record types. This ought to look familiar to anyone who has used any programming languages. The parts of each record will usually have labels to refer to each specific part, or else the developer is left to remember which part is in which position (such as in a tuple for languages like Python). So the first parts here are called _name_ and the second parts are called _age_.

In modern languages, we have a choice of designing a record specifically for the data or using _ad hoc_ map structures that use the part labels as keys. For instance, in Javascript, we can have:
```javascript
  a_person = {name: "Mary", age: 32}
```
<a name="person"/>or
```javascript
class Person {
  constructor(name, age) {
    this.name = name;
    this.age = age;
  }
}
a_person = new Person('Mary', 32);
```
The latter looks more complex, but it is especially useful when we want to guarantee that the structure contains required information, or otherwise validate the data being provided.

Once we have this simple record type, how do we go about storing more than one? Most languages provide several ways. In Javascript, you would probably use an array. But now that we have some basic elements of records I’m going to look at the Linked List.

# Linked Lists
Linked Lists are one of the first data structures taught in CS courses. Well, they were one of the first that _**I**_ was taught (confession: I skipped class that day). They are often overlooked, due to their limitations, but there are occasions when they are quite valuable. They’re also illustrative of some of the things that I want to explore, so I’m going to work with them here.

Say I want to store a series of numbers: `1, 1, 2, 3, 5, 8, 13, 21, 34`

The basic idea of a linked list is to create a daisy chain of simple elements which each hold a single value, and then refer to the next element.
![Daisy chain with numbers over each flower](https://raw.githubusercontent.com/quoll/raw-data/master/daisy_chain.jpg)
 Each element then needs to have the value being stored there, and also refer to the next one along. The trick is that the last one refers to nothing when it points to the next one.

<a name="list"/>Let’s try that, using Javascript again:
```javascript
class Element {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}
```

Worth noting is that when the `next` parameter is not provided, then it gets set to `null`. This just means that a single element list is being created, with nothing else following it.

A trick to building a linked list is to build them from the back. That way when you want the “next” element in the chain, you’ve already made it. You can do it from the front, but then you need to use up extra memory (usually on the call stack) as you run towards the end. The computer still builds the chain from the back, even if your code doesn’t look that way.

<a name="listConstruction"/>But in this case, I’m going to build the chain, starting from 34 and moving back to the front:
```javascript
let list = new Element(34);
list = new Element(21, list);
list = new Element(13, list);
list = new Element(8, list);
list = new Element(5, list);
list = new Element(3, list);
list = new Element(2, list);
list = new Element(1, list);
list = new Element(1, list);
```
This can (and should be!) written in a friendlier way, but that won’t get us any closer to where we’re going, so I’m going to leave all the raw parts here for you to see.

First of all, you can see that the final element in the chain has nothing following it, so this is left as the default, which is just `null`. You’ll also see that I’m using a `list` variable to hold the start of the list all the time. So the `list` variable keeps shifting to the most recent start of the list. Each time a new element is added to the start of the list, then the existing `list` value is used for the remainder of the list, and then the `list` variable is updated to refer to the new start.

I keep referring to "the list" and "the rest of the list". Traditionally, the beginning of a linked list is called the _head_, and the remaining list is called the _tail_. Note that both the _head_ and the _tail_ are both valid lists, and that the _tail_ list is always 1 shorter than the list that starts at the associated _head_.

What does the resulting structure look like? Is it as we expect?
```javascript
  Element {
    value: 1,
    next: Element { value: 1, next: Element { value: 2, next: [Object] } } }
```
It seems to be, but the nested data gets cut off quickly, so let’s build a function that creates a more readable string.

Linked lists are ideal for being processed with _recursive_ functions. I remember when recursion was first shown to me. I followed what was being said easily enough, but every time I tried to write something recursive I always struggled. I just wasn’t getting it. But these days I take recursive functions for granted. So it _is_ possible to learn them! Really.

Meanwhile, if I gloss over concepts like that, then I apologize. Ask me for clarification.

For linked lists, a recursive function generally falls into a standard pattern:
- Do something with the first element of the list.
- If there is a tail, then call the function again on that tail.

In this case, the operations are short enough:
- Look at the start of the list and return what’s there.
- If there is no more list, then that’s it.
- But if there **is** more list, then add a comma and then add on... the same thing again for the rest of the list:<a name="listString"/>
```javascript
	function listString(element) {
	  if (element.next === null) return element.value;
	  else return element.value + ', ' + listString(element.next);
	}
	
	listString(list)
	'1, 1, 2, 3, 5, 8, 13, 21, 34'
```
Which is what we expected, so we know the structure is working.

There are lots of things that can be done with linked lists. We can fill them from arrays, or pull them back out into arrays. We can insert extra numbers into the middle, we can remove elements, we can reverse them, we can process each element in turn… the possibilities go on. Many of these operations are quite important in contexts where we want to update structures, but this discussion will be focusing on structures that are rarely updated, so we can leave that for another time.

Instead, we are looking at how these structures may be represented in storage. To do that, the next article will consider how this linked list structure might look in an older language, like C.

On to [Part 3](https://dev.to/quoll/a-simple-structure-in-binary-6lj).