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

Algorithms

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)

Usage

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

Where number of items is unknown

HashMap

Implementation

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

Usage

Caches

Storing data with keys

One of most useful data structures

Trees

Trie tree

Link

Used for storing info about words

Easy search

Usage, Dictionaries, In suggest snippets

Binary

Unordered

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

Algorithms

Generate all possible trees

Self-balancing

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

B-tree

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

Hierarchies

DOM, XML

Fenwick tree

Quick calculation sum of elements from i to j in arrays

Array/List

Algorithms

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

Usage

For storing indexed data

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

Graphs

Algorithms

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'

Directed

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

Acyclic

Path between two vertices, Article

Usage

Representing complex structures

Modelling (networks, etc)

Stacks

With const time for push, pop, min

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

Link

Usage

Stacks in memory

In DFS

For saving contexts in processors

Features

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

Heap

Tree

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

Translation to array

Very simple. Rows, from left to right

Algorithms

Heapsort

Usage

For top k elements, O(nlogk)

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

Space structures

K-D tree

Hyperplanes

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

Probabilistic

Bloom Filter