Data structures

Get Started. It's Free
or sign up with your email address
Rocket clouds
Data structures by Mind Map: Data structures

1. HashMap

1.1. Implementation

1.1.1. non-threadsafe

1.1.1.1. Article

1.1.1.2. hash function

1.1.1.2.1. h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);

1.1.1.3. default initial capacity - MUST be a power of two.

1.1.1.4. Max capacity MUST be a power of two

1.1.1.5. load factor

1.1.1.6. Index of element

1.1.1.6.1. hash & (length - 1)

1.1.2. threadsafe

1.1.2.1. Simple

1.1.2.1.1. Lack of scalability bacause of locks

1.1.2.2. ConcurrentHashMap

1.1.2.2.1. Segments

1.1.2.2.2. Further improvement with buckets

1.1.2.2.3. coucurrencyLevel

1.1.2.3. Article

1.2. Usage

1.2.1. Caches

1.2.2. Storing data with keys

1.2.3. One of most useful data structures

2. Trees

2.1. Trie tree

2.1.1. Link

2.1.2. Used for storing info about words

2.1.3. Easy search

2.1.4. Usage

2.1.4.1. Dictionaries

2.1.4.2. In suggest snippets

2.2. Binary

2.2.1. Unordered

2.2.2. BST

2.2.2.1. Ordered

2.2.2.2. Algorithms

2.2.2.2.1. Given a pre-order and post-order traversal results, restore te BST

2.2.2.3. Article

2.2.2.4. Usage

2.2.2.4.1. Storing data, easy access

2.2.2.4.2. Better use balanced ones

2.3. In programming

2.3.1. Scaling

2.3.1.1. Trees scale not good. HashMap is better

2.4. Algorithms

2.4.1. Generate all possible trees

2.5. Self-balancing

2.5.1. RB tree

2.5.1.1. Rotation

2.5.1.1.1. quite simple

2.5.1.2. Rules

2.5.1.2.1. Root: black

2.5.1.2.2. Red can have only black childs

2.5.1.2.3. Black height of each leaf is const

2.5.2. AVL

2.5.2.1. First such structure

2.5.2.2. Balance factor (-1, 0, 1)

2.5.2.3. Flips

2.5.2.4. Wiki

2.5.3. Usage

2.5.3.1. For storing sorted data where access time equal to log(n) is needed

2.5.3.2. Representing hierarchies

2.6. B-tree

2.6.1. Complexity

2.6.1.1. O(logn)

2.6.2. Leaves and nodes contain elements

2.6.3. Links to next elements (organize single-linked list)

2.7. B+ tree

2.7.1. Nodes don't contain data, only leaves

2.7.2. Leaves organize wide list

2.7.2.1. Easy iteration, easy deletion

2.7.2.1.1. A big plus in block systems

2.7.3. Usage

2.7.3.1. Block data systems

2.7.3.1.1. File systems

2.7.3.1.2. RDBMS (storing blobs?)

2.8. 2-4 Trees

2.8.1. Like B trees with 2,3 or 4 children

2.9. Interval tree

2.9.1. Usage

2.9.1.1. Queues

2.9.1.2. Graphics (finding overlap zones)

2.10. General usage

2.10.1. Hierarchies

2.10.2. DOM, XML

2.11. Fenwick tree

2.11.1. Quick calculation sum of elements from i to j in arrays

3. Array/List

3.1. Algorithms

3.1.1. Sorting

3.1.1.1. Bubble sort

3.1.1.1.1. One of the slowest

3.1.1.1.2. O(n^2)

3.1.1.1.3. Complete loop from 0, 1...n-1 el

3.1.1.2. Merge sort

3.1.1.2.1. O(nlogn)

3.1.1.2.2. Article

3.1.1.2.3. Idea

3.1.1.3. Insertion ort

3.1.1.3.1. Worst case: O(n^2)

3.1.1.3.2. Best case: O(n)

3.1.1.3.3. Idea

3.1.1.4. Bucket sort

3.1.1.4.1. Article

3.1.1.5. Quicksort

3.1.1.5.1. Complexity

3.1.1.5.2. Idea

3.1.1.6. Table of complexity

3.1.1.7. Radix sort

3.1.1.7.1. O(mk)

3.1.1.7.2. Sort last set of digits, then sort previous etc

3.1.1.8. Heapsort

3.1.1.8.1. in-memory

3.1.1.8.2. Complexity

3.1.1.9. Counting sort

3.1.1.9.1. Linear time, linear space

3.1.1.9.2. Used for data in small ranges

3.1.2. Max increasing sequence in an array

3.1.2.1. Article

3.1.2.2. Complexity

3.1.2.2.1. Time: O(n^2)

