Choosing the appropriate Data Structure

AlgoDS/DataStructure 2019. 9. 4. 21:14

1. Overview

Data structures are the way to store and retrieve data like accessing data using an index in an array or a named key to store and retrieve information from a dictionary. Choosing the appropriate data structure enhancing inputting, processing, maintaining, retrieving information. For performance, the developer should choose the right data structure.

2. Description

Data Structure	Description	When to use
Array	To store 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
Linked List	Links each node to the next node	Constant time for insertion and deletion When the data dynamically grows Do not access random elements Insert the element in any position of the list
Stack	LIFO	Expression evaluation and syntax parsing Finding the correct path in a maze using backtracking Runtime memory management Recursion function
Queue	FIFO	Needs an order Processed in FIFO order If wanting to add or remove both ends, Using queue or double-ended queue
Doubly Linked List	Each node contains data and two links. One link point to the previous node and another link point to next node	Easier to delete the node from a doubly linked list Can be iterated in reverse order without recursion implementation Insert or remove from double-linked lists faster
Circular Linked List	Linked list 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 allows hitting the BACK button Implement MRU list Undo functionality in Photoshop or Word
Hashing	Implement an associative array, a structure 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 An Internet search engine uses hash function effetively
Binary Tree	Each node has at most two child nodes	Find a 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
B-Tree	Keeps data sorted and allows searched, sequential access, insertions, and deletions in logarithmic time.	File systems Database operations
Heap	A specialized tree-based abstract data type satisfies the heap property. Complete (mostly, Binary) Tree. Max heap and Min Heap	Implement Priority Queue Whenever wanting quick access to the largest(or smallest) element Good for selection algorithm(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, the runtime will be reduced by polynomial order
Graph	An abstract data type meant to implement the graph and directed graph concepts from mathematics	Networks have many uses in the practical side of the graph theory Finding the shortest path between the cities Solve maze game Find the optimized route between the cities
Binary Search Tree	The 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
Matrix	Store the data using rows and columns	Matrix arithmetic in graphic processing algorithms Represent the graph Represent quadratic forms and linear algebra solution
Red-Black Tree	A binary search tree with an extra bit of a data per node, it's 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
Splay Tree	A self-adjusting binary search tree with the additional property recently accessed elements are quick to access again	Needing access to recent data easily Allow duplicate elements Simple implementation and take less memory When the application deals with a lot of data
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)	Needing to control the tree height outside -1 to 1 range Fast looking element
Trie	Digital tree and sometimes radix tree or prefix tree. An ordered tree 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 a 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 a spanning tree with weight less than or equal to the weight of every other spanning tree	Describe financial market Handwriting recognition of mathematical expressions Image registration and segmentation Constructing trees for broadcasting in computer networks