What are Linked Lists?

Linked Lists are yet another linear data structure in which the elements are not stored in contiguous memory locations. There are mainly three types of linked lists:

1. Singly Linked Lists
2. Doubly Linked Lists
3. Circular Linked Lists

In general, we will be taking singly linked lists into consideration.

Basic Structure

Every linked list consists of nodes where each node has two components - data and next pointer.

Note: The above image shows a Singly Linked List.

The data part of the node is used to store some kind of data and can be of type of string, number, or any other object type. The next part of the node is a pointer pointing from one node to its next node.

Apart from this, we have another pointer called head that points to the start of the linked list, i.e., the first node of the linked list. The head pointer helps us to traverse the linked list from the beginning.

The last node of the linked list(excluding circular linked lists) points to null, which means the linked list ends here.

Arrays vs Linked Lists

Before we dive deep into linked lists and their implementations, let us quickly understand how they differ from a regular array.

Contiguous Memory

Arrays are stored in contiguous memory locations which allow the access time to be constant, whereas, in linked lists, nodes are not stored in contiguous memory.

Accessing Elements

Since arrays are indexed and stored in contiguous memory locations, it is a constant time operation to access elements in arrays. However, in the case of linked lists, to access the nth element, you need to perform O(n) operations because we need to start traversing the linked list from the head pointer to the nth element.

Insertion/Deletion

In the case of arrays, the insertion/deletion operations take O(n) time complexity because we need to shift all the elements of the array to the left or right depending upon the situation. However, in the case of linked lists, the insertion/deletion operations take constant time complexity as we just need to change the orientation of a few pointers only.

To summarise, here's what we have:

Basic Implementation

Now, let us implement the Linked List and its nodes. To start with, we need to create a Node class with two attributes - data and next.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

In the constructor of the Node class, we set self.data to the data that will passed while creating a Node object. We also set self.next to None for the time being. In the later sections, we will be changing this self.next attribute.

Next, we can create the Linked List class as:

class SinglyLinkedList:
    def __init__(self):
        self.head = None

In the constructor, we set the self.head pointer to None for now. Later, we will point it to the first node of the linked list.

Wrapping Up

Let us conclude this article here. In this article, we learned about Linked Lists and their basic structure and implementation. We also saw how they differ from arrays. In the upcoming parts, we will learn how to perform operations such as insertion, deletion, node swapping, merging of linked lists, etc.

Stay tuned, thanks for reading!