with our free apps for iPhone, iPad and Android

Get StartedAlready have an account? Log In

Data structures
by Alexander Shuiskov
# Data structures

## Linked list

### Algorithms

### Usage

## HashMap

### Implementation

### Usage

## Trees

### Trie tree

### Binary

### In programming

### Algorithms

### Self-balancing

### B-tree

### B+ tree

### 2-4 Trees

### Interval tree

### General usage

### Fenwick tree

## Array/List

### Algorithms

### Usage

## Graphs

### Algorithms

### Directed

### Acyclic

### Usage

## Stacks

### With const time for push, pop, min

### Usage

### Features

## 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

### Algorithms

### Usage

## Space structures

### K-D tree

## Probabilistic

### Bloom Filter

5.0 stars - 5 reviews
range from 0 to 5

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

Caches

Storing data with keys

One of most useful data structures

Link

Used for storing info about words

Easy search

Usage, Dictionaries, In suggest snippets

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

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)

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?)

Like B trees with 2,3 or 4 children

Usage, Queues, Graphics (finding overlap zones)

Hierarchies

DOM, XML

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)

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

Link

Stacks in memory

In DFS

For saving contexts in processors

Unknown length

No need to sort

O(1) of getting the head

Very simple. Rows, from left to right

Heapsort

For top k elements, O(nlogk)

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

Hyperplanes

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