Data Structures and Algorithms

Data Structures #

Literally, a structure that holds data.
In computer science, it refers to the organization, management, and storage of data that enables access and modification.
It signifies a collection of data values, the relationships between data, and the functions or operations that can be applied to the data.

ex ) For example, imagine a bookshelf. Deciding whether to arrange books alphabetically or stack them on a desk when putting them on the shelf—that is, determining the form in which this data is stored—is what a data structure is.

Classification of Data Structures #

Depending on the characteristics and size of the data, primary usage, types of operations performed, and memory space required for implementation, one can choose among various types of data structures. Data structure types include simple structures classified by data type, linear structures where data relationships are one-to-one, non-linear structures with one-to-many or many-to-many relationships, and finally, file structures.

By Implementation

Array: The most common structure. Data of the same type is stored contiguously in memory.
Tuple: A structure that handles two or more data types as a single bundle.
Linked List: Uses nodes as its unit. A node consists of data and a reference value pointing to the next node. If a node points to nothing as its next node, it's the end of the list.
Circular Linked List: Each node points to the next node, and the last node points to the first node.
Doubly Linked List: Each node consists of reference values pointing to the previous and next nodes. The first node has no previous node, and the last node has no next node.
Circular Doubly Linked List: A doubly linked list where the first node's previous node points to the last node, and the last node's next node points to the first node.
Hash Table: Objects are indexed according to their hash values.

By Form

Linear Structures #

Stack: In a stack data structure, what is stored first comes out last when retrieved. Conversely, what is stored most recently comes out first. If you want to reverse the order of data, you can push it onto a stack and then pop it off.
Queue: Contrary to a stack, in a queue data structure, what is stored first comes out first. Conversely, what is stored most recently comes out last.
Circular Queue: A queue that allows reading and writing within a limited length without additional operations.
Deque: A generalized linear structure that allows insertion and removal from both ends.

Non-linear Structures #

Graph: Consists of vertices and edges connecting the vertices.
Directed Graph, Undirected Graph: A classification of graphs based on whether edges have directionality. An undirected graph refers to a connected graph without cycles. In a directed graph, edge directions are usually implemented to point to parents.
Tree: A structure consisting of a root and vertices that have the root or another vertex as their single parent. Parent-child relationships are represented by edges.
Binary Tree: A tree where each node has at most two children.
Heap: A type of binary tree, which can be said to be a binary tree with certain properties.

Algorithms #

A method for solving a problem.
More specifically, in fields like mathematics and computer science, it refers to a formalized expression of a set of defined procedures or methods for solving a problem, meaning a step-by-step procedure for performing a calculation. That is, it signifies the sequence of computational procedures or processing steps required to solve a problem.
It can also mean a set of program instructions for performing basic operations within a data structure.

To use the bookshelf example again, if I need to find a book, deciding whether to search from the left, from the right, or randomly is an algorithm.

Classification of Algorithms #

Implementation: Recursive algorithms, deductive algorithms, deterministic algorithms, approximation algorithms, quantum algorithms, etc.
Design: Brute-force algorithms, divide and conquer algorithms, graph traversal, branch and bound, probabilistic algorithms, reduction, backtracking, etc.
Optimization Problems: Linear programming, dynamic programming, greedy algorithms, heuristic functions, etc.
Theoretical Fields: Search algorithms, sorting algorithms, numerical algorithms, graph algorithms, string algorithms, cryptographic algorithms, machine learning, data compression, etc.

Difference Between Data Structures and Algorithms #

Data Structure: A method for how data will be stored and managed.

Therefore, it requires consideration of how to store data efficiently.

Algorithm: A method needed when finding, transforming, or modifying stored data.

Therefore, it requires consideration of the procedures for solving a problem.

Definition of a Program #

A collection of instructions that perform specific tasks when executed on a computer.
From the perspective of data structures and algorithms, a program can be expressed as Program = Data Structure + Algorithm.