Let's Link! My Journey With Linked -> Lists

It doesn’t matter what language we start using when we begin our journey to code. You eventually learn they are different types of data structures. There are many ways & tools to solve a problem, the issue is knowing the right time to use these tools to best solve your problem.

What Is A Linked List?
To understand what a linked list is, you first need to understand what type of data structures they are. A linked list is a collection of nodes and the only properties they have are their data and their next reference. Linked lists have a linear type of data structure—meaning, there’s a sequence and an order to how they are constructed and traversed. We can think of a linear data structure like a game of hopscotch: in order to get to the end of the list, we have to go through all of the items in the list in order, or sequentially.

In a linear data structure to access any element/node, you have to traverse the entire list.

Different Types Of Linked Lists:
A singly linked list is a collection of nodes that collectively form a linear sequence. Each node stores a reference to an object as well as a reference to the next node of the list.
Example:

class Node:
        Def __init__(self,value):
            self.value = value
            self.next = next    

a = Node(1)
b = Node(2)
 c = Node(3)
 a.next = b
 b.next = c
// 1 → 2 → 3

So, just as a node can reference it’s subsequent neighbor node, it can also have a reference pointer to its previous node, too. Because there are two references contained with each node, we call this a doubly linked list. This can be helpful if we want to traverse our data structure not just in a single track or direction, but also backwards, too.
Example:

class Doubly_LinkedListNode(obj):
        def __init__(self,value):
            self.value = value
            self.next = next    
            self.prev = prev

a = Doubly_LinkedListNode(1)
b = Doubly_LinkedListNode(2)
c = Doubly_LinkedListNode(3)
a.next = b
b.prev =a
b.next = c
c.prev = b
    // 1 → 2 → 3
          ←    ←

For a singly linked list, the tail node points to null. Conversely, a circular linked tail node refers back to a previous node.

Example:

class Node(obj):
        Def __init__(self,value):
            self.value = value
            self.next = next    

a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
c.next = a
// 1 → 2 → 3
   ^_______^

Why use a Linked List Instead Of an Array?
Memory Management:
One big difference between linked lists and arrays is the memory allocation and the space that’s needed under the hood of your computer every time you create a linked list or an array. What do I mean by this? Each time you create an array, your computer needs a certain amount of space in it’s memory. The space in an array is stored in a block-like structure. If the space next to the last item is not free, your computer relocates or shifts every element over making space for the new item. When a linked list is created, the space is stored anywhere in memory. Linked lists can be scattered throughout the computer’s memory.

Array space in computer space:
Visualize going to the theaters with your friends. Typically, you want to sit with your friends and if one row doesn’t have a seat you check the next row until you have a space that accommodates all of you.

Linked List in computer space:
Visualize going to the theaters with your friends again but this time it’s a really popular new movie and you guys are dying to see it. This time you can’t all sit together so you split up and find any seat available. Each friend has a reference to the next friend.