The complexity of list operations depends on traversal. For a linked list of n nodes, the isEmpty()
method is O(1), as it only compares the first node to see if it is an empty environment. Similarly, the sizeLinkList()
method requires O(n) operations to determine the length of a linked list, as the linked list has to traverse through all the nodes for length determination.
The deletion and searching for an item in the linked list in worst case will take O(n) operations, as the pointer may have to scan through all the nodes before it finds the item for deletion. On the other hand, the addElement()
method will take O(1) time as it is directly adding a new element to the head of the linked list. Insertion based on position will take O(p) time, as the linked list has to traverse through p nodes before performing an insertion. For example, say we want to insert 11
at the third position in the list <1, 2, 5, 4>
. The current insertion operation will require the...