Why do we use multiple data structures? [duplicate]

Question

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees.

Both runs in worst case O(n) in the same operations, so why don't we use only one data structure?

Answer 1

Aspects other than asymptotic worst case time are also important. For example

• Actual speed in practice
• Memory consumption
• Implementation difficulty

Algorithmic analysis almost never tells you the complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".

Answer 2

$O(n)$ in BST means it was case degraded to Single Linked List, but it still has two pointers per node, while linked list has only one. But for balanced or almost balanced tree, the operations are $O(\log n)$. You can keep it balanced (using for example AVL tree or Red Black Tree, where both differ in cost of insert and delete by constant factor).
Linked list allows you to traverse in one direction, Doubly Linked List allows you to move in the both directions, it has two pointers per node, also if you do not use traversal in one direction, the cost of insert / delete is lower for Single Linked List. The notation makes this constant disappear. So taking memory footprint, actual time per unit operation, size of data stored, your needs and time to implement given data structure makes them differ a lot.

Also there are structures like Fibonacci heap, very good asymptotically, but rather heavy on small data and harder to implement.

There is no such structure that fits every situation and optimizes every possible feature, otherwise we would use only this one and learn about others for educational purposes only (or to stop people from reinventing the wheel).