Linked List

Linked List

#

A linked list is a linear data structure, in which every element of the list is not stored at a contiguous location, in other words each element of the list can be stored in any memory address space.

The way a linked list stores information is in nodes. A linked list forms a series of connected nodes, where each node saves the data and the address of the next node.

Now that we have a brief understanding of what a LL (linked list) is, why do we use it? We use linked lists in almost every app or software. For example, in the carousel of photos (on our phone) it shows every photo that we have taken. We know that not all the photos are taken on the same day, so the phone stores the photo (data), and creates a pointer that references the next photo to be taken. This process is called dynamic storage allocation.

Advantages of Linked Lists

#

• Dynamic Size: Linked lists can grow or shrink dynamically, as memory allocation is done at runtime.
• Insertion and Deletion: Adding or removing elements from a linked list is efficient, especially for large lists.
• Flexibility: Linked lists can be easily reorganized and modified without requiring a contiguous block of memory.

Disadvantages of Linked Lists

#

• Random Access: Linked lists do not allow direct access to elements by index. Traversal is required to reach a specific node.
• Extra Memory: Linked lists require additional memory for storing the pointers, compared to arrays.

Node Structure

#

I mentioned node before, but I didn’t explain properly what a Node is, so, in a summarized way we can say that a node is sum of two components: Data: It holds the actual value associated with the node. Next Pointer:The memory address (reference) of the next node in the sequence

Code

#

Okay, I have been writing a lot, so now lets deep dive into the code section

Node constructor

#

Before creating a linked list it is necessary to create a Node, therefore we create a class called Node. This class is very simple, consisting of only one method (and this method is the constructor of the class) that stores only two things. the value (data) and next (the reference to the next pointer).

class Node:
    """
    Node class

    Define every item on the linked list

    Attributes:
        value:  The item of the list in that node
        Next:   The next hope to the element to the linked list 
    """
    def __init__(self, value) -> None:
        """
        Constructore of the node
        """
        self.value = value
        # The pointer
        self.next = None

Linked list constructor

#

Great, we have already created the Node constructor, which is the base for this class. Now, we need to create the linked list class. But before we write the linked list constructor, I forgot to mention two important elements that are part of a linked list. The firs is the head, wichs refers to the first item in the list, and the other is the tail, which is the last item in the list.

class LinkedList:
    """
    Linked List class

    Define a general class of linked list, 
    with basic operation over the LL

    Attributes:
        lenght: The number of nodes in the LL
        head:   The first node of the LL, could be Null
        tail:   The last node of the LL, could be Null
    """
    def __init__(self, value) -> None:
        """
        Constructore of the LL
        """
        new_node    = Node(value = value)
        self.head   = new_node
        self.tail   = new_node
        self.length = 1

We have completed the linked list constructor, and our current linked list contains only one item. In a later post I will be writing about operations that we can implement in the linked list class, such as the append method or pop method.

The song of the post

#

Click here to listen

Going Kokomo
Our life’s a beach so let’s let go
Don’t stress yourself
Might even play this on the radio
— Going Kokomo - Royel Otis