In this blog let us try to understand what is a linked list and it’s types and also what are the real-time applications of a linked list.
Before diving into the details of what a linked list is let us try understanding a real-time example.
Say, you are on Spotify, and listening to your favorite song and wanted to have a song to be played next again to be your favorite song in this scenario what you do is create a playlist of songs you like so that no other song will interrupt you or stop you from listening to your favorite song so after creating a playlist there will be a first song which is placed first followed by the next song and so on until your playlist is exhausted.
Now in this scenario what we are doing is creating a playlist and setting one of the songs as the first one which is a head or beginning of your playlist, and followed by the other songs which can be changed by clicking > button so let us try correlating with the concept of linked list now, in linked list we will have a head node which is the starting or beginning node and next node is a reference to the next upcoming node.
Let us formalize the definition so that we can get a clarity.
What is a Linked List?
Linked List is a linear data structure where memory is stored in non-contiguous memory location that is the memory is allocated dynamically.
Contiguous V/S Non-Contiguous:
As we have seen in the case of arrays that it is stored in contiguous memory locations which will lead to memory wastage when there is data which is not fixed and we go on inserting, in this case we can use linked list where we start with head node and create a reference pointer next which points to the next node.
Now let us look at the real-time application of linked list:
Undo and redo functionality in games or applications is a real-time application of linked list which will have a previous history of the move we made having it’s first version as the head node.
Now let us see what are the different types of linked list:
Linked List are classified into 3 types:
- Singly linked list
- Doubly linked list
- Circular linked list
What do you mean by singly linked list?
Singly linked list is defined as a type of linked list in which the elements is a node that contains:
Data – this is the value it may be an integer, strings, or any data type.
Next – this is the pointer variable or reference variable for the next node in the list.
Some of the basic operations on a singly linked list: