Data structures

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

1. Linked list

1.1. Algorithms

1.1.1. 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

1.1.2. Reverse linked list Article O(n)

1.2. Usage

1.2.1. For queries Messaging Scheduling In BFS, DFS algorithms

1.2.2. Where number of items is unknown

2. HashMap

2.1. Implementation

2.1.1. non-threadsafe Article hash function h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 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)

2.1.2. threadsafe Simple Lack of scalability bacause of locks ConcurrentHashMap Segments Further improvement with buckets coucurrencyLevel Article

2.2. Usage

2.2.1. Caches

2.2.2. Storing data with keys

2.2.3. One of most useful data structures

3. Trees

3.1. Trie tree

3.1.1. Link

3.1.2. Used for storing info about words

3.1.3. Easy search

3.1.4. Usage Dictionaries In suggest snippets

3.2. Binary

3.2.1. Unordered

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

3.3. In programming

3.3.1. Scaling Trees scale not good. HashMap is better

3.4. Algorithms

3.4.1. Generate all possible trees

3.5. Self-balancing

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

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

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

3.6. B-tree

3.6.1. Complexity O(logn)

3.6.2. Leaves and nodes contain elements

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

3.7. B+ tree

3.7.1. Nodes don't contain data, only leaves

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

3.7.3. Usage Block data systems File systems RDBMS (storing blobs?)

3.8. 2-4 Trees

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

3.9. Interval tree

3.9.1. Usage Queues Graphics (finding overlap zones)

3.10. General usage

3.10.1. Hierarchies

3.10.2. DOM, XML

3.11. Fenwick tree

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

4. Array/List

4.1. Algorithms

4.1.1. Sorting Bubble sort One of the slowest O(n^2) Complete loop from 0, 1...n-1 el Merge sort O(nlogn) Article Idea Insertion ort Worst case: O(n^2) Best case: O(n) Idea Bucket sort Article Quicksort Complexity Idea Table of complexity Radix sort O(mk) Sort last set of digits, then sort previous etc Heapsort in-memory Complexity Counting sort Linear time, linear space Used for data in small ranges

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

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

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

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

4.1.6. Find a number in a sorted array Idea Dichotomy method Article

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

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

4.2. Usage

4.2.1. For storing indexed data

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

5. Graphs

5.1. Algorithms

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

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

5.1.3. Does represent a tree? No cycles Linked Article

5.1.4. Longest path in graph Article

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

5.1.6. Min path Dijkstra algorithm

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

5.2. Directed

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

5.3. Acyclic

5.3.1. Path between two vertices Article

5.4. Usage

5.4.1. Representing complex structures

5.4.2. Modelling (networks, etc)

6. Stacks

6.1. With const time for push, pop, min

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

6.1.2. Link

6.2. Usage

6.2.1. Stacks in memory

6.2.2. In DFS

6.2.3. For saving contexts in processors

6.3. Features

6.3.1. Unknown length

6.3.2. No need to sort

6.3.3. O(1) of getting the head

7. In programming

7.1. Element cost in data structures

8. Priority Queue

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

8.2. Implementing using heap

9. Heap

9.1. Tree

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

9.3. Translation to array

9.3.1. Very simple. Rows, from left to right

9.4. Algorithms

9.4.1. Heapsort

9.5. Usage

9.5.1. For top k elements O(nlogk)

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

10. Space structures

10.1. K-D tree

10.1.1. Hyperplanes

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

11. Probabilistic

11.1. Bloom Filter