Thread by @oliverjumpertz

Data structures and algorithms are important for any software developer.

Sometimes loved, more often dreaded, but at the core of our craft.

Here is an introduction to the most important data structures, including learning resources.

A thread. ↓

1. Why you need to learn them

The reality is: You will and should never implement many data structures yourself on the job.

There are libraries for this purpose. Either a language's standard library or a commonly used library will provide them for you.

But is this all?

To decide which data structure you need in what case, you should know about them in the first place.

You need to know:

- Which exist
- What they are good for
- How they work
- Their runtime characteristics (time and space complexity)
- Their pros
- And cons

If you, e.g., want to store values related to keys and also want to loop over the entries in the order they were inserted, you need to know that you:

- Need a map
- Backed by a tree

And you should know that maps backed by trees need a little longer to insert and find entries.

To make this decision, you will need that knowledge about data structures and their traits.

This is the first reason for you to learn about them well at least once.

And well means knowing exactly what's stated above—all of it.

You should even go so far as to implement them all and the algorithms belonging to them, at least once.

You can learn any theory, but doing it yourself will make this knowledge definitely stick.

Many developers tend to remember things they implemented themselves way better than things they only learned in theory.

This way can save you a lot of time you would otherwise spend reading theory over and over again.

Learning the algorithms associated with data structures also greatly benefits you: You will cover all common algorithmic techniques at least once.

You won't need this knowledge to implement a breadth-first-search yourself, but it might help you with the problems you tackle.

Once again, in case it didn't become clear enough:

You probably only need to do this once as long as the knowledge all this brings you sticks.

Only if you somehow lose this knowledge because you haven't worked with it for a longer time, repeat the process.

2. What you should know

You should cover the most prominent data structure groups:

- Arrays
- Lists
- Queues
- Stacks
- Sets
- Trees
- Graphs
- Hash tables

Many of the entries above actually contain different implementations, and of those different implementations, equally as many contain other data structures to back their own implementation.

This is why you reach a certain synergy effect at some point.

Let's look at them a little deeper while you get to know a few of their traits and their average time complexity.

You can use this information as a base for your own research because there is way more to those than only the following information.

-> Arrays

- Most primitive and native data structure
- Linear data structure, values are stored one after the other
- Static in size, once initialized not resizable
- Base for many other data structures

Average time complexity of common array operations:

Access: O(1)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

-> Lists

- Complex data structures but still pretty basic
- Can be backed by arrays or come as linked lists (singly, doubly linked)
- Linear data structure, values are stored one after the other
- Dynamic in size
- Base for other data structures

Average time complexity of common list operations:

(Singly- and Doubly-Linked)

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

-> Queues

- Linear data structure
- First-in-first-out
- Can be backed by an array or more prominently by a linked list
- Dynamic in size
- Often used to store work that is to be processed one after the other
- Has more implementations with different additional traits

Average time complexity of common queue operations:

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

-> Stacks

- Linear data structure
- Last-in-first-out
- Can be backed by an array or more prominently by a linked list (sometimes by a Dequeue)
- Dynamic in size
- Undo operations are usually based on stacks, for example

Average time complexity of common stack operations:

Access: O(n)
Search: O(n)
Insertion: O(1)
Deletion: O(1)

-> Sets

- One of a kind (unique value) storage
- Can be backed by a hash table or a tree
- Dynamic in size
- Especially used when you only want unique values of any kind
- Can be ordered and unordered

Average time complexity of common set operations:

(backed by some form of hash table)

Access: O(1)
Search: O(1)
Insertion: O(1)
Deletion: O(1)

-> Trees

- A recursive collection of nodes
- Dynamic in size
- Can be ordered and unordered
- Can contain unique and non-unique values
- Often used to model documents or by your favorite programming language's parser (Abstract Syntax Tree)

Average time complexity of common tree operations:

(Red-Black-Tree)

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

-> Graphs

- Non-linear data structure
- Consists of nodes (vertex) and edges
- Can store information on its edges
- Can be directed and undirected
- Dynamic in size
- Often used to represent networks (your Facebook connections can be represented as a graph, e.g.)

Average time complexity of common graph operations:

(Adjacency Matrix)

Access: O(1)
Search: O(1)
Insertion: Edge: O(1), Vertex: O(|V|^2)
Deletion: Edge: O(1), Vertex: O(|V|^2)

-> Hash tables

- Key-value mapping
- Uses math operations to map a hash value to a spot in a table
- Unordered
- Needs keys that are hashable
- Dynamic in size
- Often used when quick lookup of values by keys is needed

Average time complexity of common hash table operations:

Access: O(1)
Search: O(1)
Insertion: O(1)
Deletion: O(1)

3. Where you can learn more about them

-> GeeksforGeeks

GeeksforGeeks has an incredible collection of articles and how-tos on data structures and algorithms.

Most articles also include implementations in different programming languages.

geeksforgeeks.org/data-structure…

-> Programiz

A full collection of nearly everything you need to know about algorithms and data structures.

Implementations are usually in C, C++, Python, and more.

programiz.com/dsa

-> JavaScript Algorithms

This repository on GitHub will teach you a lot about algorithms and data structures and everything in JavaScript!

Definitely worth a look. Especially if you want to improve your A&DS skills with JavaScript.

github.com/trekhleb/javas…

4. Thread end

That's it for this thread. 💛

I hope you found something useful in it for you. 🙏🏼

If you enjoyed reading this, consider liking the thread, retweet the first tweet, and follow me (@oliverjumpertz) for more content like this.