Introduction to Linked List – Data Structure and Algorithm Tutorials
Last Updated :
22 Oct, 2024
Linked List is basically chains of nodes where each node contains information such as data and a pointer to the next node in the chain. It is a popular data structure with a wide range of real-world applications. Unlike Arrays, Linked List elements are not stored at a contiguous location. In the linked list there is a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.
In this article, we will provide a complete introduction of Linked List, which will help you tackle any problem based on Linked List.
Basic Terminologies of Linked List
- Head: The Head of a linked list is a pointer to the first node or reference of the first node of linked list. This pointer marks the beginning of the linked list.
- Node: Linked List consists of a series of nodes where each node has two parts: data and next pointer.
- Data: Data is the part of node which stores the information in the linked list.
- Next pointer: Next pointer is the part of the node which points to the next node of the linked list.
Importance of Linked List
Here are a few advantages of a linked list that is listed below, it will help you understand why it is necessary to know.
- Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.
- Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated.
- Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.
- Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.
Implementations of Basic Operations on Different Types of List
Basic Operations on Singly Linked List
The following are some basic operations performed on a Single Linked List:
- Insertion: The insertion operation can be performed in three ways. They are as follows:
- Deletion: The deletion operation can be performed in three ways. They are as follows:
- Traverse: This process displays the elements of a Single-linked list.
- Search: It is a process of determining and retrieving a specific node either from the front, the end or anywhere in the list.
Operations on Doubly Linked List:
In a doubly linked list, we perform the following operations…
- Insertion: The insertion operation can be performed in three ways as follows:
- Deletion: The deletion operation can be performed in three ways as follows…
- Display: This process displays the elements of a double-linked list.
Commonly used operations on Circular Linked List:
The following operations are performed on a Circular Linked List
- Insertion: The insertion operation can be performed in three ways:
- Deletion: The deletion operation can be performed in three ways:
- Display: This process displays the elements of a Circular linked list.
|
Array
|
Linked List
|
|
Arrays are stored in contiguous location.
|
Linked Lists are not stored in contiguous location.
|
|
Fixed size (Dynamic Sized Arrays also internally use fixed sized arrays)
|
Dynamic Size
|
|
Only store elements no extra reference / pointer.
|
It stores both data and address of next node.
|
|
Elements can be accessed easily in O(1) time.
|
Elements can be access by traversing through all the nodes till we reach the required node.
|
|
Insertion and deletion operation is slower than Linked List.
|
Insertion and deletion operation is faster than Array.
|
Time Complexity Analysis of Linked List and Array:
| Operation |
Linked list |
Array |
| Random Access |
O(N) |
O(1) |
| Insertion and deletion at beginning |
O(1) |
O(N) |
| Insertion and deletion at end |
O(N) (If we maintain only head) |
O(1) |
| Insertion and deletion at a random position |
O(N) |
O(N) |
Please refer Applications, Advantages and Disadvantages of Linked List for more details
Frequently Asked Questions (FAQs) about Linked List:
1. What is linked list data structure?
Linked list are most commonly used to handle dynamic data elements. Linked list consists of nodes and a node consists of two fields one for storing data and other for keeping the reference of next node.
2. What is linked list example?
A linked list can be assumed as a garland that is made up of flowers. Similarly, a linked list is made up of nodes. Every flower in this particular garland is referred to as a node. In addition, each node points to the next node in this list, and it contains data (in this case, the type of flower).
3. Why do we need linked list data structure??
There are some important advantages to using linked lists over other linear data structures. This is unlike arrays, as they are resizable at runtime. Additionally, they can be easily inserted and deleted.
4. What are linked lists used for?
The linked list is a linear data structure that stores data in nodes. these nodes hold both the data and a reference to the next node in the list. Linked are very efficient at adding and removing nodes because of their simple structure.
5. What is the difference between array and linked list?
There are some following differences between them:
- Arrays are data structures containing similar data elements, whereas linked lists are non-primitive data structures containing unordered linked elements.
- In an array, elements are indexed, but in a linked list nodes are not indexed.
- Accessing an element array is fast if we know the position of an element in the array, while in the Linked list it takes linear time so, the Linked list is quite bit slower.
- Operations like insertion and deletion in arrays take a lot of time. Whereas, the performance of these operations is faster in Linked lists.
- Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.
6. Why is a linked list preferred over an array?
Following are the reason that linked lists are preferred over array
- Nodes in a linked array, insertions, and deletions can be done at any point in the list at a constant time.
- Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.
- Linked lists provide an efficient way of storing related data and performing basic operations such as insertion, deletion, and updating of information at the cost of extra space required for storing the address.
- Insertion and deletion operations in the linked list are faster as compared to the array.
7. Which is the best array or linked list?
There are some advantages and disadvantages to both arrays and linked lists when it comes to storing linear data of similar types.
Advantages of linked list over arrays:
- Dynamic size: Linked lists are dynamic and flexible and can expand and shrink their size
- Ease of Insertion/Deletion: Insertion and deletion operations in linked list are faster as compared to the array
Disadvantages of linked list over arrays:
- If the array is sorted we can apply binary search to search any element which takes O(log(n)) time. But even if the linked list is sorted we cannot apply binary search and the complexity of searching elements in the linked list is O(n).
- A linked list takes more memory as compared to the array because extra memory space is required for the pointer with each element in the linked list.
8. What are the limitations of linked list?
Following are some limitations of the linked list:
- The use of pointers is more in linked lists hence, complex and requires more memory.
- Random access is not possible due to dynamic memory allocation.
- Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.
- Searching for an element is costly and requires O(n) time complexity.
9. Why insertion/deletion are faster in a linked list?
If any element is inserted/ deleted from the array, all the other elements after it will be shifted in memory this takes a lot of time whereas manipulation in Linked List is faster because we just need to manipulate the addresses of nodes, so no bit shifting is required in memory, and it will not take that much of time.
10. What is the difference between a singly and doubly linked list?
Following are some difference between single and double linked list.
| Singly-linked list (SLL) |
Doubly linked list (DLL) |
| SLL nodes contains 2 field data field and next link field. |
DLL nodes contains 3 fields data field, a previous link field and a next link field. |
| In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. |
In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward). |
| The SLL occupies less memory than DLL as it has only 2 fields. |
The DLL occupies more memory than SLL as it has 3 fields. |
| The Complexity of insertion and deletion at a given position is O(n). |
The Complexity of insertion and deletion at a given position is O(n / 2) = O(n) because traversal can be made from start or from the end. |
| Complexity of deletion with a given node is O(n), because the previous node needs to be known, and traversal takes O(n) |
Complexity of deletion with a given node is O(1) because the previous node can be accessed easily |
| A singly linked list consumes less memory as compared to the doubly linked list. |
The doubly linked list consumes more memory as compared to the singly linked list. |
Conclusion:
There are many advantages of the linked list compared to array, despite the fact that they solve the similar problem to arrays, we have also discussed the advantage, disadvantages, and its application, and we concluded the fact that we can use a linked list if we need the dynamic size of storage and list are good for adding and removing items quickly or for tasks that require sequence but are not suitable for querying or search elements in a large collection of data.
So, it becomes important that we should always keep in mind the positive and negative aspects of a data structure and how they relate to the problem you are trying to solve.
Related articles:
Similar Reads
Linked List Data Structure
A linked list is a fundamental data structure in computer science. It mainly allows efficient insertion and deletion operations compared to arrays. Like arrays, it is also used to implement other data structures like stack, queue and deque. Here’s the comparison of Linked List vs Arrays Linked List:
3 min read
Basic Terminologies of Linked List
Linked List is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers. Linked List forms a series of connected nodes, where each node stores the data and the address of the next node. Node Structure: A node in a linked list typically
3 min read
Introduction to Linked List - Data Structure and Algorithm Tutorials
Linked List is basically chains of nodes where each node contains information such as data and a pointer to the next node in the chain. It is a popular data structure with a wide range of real-world applications. Unlike Arrays, Linked List elements are not stored at a contiguous location. In the lin
10 min read
Applications, Advantages and Disadvantages of Linked List
A Linked List is a linear data structure that is used to store a collection of data with the help of nodes. Please remember the following points before moving forward. The consecutive elements are connected by pointers / references.The last node of the linked list points to null.The entry point of a
4 min read
Linked List vs Array
Array: Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked List: Linked lists are less rigid in their storage structure and elements are usually not stored in co
2 min read
Basic Operations on Linked List
Insertion in Linked List
Given a Linked List, the task is to insert a new node in this given Linked List at the following positions: At the front of the linked list Before a given node.After a given node.At a specific position.At the end of the linked list.Insert a Node at the Front/Beginning of Linked ListTo insert a new n
15+ min read
Search an element in a Linked List (Iterative and Recursive)
Given a linked list and a key, the task is to check if key is present in the linked list or not. Examples: Input: 14 -> 21 -> 11 -> 30 -> 10, key = 14Output: YesExplanation: 14 is present in the linked list. Input: 6 -> 21 -> 17 -> 30 -> 10 -> 8, key = 13Output: NoExplanat
13 min read
Find Length of a Linked List (Iterative and Recursive)
Given a Singly Linked List, the task is to find the Length of the Linked List. Examples: Input: LinkedList = 1->3->1->2->1Output: 5 Input: LinkedList = 2->4->1->9->5->3->6Output: 7 Iterative Approach to Find the Length of a Linked List:The idea is similar to traversal o
11 min read
Reverse a Linked List
Given a linked list, the task is to reverse the linked list by changing the links between nodes. Examples: Input: head: 1 -> 2 -> 3 -> 4 -> NULLOutput: head: 4 -> 3 -> 2 -> 1 -> NULLExplanation: Reversed Linked List: Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> NULLOu
15+ min read
Deletion in Linked List
Deleting a node in a Linked List is an important operation and can be done in three main ways: removing the first node, removing a node in the middle, or removing the last node. In this article, we will explore deletion operation on Linked List for all the above scenarios. Types of Deletion in Linke
15+ min read
Delete a Linked List node at a given position
Given a singly linked list and a position (1-based indexing), the task is to delete a linked list node at the given position. Note: Position will be valid (i.e, 1 <= position <= linked list length) Example: Input: position = 2, Linked List = 8->2->3->1->7Output: Linked List = 8-
8 min read
Write a function to delete a Linked List
Given a linked list, the task is to delete the linked list completely. Examples: Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> NULLOutput: NULLExplanation: Linked List is Deleted.Input: head: 1 -> 12 -> 1 -> 4 -> 1 -> NULLOutput: NULLExplanation: Linked List is Deleted. Table o
9 min read
Write a function to get Nth node in a Linked List
Given a LinkedList and an index (1-based). The task is to find the data value stored in the node at that kth position. If no such node exists whose index is k then return -1. Example: Input: 1->10->30->14, index = 2Output: 10Explanation: The node value at index 2 is 10 Input: 1->32->
11 min read
Program for Nth node from the end of a Linked List
Given a Linked List of M nodes and a number N, find the value at the Nth node from the end of the Linked List. If there is no Nth node from the end, print -1. Examples: Input: 1 -> 2 -> 3 -> 4, N = 3Output: 2Explanation: Node 2 is the third node from the end of the linked list. Input: 35 -
15 min read
Top 50 Problems on Linked List Data Structure asked in SDE Interviews
A Linked List is a linear data structure that looks like a chain of nodes, where each node is a different element. Unlike Arrays, Linked List elements are not stored at a contiguous location. Here is the collection of the Top 50 list of frequently asked interview questions on Linked Lists. Problems
3 min read