Easy to create and use

Direct indexing: O(1)

Sequential access: O(n)

Sorting: O(nlog(n))

Searching: O(n) and O(log(n)) if sorted

Inserting and deleting: O(n) because of shifting items.

Inserting and deleting: O(1)

Sequential Access: O(n)

No direct access (only sequential access)

Searching: O(n)

Sorting: O(nlog(n))

Uses more storage space compared to Arrays

Collections: Mutable arrays, Sparse Matrices, Trees, Graphs, Queues, Stacks

Dynamic Memory Allocation

Persistent Data Structures

Ordered sets implentation

Indexes

Lock-free shared memory

Highly scalable concurrent priority queues with less lock contention

Lock-free concurrent dictionaries

3D Sparse Grid for Robot Mapping systems

Moving medians

Push/Add: O(1)

Pop/Remove: O(1)

Peek: O(1)

Searching: O(n)

Random Access: O(n)

Track method calls or the state of a program

Depth-first search

Expression Handling

Push/Add: O(1)

Pop/Remove: O(1)

Peek: O(1)

Searching: O(n)

Random Access: O(n)

Network packets

I/O requests

Inserting and deleting: O(1) + Hashing & Indexing (amortized)

Direct access: O(1) + Hashing & Indexing

Some overhead (requires a bit more memory space compared to arrays)

Retrieval of elements not guaranteed to be in specific order

Searching for a value (without knowing it’s key)

Caching

Look-up Tables

Database indexing

Sets

Graph representation

Fast insert / access storage

Checking membership / value existence

Avoid duplicates

Limited use cases

Performance depends on underlying implementation (hash table vs tree)

Finite unique collection representation

Extends the capability of a normal array

Inserting, deleting and accessing: O(log(n))

Fast search of values: O(log(n))

Retrieval of elements is in order

Scales better than linked lists

Bad performance when unbalanced: O(n)

Some overhead

Slower access than arrays

Bad performance for concurrent access compared to skip lists

Not as optimized for cpu cache levels as arrays (**)

Grows slower than linked lists

Efficiently maintains a dynamically changing dataset in sorted order

Database indexing: Element comparison in a less than / greater than manner

Binary Tries: Networking (storing router-tables)

Hash Trees: p2p programs, specialized image-signatures in which a hash needs to be verified, but the whole file is not available

Heaps

Persistent Data Structures

Min/Max search: O(1)

Inserting: O(log(n))

Min/Max Deletion: O(log(n))

Searching and deleting: O(n)

Efficient priority-queues

Process scheduling

Path-finding: Robotics, video games

Great for static / slow updating systems [2]

Faster search than Red–Black trees for lookup-intensive applications [2]

Slow inserts and deletes if unbalanced (even if slightly) [2]

Slow for fast updating systems [2]

Fast data search [2]

Simplest implementation of all trees [3]

Sequential storage on disk [4]

Faster insertion and deletion than other trees (no rebalancing mechanism) [4]

Smaller memory footprint [4]

Poor performance if not balanced [5]

No self-balacing mechanisms [3]

Sorting algorithms [4]

Main-memory data structures [4]

Basic framework for other tree implementations [4]

Better for disk I/O (also check B+-Trees) [6][7]

Uses memory caching to offset searching costs [7]

Expensive insertion and deletion for trees with a large branching factor [7]

Simple implementation [8]

The lowest common ancestor between two nodes is the minimum node between them [8]

Efficient operations on sub-trees: O(log(n)) [9]

Search, insertion and deletion: O(n) [1]

Higher overhead compared to other trees [9]

Sorting [10]

Treaps [10]

Suffix trees [10]

Efficiently solves the range minimum query (RMQ) by finding the lowest common ancestor (LCA) [11]

Fast search for low dimensional data (e.g., 2D/3D space) [13]

Degradation in performance with high-dimensional data [13]

Organizing points in a k-dimensional space [13]

Multidimensional search: range-search, nearest-neighbour [12][13]

Creates a distinct ”root” for each unique set of values [14]

Hability to reconstruct the root and / other branches [14]

Size of the proofs increase logarithmically with the number of values and the branching factor of the tree [17]

Susceptible to second-preimage attacks if not implemented correctly [14]

Hash-based cryptography [15]

File systems: IPFS, Btrfs, ZFS [14]

Distributed version control systems: Git, Mercurial [14]

Blockchain: Bitcoin [14]

Peer-to-peer networks: Ethereum [14]

Certificate authorities [16]

NoSQL databases [14]

Slower search than AVL trees for lookup-intensive applications [2]

Libraries: map, multimap, multiset [18]

Schedulers [20]

Collections: Associative Arrays, Sets, Hash Maps, Persistent Data Structures [19]

Access of recently searched items in O(1) [21]

Better read performance compared to AVL trees [21]

Smaller memory footprint: does not store additional information as AVL / Red-Black Trees [23]

Height can be linear [23]

Trees are not strictly balanced [22]

Difficult to use in multi-threaded environments: defeats memory caches and can create unnecessary lock contention [23][24]

Worse performance for random access patterns compared to AVL / Red-Black Trees [23]

Virtual memory [21]

Networking [21]

File systems [21]

Compilers [21]

Recommended searches [24]

Data compression algorithms [25]

pInsert and find strings in O(L) [28]

Easily print all words in alphabetical order [28]

Huge memory for storing the strings [28]

Sorting algorithms [26]

Autocomplete dictionary [26]

Spell checking [26]

Longest prefix matching [27]

Browser history [27]