Space is o n unless otherwise specified. |  | Array: |  | Average | theta 1 access, theta n search, theta n insertion, theta n deletion |  | Worst | O 1 access, O n search, O n insertion, O n deletion |  |  | Stack: |  | Average | theta n access, theta n search, theta 1 insertion, theta 1 deletion |  | Worst | O n access, O n search, O 1 insertion, O 1 deletion |  |  | Queue: | theta n access, theta n search, theta 1 insertion, theta 1 deletion |  | Worst: | o n access, o n search, o 1 insertion, o 1 deletion |  |  | Singly-linked list: |  | Average |  | theta n access, theta n search, theta 1 insertion, theta 1 deletion |  | Worst | o n access, o n search, o 1 insertion, o 1 deletion |  | Doubly-linked list: |  | Average | theta n access, theta n search, theta 1 insertion, theta 1 deletion |  | Worst | o n access, o n search, o 1 insertion, o 1 deletion |  | Skip list |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o n access, o n search, o n insertion, o n deletion |  | Memory | o n log n |  | Hash Table |  | Average | theta 1 access/search, theta 1 insertion, theta 1 deletion |  | Worst | o n access/search, o 1 insertion, o 1 deletion |  | Binary Search Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o n access, o n search, o n insertion, o n deletion |  | Cartesian Tree |  | Average | theta log n search/access, theta n insertion, theta n deletion |  | Worst | o n search/access, o n insertion, o n deletion |  | B-Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o log n access, o log n search, o log n insertion, o log n deletion |  | Red-Black Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o log n access, o log n search, o log n insertion, o log n deletion |  | Splay Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o log n access, o log n search, o log n insertion, o log n deletion |  | AVL Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o log n access, o log n search, o log n insertion, o log n deletion |  | KD Tree |  | Average | theta log n access, theta log n search, theta log n insertion, theta log n deletion |  | Worst | o n access, o n search, o n insertion, o n deletion