Data structures in Plain English — Linked Lists

Linked lists, just like arrays are data structures that are used to store a bunch of elements. But unlike arrays, linked lists are not stored in a contiguous location in memory. Instead, they use nodes that can be stored anywhere in memory but are linked together via pointers. Every node contains a link to the next node in the linked list.

Class node:
   def __init__(self,data) -> None:
       self.data = data
       self.next_node = None

Creating A Linked List

To create a linked list, all we need to know is the first node since every node in the linked list points to the next one, the last node points to null, indicating the end of the linked list.

Class linked_list :
    def __init__(self,first_node = None) -> None:
          self. first_node = first_node
node1 = node('first')
node2 = node('second')
node3 = node('third')
linked_list1= linked_list(node1)
node1.next_node = node2
node2.next_node = node3

This is how you create a simple linked list containing 3 elements, easy right? okay, maybe not as easy as creating an array but as you’d learn later on, it can be very useful and worth taking your time.

Traversing a Linked List

Since linked lists are not stored in easily determinable locations in memory, it is impossible for the computer to move to the third element without having gone through the first and second elements, hence the need for moving through every element in the linked list, to perform an operation on it. This is called traversing the linked list

def read(self,index):
   current_node = self.first_node
   current_index = 0   while current_index < index:
      current_node = current_node.next_node
      current_index += 1
      if current_node == None :
          return None
   return current_node

The read function is a form of traversal where we return the node in the given index. This form of traversal is useful in other operations
Searching for an Item in a Linked List

When checking if an item is in a linked list, we have to go through every element in the linked list and compare it to the value we’re searching for

def search(self,data):
    current_node = self.first_node
    current_index = 0
    while current_node:
        if current_node.data == data:
            return current_index
        else:
            current_node = current_node.next_node
            current_index += 1
    return None

Inserting Items Into A Linked List

Remember the bit about arrays being stored in a contiguous location? well, this works well until we have to insert an item into the array. Let’s say we want to insert x into the 3rd index of an array of 20 elements, we would need to shift every element from the 3rd element one space forward, which is not very fast. Inserting into an array is fastest at the end and slowest at the beginning, the opposite is the case for the linked list. In fact, it only takes one step to insert into the beginning of the linked list, which in terms of speed is about as fast as it can be.

Insertion in linked lists is done by changing the next_node of the new node to the node after the given index and the next_node of the previous node to the new node

def insert(self,value,index):
    previous_node = self.read(index-1) 
    next_node = previous_node.next_node
    current_node = node(value,next_node)
    previous_node.next_node = current_node

Inserting at the beginning only requires changing the first_node to the new node and linking it to the previous first_node

def insert_at_beginning(self,value):
    old_node = self.first_node
    self.first_node = node(value)
    self.first_node.next_node = old_node

Deleting Items In a Linked List

Just like in insertion, deleting an item is done by changing the links between nodes.

def delete(self,index):
    node_before = self.read(index-1)
    current_node = node_before.next_node
    node_after = current_node.next_node
    node_before.next_node = node_after

In the example above, we try to remove the node at the given index by getting the node before and after it then having them link to each other instead.

To delete at the beginning all we need to do is change the first_node to its next_node

def delete_at_beginning(self,index):
    self.first_node = self.first_node.next_node

Why Use a Linked List?

As you might have guessed, linked lists do not outperform arrays in general. Instead, they are better at insertion and deletion operations and are very useful when you have large data sets that would be modified a lot when using them. This can save a lot of time as there will be no need for shifting elements like in the array.

It is important to learn to take advantage of every data structure’s unique strengths and weaknesses when trying to solve problems or preparing for interviews.

Thanks for reading. I hope this was helpful. Let me know in the comments if you have any questions or comments to add. I’ll be waiting for your response.