Linked List:
- Accessing an element:
When you want to find an element in the linked list based on its position (index), you have to start from the beginning of the list and go through each element one by one until you reach the desired position. This process takes longer as the list gets bigger, so the time it takes to find the element is directly proportional to the number of elements in the list. We call this time complexity “O(n)”, where ‘n’ is the number of elements in the linked list.
- Insertion at the beginning:
When you add an element to the beginning of the linked list, you just need to create the new element and make it the new first element of the list. This operation is quick and does not depend on how many elements are already in the list. Therefore, we say the time complexity is “O(1)”, which means it takes constant time, regardless of the list size.
- Insertion at the end:
When you insert an element at the end of the linked list, you have to go through the entire list to find the last element and then add the new element after it. The time it takes to do this is directly related to the number of elements in the list, so we say the time complexity is O(n)n where ‘n’ is the number of elements in the linked list.
- Insertion in the middle (based on index or value):
If you want to insert an element in the middle of the linked list, you need to first find the position where you want to insert it. This involves going through the list, element by element, until you reach the right position. Therefore, like before, the time it takes to do this is directly proportional to the number of elements in the list, so the time complexity is “O(n)”.
- Deletion at the beginning:
When you remove the first element from the linked list, you only need to update the list’s starting point to the second element. This operation is quick and does not depend on the list size, so the time complexity is “O(1)” or constant time.
- Deletion at the end:
If you want to delete the last element in the linked list, you have to traverse the entire list to find the second to last element. After finding it, you can remove the last element. Since the time taken to find the second to last element increases with the number of elements in the list, the time complexity is “O(n)”, where ‘n’ is the number of elements in the linked list.
- Deletion in the middle (based on index or value):
Deleting an element from the middle of the linked list is similar to inserting in the middle. You first need to find the element you want to delete by going through the list until you locate it. After that, you can remove it. As with finding a position or value, the time taken to delete an element from the middle is also directly related to the number of elements in the list, so the time complexity is “O(n)”.
