Let's talk about Lists first
In computer programming Lists are a type of data structure through which we store data. List data structures are similar to the "real life list" concept. The way all of the elements of a real life list comes one after another list data structures also store the data contiguously in the memory. We can access, modify as well as delete the elements of a list data structure.
(The theoretical part)
What are Linked Lists
Linked Lists are the data structures which store data linearly (like a list) but they don’t store the elements contiguously in the memory. Each element of a Linked List is called a Node. The links among the nodes is a unique feature of a Linked List. Based on the connections there are 4 types of Linked Lists. The 4 types of Linked Lists are: Singly Linked List, Circular Singly Linked List, Doubly Linked List and Circular Doubly Linked List.
Enough of the bookish definition of Linked Lists now we'll learn about Linked Lists in our own words.
Every linked list has atleast concepts/parts. A head node/value, a tail node/value, next and pervious node's reference.
🔶 Singly Linked List:
Let's assume the Singly Linked list as a train. The way the train compartments are connected to their next compartments with a link, the nodes of a Singly Linked List are linked to their next nodes. Every element of a Linked List is called a node. The very first node of the Linked List is called the Head. The last node is called the tail(the node after which no newnode will exist is the last node). As we know that Linked Lists don’t store data sequentially so index 1 stores the tail node(this is the 2nd node we create). A node stores the memory address of the next node. We can access the next node of a linked list using the node.
Real life application: Back buttons(for example:- the smartphone back buttons are created using Singly Linked List so they allow us to go only in a single direction).
🔶 Circular Singly Linked List:
The only structural difference between Singly Linked List and Circular Singly Linked List is that the Circular Singly Linked List has a link between the Head and Tail node. Which means the Tail node stores the memory value of the Head node.
Real life application: The Circular Singly Linked List is used in our personal computers. When multiple applications are run on a PC all of the running apps are stored in a CSLL.
🔶 Doubly Linked List:
The nodes of a Doubly Linked List store the memory locations of both the previous and next node. Which means we can access both the previous and next node using the current node. Otherwise all of the features of DLL are similar to SLL.
Real life applications: Web browser cache, music player etc.
🔶 Circular Doubly Linked list:
The only structural difference between Circular Singly Linked List and Circular Doubly Linked List is that in CDLL the Head and Tail nodes are connected with eachother both ways so the tail's next node will be the head and the head's previous node will be the tail node.
Real life applications: Shopping cart on online websites etc.
(The implementation part will be added here soon)
Top comments (0)