Understanding Linked List Data Structure

A warm hello to all the readers!

This post will talk about the use of linked list data structure. This is the second data structure after array. There are certain limitations with array because of which linked list came into picture.

The array is a fixed memory sized structure and stores elements in continuous memory locations. This means that if an array items[10] is defined, then it will consume 10*4 = 40 bytes of memory (let us assume each element takes 4 bytes memory). Now whether an element is stored or not inside this array, despite this fact it will still keep occupying the 40 bytes.

Therefore, to overcome this limitation, linked list was born.

What Is Linked List?

A linked list is a list of elements of same data type that are linked with each other by use of memory address. The elements are stored in non continuous memory locations unlike array. In order to make the list, these elements that are stored in non continuous locations are connected or linked with the help of each’s memory address.

Above elements are linked with each other by their respective memory address. This means it requires to store not only the value of the element but also it’s memory address. And each element in linked list is thereby called a node.

A node is a collection of two things – Element value, Memory address of next element represented in the following form:

And a sample linked list is represented as:

The only downside with linked list is that each node has two parts attached to it, the value and next value’s address. While this was pretty simple in arrays.

What Are Linked List Operations?

Let us now talk about different operations that can be performed on the linked list.

1. The item can be accessed
2. A new item can be inserted in the beginning, end or anywhere in between the list
3. Any item can be deleted
4. Any item can be searched by traversing the list

What Is The Time Complexity Of Linked List?

Now we know the different operations that can be performed on the linked list. We shall now see what is the time complexity of each operation.

1. Accessing element – This takes O(n) time because each element has to be traversed to see memory address of next element
2. Inserting element – This takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
3. Deleting element – This again takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
4. Searching element – This also takes O(n) time since it requires (n) unknown number of iterations over the elements of the list in order to search a particular value

Types Of Linked List

There are three different variations of linked list.

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