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:
- Singly Linked Lists
- Doubly Linked Lists
- Circular Linked Lists
In general, we will be taking singly linked lists into consideration.
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.
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.
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.
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:
Now, let us implement the Linked List and its nodes. To start with, we need to create a
Node class with two attributes -
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
None for the time being. In the later sections, we will be changing this
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.
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!