Data Structures — Linked Lists
Linked Lists, consist of nodes connected to each other. When you connect these nodes in one direction, it’s called a Singly Linked List, and when you connect them in two directions, it’s referred to as a Doubly Linked List. We will talk about singly linked lists.
First, let’s start by comparing linked lists and arrays. For instance, let’s draw an array and then transform it into a linked list.
1 — Let’s go step by step. Firstly, linked lists do not have indexes like arrays.
2 — Arrays are in contiguous places in memory, but linked lists can be all over the place in memory.
3 — Linked Lists are represented graphically in different way and each item in the linked list, point to the next. Last one points to the null.
In more detail:
Let’s take a look at Big O for linked lists. If you’re not familiar with Big O, you can read my previous article. For instance, let’s see what happens if we push a new node to the end of a linked list.
We already have direct access to the last node of the list through the tail pointer and simply adjust the next pointer of the current tail node to point to the new node. Then, we update the tail pointer to the new node. The number of steps are same which means this is constant time to push something to the end. Result is O(1)
All these steps are basic pointer operations that take constant time each. They don’t require traversing the list or doing any operation that would take more time with a longer list. That’s why the time complexity is O(1)
If we remove item which we pushed to the end (pop) :
We cannot go backwards in the linked list, because nodes don’t have a “previous” pointer. We have to start at the head of the list and traverse the list until you reach that penultimate node. Once we’ve reached the penultimate node, we adjust its “next” pointer to null, effectively removing the tail node from the list. Finally, we set the new tail. So, Big O is O(1)
If we remove the head node, we can simply change the head pointer to point to the next node in the list. So, it doesn’t require traversing any other part of the list, constant time again. Our result is O(1)
If we insert something into the middle of the linked list :
We have to start the head and iterate through the linked list to get this point. That’s why Big O is O(n) If we remove the node we inserted, there will be an iteration again, so the result will still be O(n)
So, what do you think is the Big O of searching for a node in a linked list? In my opinion, everything is clearer now, and yes, the answer is O(n).
We have to start from the beginning again, and since there’s a iteration, our answer is O(n). Here, you can see the difference between an array and a linked list more clearly. Finding in an array by value and by index is different. If we search by index in an array, the result is O(1).
In this article, I introduced linked lists and discussed their logic to make my next article more understandable. In my next article, we’ll write some code related to what I explained today. See you then.
