How to determine the duration of operations with a LinkedList data structure?

To determine the time complexity of operations with a LinkedList, it is necessary to analyze how the structure is organized and how the operations are implemented.

For a singly or doubly linked list:

• Access by index: O(n), since you need to traverse from the beginning to the desired element.
• Insertion/deletion at the beginning of the list: O(1), as it is enough to change the links to the first element.
• Insertion/deletion at the end of the list:
  • If there is a pointer to the tail — O(1)
  • If not — O(n), since you need to traverse the entire list.
• Search for an element by value: O(n), as you need to traverse the list until the element is found.

To estimate the execution time of operations, profiling or measuring time using System.nanoTime() in Java can be used:

LinkedList<Integer> list = new LinkedList<>();
long start = System.nanoTime();
// operation, for example, adding an element
list.addFirst(10);
long end = System.nanoTime();
System.out.println("Operation time: " + (end - start) + " ns");

But for understanding the algorithmic complexity, it is enough to know that LinkedList is optimal for insertion/deletion operations at the beginning/end, but not for fast access by index.