Introduction to Linked Lists
Introduction to Linked lists using practical real-life example along with its implementation in Python.
Linked Lists are one of the linear Data Structures and form the foundation to learning the more complex ones. Let’s go over it in detail.
What is a Linked List?
Linked Lists is basically a linked “linear” collection of nodes. But we I mean by this statement? Let’s take an example.
Image a train with many connected coaches. Each coach is used to carry passengers. You can think of this coach as a “node” carrying some passengers AKA data. Say, you want to go to the next coach, what will you do? Simply you can use the “link” between these two coaches or nodes. In Computer Science, that’s what you would call a “Linked” List. Have a look at the image below for the basic structure of a linked list.
Here, the ‘Head‘ node is the first and ‘Tail‘ is the last node of the list. Given below is how you would implement a ListNode class (Train coach) in code.
Implementation in Code
A series of such nodes create a Linked List. Each Train coach, that is ListNode, will have 2 types of information. This info can also be called as an attribute or field of the ListNode class. These are:
data – Think of this as the passengers that each coach will carry
next – This is the link or pointer to the next train coach.
Lack of Random Access
One main difference between an array and a linked list is lack of Random Access in the latter. In an array, it takes O(1) constant time to find the element at the ith index. But in the case of linked lists, we need to traverse it completely node by node to arrive at the desired index. Hence, the time complexity in this case comes out to be O(N) where N denotes the number of nodes in the list.
The second drawback is we are also using some additional space in the form of pointers in the case of Linked Lists.
But then you may ask, What’s the real benefit of Linked Lists ? Can’t we just use arrays instead?
Well, this is because of the ease in Insertion in Linked Lists. We’ll see that how in my next post.
Types of Linked Lists
There are mainly 4 different types of linked list:
- Singly Linked Lists
- Doubly Linked Lists
- Circular Linked Lists
- Circular Doubly Linked Lists
We’ll focusing only on the first two types as they are most commonly used. We’ll see them in detail in the next post and will also discuss all the operations that can be done on linked list with time and space complexities. So Stay Tuned!
