Use cases
Stack
a last in, first out data structure
Pringles tube
navigate web page from one to another
Expression evaluation and syntax parsing.
Finding the correct path in a maze using backtracking.
Runtime memory management.
Recursion function.
Queue
a first in, first out (FIFO) data structure.
line up before the movie theatre
browsing history
Use queue when the developer wants an order.
Processed in First In First Out order.
If the developer wants to add or remove both ends, they can use the queue or a double-ended queue.
Linked list
a data structure which links each node to the next node.
Consider the thinking process when you placed your car keys somewhere and couldn’t remember. Our brain follows association and tries to link one memory with another and so on and we finally recall the lost memory.
When the developer needs constant time for insertion and deletion.
When the data dynamically grows/shrinks
Do not access random elements from the linked list.
Insert the element in any position of the list.
Double linked list
a data structure which each node contain data and two links.
handles browsing history more efficiently in O(1) time
Easier to delete the node from doubly linked list.
Can be iterated in reverse order without recursion implementation.
Insert or remove from double-linked lists faster.
Circular linked list
a linked list which the link field of the tail node link to the head node.
Develop the buffer memory.
Represent a deck of cards in a game.
Browser cache which allows to hit the BACK button.
Implement Most Recently Used (MRU) list.
Undo functionality in Photoshop or Word.
Binary tree
a tree data structure in which each node has at most two child nodes.
DOM
Find name in the phone book.
Sorted traversal of the tree.
Find the next closest element.
Find all elements less than or greater than a certain value.
Binary search tree
a tree data structure in which root node is less than or equal to left subtree and greater than or equal to right subtree.
Binary Search Trees are memory-efficient.
Use when the data need to be sorted.
Search can be done for a range of values.
Height balancing helps to reduce the running time.
Heap
a specialized tree-based abstract data type that satisfies the heap property.
Implement Priority Queue.
whenever the developer want quick access to the largest (or smallest) item.
Good for selection algorithms (finding the min or max).
Operations tend to be faster than for a binary tree.
Heap sort sorting methods being in-place and with no quadratic worst-case scenarios.
Graph algorithms are using heaps as internal traversal data structures, run time will be reduced by polynomial order.
Hash table
a data structure used to implement an associative array, a structure that can map keys to values.
Constant time operation.
Inserts are generally slow, reads are faster than trees.
Hashing is used so that searching a database can be done more efficiently.
Internet routers use hash tables to route the data from one computer to another.
Internet search engine uses hash function effectively.
Graph
an abstract data type that is meant to implement the graph and directed graph concepts from mathematics.
Networks have many uses in the practical side of graph theory.
Finding the shortest path between the cities.
Solve maze game.
Find the optimized route between the cities.
Red-black tree
a binary search tree with an extra bit of data per node, its color, which can be either red or black.
Java Tree Map and C++ map implemented using Red Block Tree.
Computational Geometry Data structures.
Scheduler applications.
Array
a data structure to store the same type of elements continuously.
Need access the elements using the index.
Know the size of the array before defining the memory.
Speed when iterating through all the elements in the sequence.
Array takes less memory compare than linked list.
Matrix
a data structure which store the data using rows and columns.
Matrix arithmetic in graphic processing algorithms.
Represent the graph.
Represent quadratic forms and linear algebra solution.
B-tree
a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
File systems.
Database operations.
Splay tree
a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.
When the developer wants access the recent data easily.
Allow duplicate items.
Simple implementation and take less memory.
When the application deals with a lot of data, use the splay tree.
AVL tree
AVL tree, the shape of the tree is constrained at all times such that the tree shape is balanced. The height of the tree never exceeds O(log n).
When the developer wants to control the tree height outside -1 to 1 range.
Fast looking element.
Trie
A Trie (digital tree and sometimes radix tree or prefix tree), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.
Fixed dictionary and want to look up quickly.
Require less storage for a large dictionary.
Matching sentences during string matching.
Predictable O(k) lookup time where k is the size of the key.
Lookup can take less than k time if it’s not there.
Supports ordered traversal.
No need for a hash function.
Deletion is straightforward.
Minimum spanning tree
A spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.
Describe financial markets.
Handwriting recognition of mathematical expressions.
Image registration and segmentation.
Constructing trees for broadcasting in computer networks.
Last updated