What is Linked list?

A linked list is a type of linear data structure where the data elements are randomly arranged and linked through a pointer. In this blog post, we are going to discuss more about them.

A linked list has a series of nodes that are connected in sequential order. The first node of this linked list is called the head node while the last one is called as tail node/end node. Each node carries the data value and the address for the next node.

Types of Linked Lists:

1. Single linked list

2. Double linked list

3. Circular linked list (3D Arrays)

What is a single linked list

• Every node in a single linked list has an address to the next node in the list.

• Traversal happens from the head node to the tail node.

• Since every node is only addressing the next node in the list, reverse traversal (tail to head) doesn't happen.

Advantages:

• Easy to access a node in the forward direction

• Addition and deletion of nodes are easier without disturbing the other nodes

• Due to the simple structure and dynamic size, it is easy to implement a data structure with a single linked list.

Disadvantages:

• Due to no information about the previous node, it takes time to remove a node

• Due to one-way traversal, node access gets difficult.

Double-linked list

• Except for the head and tail node, every other node in a double-linked list has an address to both the previous and the next node in the list.

• The head node has no address reference for the previous node and the tail node has a null address reference for the next node.

• Traversal happens from the head node to the tail node and vice versa.

• Compared to a single-linked list, a double-linked list consumes more memory usage due to bidirectional traversal

Advantages:

• Two-way traversal is easy with the double-linked list. This further helps in topological sorting.

• Deletion of nodes is easier in a double-linked list than in a single-linked list.

• Since graph algorithms require backtracking during the execution and backtracking is made easy with a double-linked list, it is easy to implement graph algorithms through a double-linked list.

Disadvantages:

• Implementing a double-linked list is more complex than a single-linked list

• Traversal through a double-linked list takes more time than a single-linked list

Circular linked list

• In the circular linked list, the tail node addresses the head node to be the next node, thus making the circular pattern.

• Circular linked lists can be either single-linked or double-linked.

• Traversal happens based on the link used in the circular linked list.

Advantages:

• Traversal can happen at any point in the list.

• Compared to trees or graphs, implementing a circular linked list is easier.

• Useful for applications that go through a list. Eg: Music playlist.

• Since the circular structure aligns well with the queue behavior, it is easier to implement a queue with circular linked lists.

Disadvantages:

• Complex to implement when compared to a single-linked list.

• If not handled carefully there are higher chances for the code to go into an infinite loop.

• Circular linked lists can be slower in cases like sorting or searching due to no direct node access.

Purpose of linked list

1. Insertion and deletion of elements happen by updating the address. This makes it easier to add the data elements.

2. Since it is a dynamic data structure, memory allocation is made flexible. This further helps in efficient memory usage.

3. This simplified memory management and the recursive structure makes the linked list a smooth foundation to implement advanced data structures like stacks, queues, graphs, hash maps, skip lists, etc

How do you create a Linked List

1. We use a class to store the structure of a Linked List Node. The following is the C++ code for the Linked List Node class which can be used to create a Linked List Node Object.

   	
   class Node { 
   	public:
   	int value; 
   	Node *next; 
   	Node *prev; //If a Double
   	Linked List Node (int x) { 
   		value = x; 
   		next = NULL; 
   		prev = NULL; //If a Double Linked List 
   	} 
   }
   								

   Here is how you write the same Linked List class in python

   
   									
   class Node:
   	def__init__(self,x):
   	self.data = x
   	self.next = None 
   	self.prev = None #If a Doubly Linked List
   									

2. The following is the code to create a Singly Linked List having values form 1 to N in each corresponding node.

   
   									
   Node* create(int N) { 
   	Node* head = new Node(1); // Initially the LL is created with a single Node in it with a value of 1 
   	Node* temp = head;// Storing the head in a temp variable as we are going to move head later 
   	for(int i=2;i <= N;i++){
   		Node* curr = new Node(i); // Creating a Node with the current index as the value 
   		head-> next = curr; // Setting the curr Node as the next node for head 
   		head = head-> next; // Moving the head forward so that we can add the next node 
   	}
   	return temp; // Returning temp which has the address for the original head 
   }
   								

Quiz time

1. How does traversal happen in a single linked list?

   1. Head to tail

   2. Tail to head

   3. Both directions

2. What kind of links are used in the Circular linked list?

   1. Single linked

   2. Double linked

   3. Both A and B

3. What kind of links are used in the Circular linked list?

   1. 1

   2. 2

   3. 3

Conclusion:

In this blog post, we discussed what are linked lists, and the types of linked lists in data structure. We hope you got a good understanding of the basic details of linked lists. Here's an infographic for your quick reference.

Answers

1. A - Head to tail

2. C - Both A and B

3. B - 2

How many answers did you get right?