What is the complexity of accessing an element in various data structures?

Access complexity to an element depends on the type and implementation of the data structure.

Main data structures and their access complexity:

• Array:

  • Complexity: O(1)
  • Access is by index, knowing the starting address and element size.

• Linked List:

  • Complexity: O(n) in the worst case (for singly linked), O(n) in the best case (if the element is the first)
  • Requires sequential traversal from the beginning of the list to the desired element.

• Tree:

  • Binary Search Tree:
    • Complexity: O(log n) on average, O(n) in the worst case (degenerate tree)
    • Efficient for search, insertion, and deletion.
  • Balanced Tree (e.g., AVL, Red-Black Tree):
    • Complexity: O(log n)
    • Maintains logarithmic operation complexity through balancing.

• Hash Table:

  • Complexity: O(1) on average, O(n) in the worst case (with collisions)
  • Access is by hash of the key, which points to the data storage location.

Example for array:

// Access to array element by index
int arr[] = {1, 2, 3, 4, 5};
int element = arr[2]; // O(1)

Example for singly linked list:

// Searching for an element in a singly linked list
struct Node {
    int data;
    Node* next;
};

Node* head = ...; // Start of the list
int target_data = 3;
Node* current = head;
while (current != nullptr) {
    if (current->data == target_data) {
        // Element found
        break; // Worst-case complexity O(n)
    }
    current = current->next;
}