3.1.2.2.2. Memory: O(n)

3.1.2.3. Idea

3.1.2.3.1. Use accumulatedLength for each element

3.1.3. Min and max elements

3.1.3.1. Recursive

3.1.3.1.1. Sort (nlogn)

3.1.3.1.2. Find (n)

3.1.3.2. Non-recursive

3.1.3.2.1. O(n)

3.1.3.3. Article

3.1.4. Find firt pair of dublicates

3.1.4.1. Additional memory

3.1.4.1.1. HashMap with occurences

3.1.4.1.2. O(n) time O(n) worst case map

3.1.4.2. Without additional memory

3.1.4.2.1. O(nlogn)

3.1.5. Find common elements in 2 arrays

3.1.5.1. Article

3.1.5.2. Idea

3.1.5.2.1. Sort both arrays: O(m) and O(n)

3.1.5.2.2. Walt through both: O(m+n)

3.1.6. Find a number in a sorted array

3.1.6.1. Idea

3.1.6.1.1. Dichotomy method

3.1.6.2. Article

3.1.7. Find a median in distributed collection on thouands of servers

3.1.7.1. Article

3.1.7.2. Idea

3.1.7.2.1. Median of medians

3.1.7.2.2. O(n)

3.1.8. Maximum contigious ubsequent sum problem

3.1.8.1. Article

3.1.8.2. Idea

3.1.8.2.1. Walk from 0 to n-1

3.1.8.2.2. If accumulated sum is negative - reset

3.2. Usage

3.2.1. For storing indexed data

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

4. Graphs

4.1. Algorithms

4.1.1. Traversal

4.1.1.1. BFS

4.1.1.1.1. Nearest elements are added to the end of query

4.1.1.2. DFS

4.1.1.2.1. Nearest els are added to the begin of the query

4.1.2. Prim apgorithm - find the minimal spanning tree

4.1.2.1. Select any vertex

4.1.2.2. Each step add to the tree the nearest edge with min weight

4.1.3. Does represent a tree?

4.1.3.1. No cycles

4.1.3.2. Linked

4.1.3.3. Article

4.1.4. Longest path in graph

4.1.4.1. Article

4.1.5. Paths rom all to all

4.1.5.1. Warshall-Floyd algorithm

4.1.5.1.1. O(n^3)

4.1.5.1.2. Link

4.1.6. Min path

4.1.6.1. Dijkstra algorithm

4.1.7. A*

4.1.7.1. Improvement of Dijkstra algorithm

4.1.7.2. Uses heuristics

4.1.7.3. Result is sum of 2 functions: minDistance + h(x). h(x) is heuristical function

4.1.7.3.1. Named 'best-first'

4.2. Directed

4.2.1. weighted

4.2.1.1. Dijkstra algorithm - find min distance from one vertex to anothers

4.2.1.1.1. Link

4.2.1.2. Impl

4.3. Acyclic

4.3.1. Path between two vertices

4.3.1.1. Article

4.4. Usage

4.4.1. Representing complex structures

4.4.2. Modelling (networks, etc)

5. Stacks

5.1. With const time for push, pop, min

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

5.1.2. Link

5.2. Usage

5.2.1. Stacks in memory

5.2.2. In DFS

5.2.3. For saving contexts in processors

5.3. Features

5.3.1. Unknown length

5.3.2. No need to sort

5.3.3. O(1) of getting the head

6. In programming

6.1. Element cost in data structures

7. Priority Queue

7.1. Pop high-priority element: O(1)

7.2. Implementing using heap

8. Heap

8.1. Tree

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

8.3. Translation to array

8.3.1. Very simple. Rows, from left to right

8.4. Algorithms

8.4.1. Heapsort

8.5. Usage

8.5.1. For top k elements

8.5.1.1. O(nlogk)

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

9. Space structures

9.1. K-D tree

9.1.1. Hyperplanes

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

10. Linked list

10.1. Algorithms

10.1.1. Determine whether has cycles

10.1.1.1. Article

10.1.1.2. Idea

10.1.1.2.1. 2 pointers

10.1.1.2.2. 1 pointer has speed 1 el/iteration, another - 2 el/iteration

10.1.1.2.3. If they visit before the first pointer reaches the end - has cycles

10.1.1.2.4. O(n) worst case, no additional memory

10.1.2. Reverse linked list

10.1.2.1. Article

10.1.2.2. O(n)

10.2. Usage

10.2.1. For queries

10.2.1.1. Messaging

10.2.1.2. Scheduling

10.2.1.3. In BFS, DFS algorithms

10.2.2. Where number of items is unknown

11. Probabilistic

11.1. Bloom Filter