Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

Data structures by Mind Map: Data structures
5.0 stars - 5 reviews range from 0 to 5

Data structures

Linked list


Determine whether has cycles, Article, Idea, 2 pointers, 1 pointer has speed 1 el/iteration, another - 2 el/iteration, If they visit before the first pointer reaches the end - has cycles, O(n) worst case, no additional memory

Reverse linked list, Article, O(n)


For queries, Messaging, Scheduling, In BFS, DFS algorithms

Where number of items is unknown



non-threadsafe, Article, hash function, h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);, Used to decrease number of collisions, Max 8 by default, default initial capacity - MUST be a power of two., Max capacity MUST be a power of two, load factor, Index of element, hash & (length - 1), length is power of 2 so this will return 1111 bit mask

threadsafe, Simple, Lack of scalability bacause of locks, ConcurrentHashMap, Segments, Further improvement with buckets, coucurrencyLevel, if only 1 thread changes data - 1, Article



Storing data with keys

One of most useful data structures


Trie tree


Used for storing info about words

Easy search

Usage, Dictionaries, In suggest snippets



BST, Ordered, Algorithms, Given a pre-order and post-order traversal results, restore te BST, Article, Article, Usage, Storing data, easy access, Better use balanced ones

In programming

Scaling, Trees scale not good. HashMap is better


Generate all possible trees


RB tree, Rotation, quite simple, Rules, Root: black, Red can have only black childs, Black height of each leaf is const

AVL, First such structure, Balance factor (-1, 0, 1), Flips, Wiki

Usage, For storing sorted data where access time equal to log(n) is needed, Representing hierarchies


Complexity, O(logn)

Leaves and nodes contain elements

Links to next elements (organize single-linked list)

B+ tree

Nodes don't contain data, only leaves

Leaves organize wide list, Easy iteration, easy deletion, A big plus in block systems

Usage, Block data systems, File systems, RDBMS (storing blobs?)

2-4 Trees

Like B trees with 2,3 or 4 children

Interval tree

Usage, Queues, Graphics (finding overlap zones)

General usage



Fenwick tree

Quick calculation sum of elements from i to j in arrays



Sorting, Bubble sort, One of the slowest, O(n^2), Complete loop from 0, 1...n-1 el, Merge sort, O(nlogn), Article, Idea, Recusrive sort, After sorting left & right part we merge them: O(m+n), Insertion ort, Worst case: O(n^2), Best case: O(n), Idea, Start from 1-sorted array and go to left, Each iteration there is a sorted array in the left part, Bucket sort, Article, Quicksort, Complexity, Worst case: O(n^2), Avg case: O(nlogn), Idea, Recursive algorithm like mergesort, Take a random pivot from list, All els less than pivot move to list1, All els greater than pivot move to list2, Concatenate(quicksort(list1),pivot,quicksort(list2)), Table of complexity, Radix sort, O(mk), Sort last set of digits, then sort previous etc, Heapsort, in-memory, Complexity, All cases: O(nlogn), Counting sort, Linear time, linear space, Used for data in small ranges

Max increasing sequence in an array, Article, Complexity, Time: O(n^2), Memory: O(n), Idea, Use accumulatedLength for each element

Min and max elements, Recursive, Sort (nlogn), Find (n), Non-recursive, O(n), Article

Find firt pair of dublicates, Additional memory, HashMap with occurences, O(n) time O(n) worst case map, Without additional memory, O(nlogn)

Find common elements in 2 arrays, Article, Idea, Sort both arrays: O(m) and O(n), Walt through both: O(m+n)

Find a number in a sorted array, Idea, Dichotomy method, Article

Find a median in distributed collection on thouands of servers, Article, Idea, Median of medians, O(n)

Maximum contigious ubsequent sum problem, Article, Idea, Walk from 0 to n-1, If accumulated sum is negative - reset


For storing indexed data

When element size matters (approx 8 times less than other data structures)



Traversal, BFS, Nearest elements are added to the end of query, DFS, Nearest els are added to the begin of the query

Prim apgorithm - find the minimal spanning tree, Select any vertex, Each step add to the tree the nearest edge with min weight

Does represent a tree?, No cycles, Linked, Article

Longest path in graph, Article

Paths rom all to all, Warshall-Floyd algorithm, O(n^3), Link

Min path, Dijkstra algorithm

A*, Improvement of Dijkstra algorithm, Uses heuristics, Result is sum of 2 functions: minDistance + h(x). h(x) is heuristical function, Named 'best-first'


weighted, Dijkstra algorithm - find min distance from one vertex to anothers, Link, Impl


Path between two vertices, Article


Representing complex structures

Modelling (networks, etc)


With const time for push, pop, min

O(n) additional memory for havingg min(Stepi)



Stacks in memory


For saving contexts in processors


Unknown length

No need to sort

O(1) of getting the head

In programming

Element cost in data structures

Priority Queue

Pop high-priority element: O(1)

Implementing using heap



if B is a child node of A, then key(A) ≥ key(B)

Translation to array

Very simple. Rows, from left to right




For top k elements, O(nlogk)

Heapsort (in-memory O(nlog(n))

Space structures

K-D tree


To the left of hyperplane - one part, to the right - second. (as a hyperplace an X axis can be used)


Bloom Filter