RnR: Linked Lists

What is a linked list?

Basically, a linked list is a type of data structure that can be used to organize information. Basically, but so what? So are maps, objects, arrays, vectors, hashes, dictionaries, queues, etc… What specifically is a linked list? Well, it’s pretty self-explanatory. They store data in a node structure wherein each node contains a reference (or link) to the next node, and so on.

If only that was all to be said about this topic! Yeah, right.

Maybe I can start to explain by making their case. I did not find evidence of this, but I imagine that linked lists were invented in a time when computer memory was scarce enough to require very creative methods for storing data. There was a time not that long ago when programmers needed to manually allocate space in memory to store their data in. So, when you’ve got 4 bytes of memory free here, and 10 bytes there, and you need to store 16 floats and be able to access them relatively conveniently in one place, maybe an array won’t cut it.

Why not? This is perhaps a good place to start to explain how linked lists work. Where an array will store data in contiguous locations in memory, a linked list is less rigid. A linked list does not need contiguous memory blocks to store information. At a low level, a node in a linked list contains a reference, and this reference need only be the location in memory of the next node in the list.

As an aside, the concept of storing a memory address in a variable is not exclusive to linked lists. In fact, storage of a memory address in a variable is known as a pointer, and has broader and equally important implications for computer science.

Here’s an example of a linked list node (in C, since these details are abstracted away in javascript, basically):

struct Node {
  //type of data that you want to store.
  float data;
  
  //pointer to next Node in list
  Node * next;
  
  //constructor that sets data
  Node(float data) {
    this->data = data;
  }
};

Once you have a declaration of a Node object, creating a linked list is as easy as hooking up the pointers:

  Node *head = new Node(1.1);
  Node *second = new Node(2.2);
  Node *third = new Node(3.3);
  
  head->next = second;
  second->next = third;

Here we have a linked list with three elements: head, second and third. Each node is initialized with a float as an example. Then, head’s next pointer is set to second, second’s next pointer is set to third, and third’s next pointer points to no memory address, so it is NULL.

If we output the memory locations of these three pointers, and their next nodes, we would get:

head->next is set to the same location as second! second->next is set to the same location as third, and third’s next is 0, since it is hooked up to nothing currently.

Now that this is hooked up, we can use these node’s pointers to access data along the list. To do this, we could simply call node->next->data list so:

float headData = head->data;
float secondData = head->next->data;
float thirdData = head->next->next->data;
//and so on...

Outputs:

Exactly as we declared the data! And this is essentially how linked lists work. Of course, implementing one in this way is awkward and repetitive, so in real life you might declare a LinkedList class that takes care of adding and removing Nodes.

But wait! You might have noticed that these memory locations appear to be contiguous, an even 20 bytes apart:

Compare this to the memory locations of the elements in an array of floats with similar values:

Contiguous and 4 bytes apart, since a float is 4 bytes in size. The linked list is not bound by the order that the nodes are created in. Although the linked list has a larger memory footprint (20 bytes in this case), each node is self contained with its data and accessing information. This allows for nodes in the list to be in any order, or inserted and removed from any point in the array. Consider if we were to declare the nodes in our list in a different order and output the results:

  Node *third = new Node(3.3);
  Node *head = new Node(1.1);
  Node *second = new Node(2.2);
  
  
  head->next = second;
  second->next = third;

The order is purely coincidental. At least in an older language like C or C++, an array can not be dynamically sized. So when you declare an array, you need to tell the compiler up front how many elements you want and of what type they are. Then, that specific amount of memory is allocated for that array. By contrast, a linked list can be dynamically prepended or appended with data after the list has been created. Because of how pointers work, all the relating nodes need to know are the memory addresses of the next nodes, and nothing else.

I have commented today on singly linked lists, but there are also doubly linked lists. Doubly linked lists are where each node has two pointers: one to the next node and one to the previous node. This allows for list traversal in two directions instead of one.

In this case, the code only requires one extra pointer.

struct Node {
  //type of data that you want to store.
  float data;
  
  //pointer to next Node in list
  Node *next;

  //pointer to the previous Node in list
  Node *prev;
  
  //constructor that sets data
  Node(float data) {
    this->data = data;
  }
};

While the linked list is an interesting and useful alternative to an array structure, it does have some limitations. They do require more memory per node than an array would require per element. In addition, it is more difficult to access a specific element in a linked list, since nodes in the list are not in relative position to a structure like an array.

All this being said, linked lists are fun and can lead to some interesting projects. They are easier to grasp while programming something like a snake game!

Happy linking!