[Data structure] 자료 구조

What is data structure?

• A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.
• 컴퓨터가 데이터를 효율적으로 저장하고 처리하기 위해 사용되는 저장공간 혹은 방법.
• 효율은 메모리 , 처리 속도 관점.

Importance

• 효율적인 데이터 처리
• 메모리 관리
• 코드 재사용
• 추상화
• 알고리즘 설계

Classification

• non-primitive data structres
• Arrays
• Linked lists
• Stacks
• Queues
• Trees
• Graphs
• Hash tables (Neural Net 으로 만들면 ?)
• Heaps
• Matrix
• Tries
• Sets
• Maps

Special Feature

Arrays

• An array is a collection of items of same data type stored at contiguous memory locations.
• 배열의 첫 요소의 메모리 위치에 오프셋을 추가하여 각 요소에 쉽게 접근 가능.
• In C language, the array has a fixed size meaning once the size if given to it, it caanot be changed.

• 수학적 계산
• 이미지 처리
• DB 레코드 관리

Linked List

• A linked list is a linear data structure where each node contains a value and a reference to the next node.
• Random memory

• 메모리 관리
• 방문한 페이지 , 실행 취소 , 이미지 컨테이너 등 연결되어 있는 구조에 사용
• 소셜 미디어 피드

Stack

• Stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO(Last in first out).
• Entering and retrieving data is possible from only one end.
• stack overflow , stack underflow

• 재귀
• 메모리 관리
• 함수 호출 처리
• 실행 취소 및 다시 실행 작업
• 이전에 방문한 브라우저

Queue

• Stack is a linear data structure that follows a particular order in which the operations are performed. The order is FIFO(First in first out).
• The data item stored first will be accessed first.

• 에스컬레이터
• 줄 서기
• 작업 예약
• 프로세스간 통신

Tree

• A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like structure.
• B-Tree and B+ Tree are used to implement indexing in databases.
• Head is a tree data structure that is implemented using arrays and used to implement priority queues.
• Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic expressions in Compiler design.
• K-D Tree is a space partitioning tree used to organize points in K-dimensional space.
• Spanning trees are used in routers in computer networks.

• 게임 개발
• DB 인덱싱
• 의사 결정 트리
• Domain Name Server
• 모든 소셜 네트워킹 사이트

Graph

• A graph is a non-linear data structure that consists of vertices (or nodes) and edges.
• A graph is a collection of vertices (nodes) and edges that represent relationships between the vertices.
• Faster data retrieval and manipulation
• Increased computational and memory overhead

• Google map (cities are located as vertices and paths connecting those vertices are located as edges of the graph)
• Social network (every person on the network is a node, and all of their friendships on the network are the edges of the graph)
• network modeling
• Social media analysis
• Network monitoring
• Financial trading
• IoT management
• Autonomous vehicles
• Disease surveillance

Heap

• A Heap is a special Tree-based data structure in whice the tree is complete binary tree.
• Max heap, Min Heap

• Priority queue
• Heapsort algorithm
• Memory management 
• Graph algorithm
• Job scheduling

 

 

Reference

geeksforgeeks.org