Exploring a possible solution

Now that we know arrays' limitations and the situations where those limitations lead to sub-optimal solutions, we can start to think about a data structure that can be used efficiently in such situations. A singly linked list is designed precisely for situations like this.

Linked list

A linked list is a linear and dynamic data structure that stores data sequentially at random memory locations. Instead of storing all the data items in a contiguous block of memory like arrays, a linked list stores them at random locations in memory. Whenever a new item is to be added, a new memory block is dynamically created to store this new value, which is then added to the chain of already existing items, effectively extending the linked list.

Linked lists vs arrays

A linked list guarantees the insertion and deletion of items from the start and end of the list in O(1) space and O(1) time. It also guarantees the insertion and deletion of any data item without using any extra space. You can imagine it as a dynamic sequential container whose size can be increased or decreased at will.

Let us look at an example of insertion in a singly linked list to understand this better.

Advantages

A single linked list has a few advantages over traditional arrays, which are listed below.

• Dynamic size: The size of a linked list is not fixed. Adding or removing items can increase or decrease at will during runtime.
• Efficient performance: Insertion and deletion of the first node is an O(1) operation.

Limitations

Singly linked lists are not the solution to all our problems. They are very efficient for specific use cases but also have some limitations. 

• Extra space: A little extra memory is required to store an item in a linked list compared to an array. The extra space is used to store the information of the next item in the sequence.
• Traversal: Traversal in a linked list is more time-consuming than an array since random access using an index is not possible. To access an item at position n, one must traverse all the items before it.

A linked list is the most basic but also the most important data structure. Almost all the other data structures build upon the concepts of a linked list, so if there is one data structure that you absolutely must master, it's the linked list.