In case the node which is deleted is the last node, one needs to ensure that END now points to TEMP. In order to delete an element from the any other position (including the last position), one needs to traverse the linked list until they reach the node before the node that is to be deleted(let this node be TEMP), and ,make this point to the node which succeeds the node to be deleted. This situation arises when any other element needs to be deleted. Since this operation takes constant time, and does not need any extra space, both the time and the space complexity of this operation is given by O(1). For this operation, we only need to make the last element of the linked list point to the element that the first element of the linked list is pointing to. The best case is observed when the deletion is at the beginning. The worst case time complexity also happens to be O(n), which would arise when the element needs to be inserted at the (n-1) th position. Since this operation takes up constant space, the space complexity of this operation is given by O(1). Hence, the time complexity of this operation is given by O(n). Note that traversal in a linked list is of O(n) (since one needs to go through the elements one by one until the required position is reached), and that the insertion after reaching the required position is of constant time complexity. Then, one needs to make the previous element point to this new element, and the new element to point to the next element of the linked list. If one needs to insert a node at a given position(not the beginning or the end of the linked list), then one shall first need to traverse to this position. The average case can be observed when insertion is at any position other than the beginning or at the end. Hence this is an advantage that the Circular Linked List provides over the normal linked list. Note that in a normal linked list, this operation would have a time complexity of O(n), since one needs to traverse to the end of the linked list first. This is similar to insertion at the beginning, and hence both the time and space complexity of this operation is given by O(1). In order to insert an element at the end, one needs to make the last element as well as the END pointer to point to the new node, and the new node to point to the first element. Since the space required is also constant, the space complexity is given by O(1). Since both these operations take constant time, the time complexity of this operation is given by O(1). To insert an element at the beginning, one shall need to make the last element point to the new element, and to make the new element point to the previously first element. We observe the best case of insertion in a circular linked list when the element is to be inserted at the beginning or at the end. As there is no extra space used, the space complexity is given by O(1). Hence, the time complexity of traversal is given by O(n). If there are n elements in the circular linked list, this operation shall run at most n times, until it reaches the element from which it started. Note that one can start from any one element of the linked list. In case one wants to traverse the entire linked list, or search for a particular element, one shall first start with the element that *END* is pointing to, and then go through each element of the linked list. We shall now analyze the time and space complexity of the various operations that can be performed on a circular linked list, such as traversal, insertion, and deletion. The circular linked list can be represented as follows: The circular linked list also enables traversal of the entire linked list starting from any one point. Since the last element points to the first element, this enables quick traversal from the last element to the first. This linked list comes with a pointer END which points to the last element.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |