Linked Lists

Question:
What is the data structure whose singular purpose in life is to be reversed.
Answer:
Linked list

What is a Linked List

A linked list is one of the fundamental data structure. It's a linear data structure for storing a collection of items. A linked list is very similar to an array. The main difference is how a linked list is implemented or stored in memory.

Unlike arrays, linked lists are not stored in contiguous or back-to-back memory slots. They are stored/linked using pointers.

A pointer is a data type used for storing a memory address. It enables us to store the memory address of another memory address/slot.

This is what a basic linked list looks like:

Breakdown

When creating a linked list, we create a structure called a node. A linked list includes a series of connected nodes. Each node has a data/value and a pointer to the next node in the linked list.

Linked Lists in Memory

Linked lists are not stored in contiguous memory slots. They are stored using pointers. Here is how they're actually stored. In memory, we would have two back-to-back memory slots for each node, where one memory slot holds the data/value, and the second memory slot holds the pointer. The next node in the linked list we're pointing could be anywhere in the memory. Let's look at an example:

1 -> 2 -> 3 -> 4

The first data/value in our linked list is called the head. Our first data/value in our linked list is the number 1. That value is stored in memory address 18, and the pointer is stored next to it in memory address 19, because each node has the value and the pointer, and they need to be in a back-to-back memory slot. Memory address 19 points to the value of number 2 at memory address 9. The pointer is stored next to it in memory address 10. Memory address 10 points to the value of the number 3 at memory address 3. The pointer is stored next to it in memory address 4. Memory address 4 points to the value of the number 4 at memory address 7. The pointer is stored next to it in memory address 8. Memory address 8 points to null, which basically points to nothing. The last node (value & pointer) in our linked list is known as the tail.

An important thing to note is that, if any two back-to-back memory slots are occupied, our program will never replace/delete that data. Our program will try to find other available memory slot/address that are free to store in our data.

Why Linked Lists?

As mentioned, a linked list is very similar to an array. Both have their own pros and cons. Arrays are easy and quick to access. On the other hand linked lists require iteration of the entire data structure to access data. Insertion of a new element or deletion of an element in an array would shift every element in the array, which is not efficient. However, in linked list, it can be done by redirecting the next pointer of the previous node to point to the new node instead of the current one and the next pointer of the new node must point to the original next node.

Types of Linked Lists

• Singly Linked List: The most basic and simple type of linked list, where each node points to the next node in the linked list. The first node is knows as the head, whereas the last node is called the tail.

Example:
1 -> 2 -> 3 -> 4 -> 5 -> null

• Doubly Linked List: Similar to singly linked list, however each node has a pointer to the previous node in the linked list. The previous node is usually referred to as prev

Example:
null <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null

• Circular Linked List: A type of linked list that has no plain head or tail, because the pointers form a closing circle. A circular linked list can be either a singly or doubly linked list.

Example 1:
1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> 3 -> 4 -> 5 -> 1 ...
Example 2:
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 ...

Conclusion

A linked list is a linear data structure. Each element is represented as a node, which contains the value and a pointer to the next node. Linked list is not stored at a contiguous memory address. The nodes are linked and stored using pointers. There are three main types of linked lists: singly, doubly, and circular linked list.

Thank you!
Jonny