📔 학습한 내용을 정리하기 위해 작성하는 게시글입니다.
자료구조(data structure)란?
대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조(자료의 집합)을 의미한다.
자료구조의 선택 기준
- 자료의 처리 시간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
자료구조의 특징
- 효율성 - 적절한 자료구조를 선택하여 효율적인 데이터의 관리 및 사용
- 추상화 - 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것
- 재사용성 - 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계
자료구조의 분류
1. 단순 구조
1) 정수
2) 실수
3) 문자
4) 문자열
2. 선형 자료구조(linaer)
: 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬
1) 배열(Array)
-
정의 : 자료형이 같은 데이터를 하나의 변수 이름으로 모아 순차적으로 저장 및 정렬하는 자료구조
-
장점 : 각 요소에 인덱스가 부여되므로 검색이 용이함
-
단점 : 데이터의 추가,삭제 시 배열 내 다른 데이터의 순서를 다시 매겨야 하므로 많은 시간이 걸림, 리스트의 길이가 고정적
2) 연결리스트(Linked List)
- 정의 : '노드'라는 저장구조를 이용해서 선형 리스트를 표현하는 방법, FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조
노드(node) - 데이터의 저장 단위, 연결리스트의 각 원소, 데이터 요소와 다음 요소를 가리키는 포인터(주소값)의 쌍
-
장점 : 리스트의 길이가 가변적(배열의 단점 커버), 데이터의 추가,삭제를 배열보다 간단하게 할 수 있음
-
단점 : 저장 공간 효율이 낮음(포인터를 위한 저장 공간 필요),
데이터 탐색 속도가 느림(포인터를 이용해 연결노드를 찾는 시간 필요),
중간에 위치한 데이터 삭제 시, 삭제된 데이터의 앞뒤 데이터의 연결을 재구성하는 부가적인 작업이 필요 -
배열과의 차이점 : 인덱스가 없음(원소들을 엮어서 관리함)
3) 스택(Stack)
- 정의 : 추가된 요소를 쌓는 방식(LIFO)으로 데이터를 저장 및 정렬하는 자료구조
스택에 요소를 추가하는 동작을 푸시(push), 마지막으로 추가된 요소를 꺼내는 동작을(pop)이라고 함
LIFO(last in first out) : 스택에 마지막으로 추가된 요소를 먼저 삭제하는 스택 구조 → 후입선출 데이터 구조(세로로 된 바구니 모양)
-
장점 : 데이터의 저장 및 읽기 속도가 빠름, 구조가 단순하여 구현이 쉬움
-
단점 : 저장될 데이터의 최대개수를 미리 정해야 함(저장 공간 확보 필요) → 저장 공간의 낭비가 발생할 수 있음
4) 큐(Queue)
- 정의 : 한쪽 끝에서는 데이터의 삽입만 수행되고 다른 한쪽 끝에서는 삭제만 수행되는(FIFO) 자료구조
큐에 요소를 추가하는 것을 인큐(enqueue), 큐에서 요소를 삭제하는 것을 데큐(dequeue)라고 함
FIFO(first in first out) : 큐에 가장 먼저 추가된 요소가 우선적으로 삭제되는 선입선출 데이터 구조(줄 서있는 모양)
-
장점 : FIFO방식으로 인해 데이터 삭제 시 재정렬이 필요 없음
-
운영체제(OS)에서 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨
2. 비선형 자료구조(non-linear)
1) 트리(Tree)
-
정의 : 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로, 노드들이 부모와 자식 관계로 이루어진 자료구조(노드와 브랜치를 이용하여 구성된 계층 구조)
-
계층이 있는 데이터를 표현하기에 적합
-
트리를 기반한 이진트리를 이용하여 탐색 알고리즘 구현에 자주 사용
2) 그래프(Graph)
-
정의 :정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
-
장점 : 새로운 데이터의 추가, 삭제가 용이하고 구조를 응용하기에 적합
-
단점 : 데이터간 충돌이 일어날 수 있음
3. 파일 구조
1) 순차 파일 구조
2) 색인 파일 구조
3) 직접 파일 구조
🔔 Reference
<이재환의 자바 프로그래밍 입문>
<코드 없는 알고리즘과 데이터 구조>
https://andrew0409.tistory.com/148
https://devraphy.tistory.com/88
https://pyoungt.tistory.com/166
https://hudi.blog/ds-linked-list/
https://lucaseo.github.io/posts/2021-02-01-python-datastructure-linked-list/
https://mangkyu.tistory.com/89
https://zrr.kr/T8qK
https://zrr.kr/MqLy
