📄 자료구조(Data Structure)란?
자료구조(資料構造, data structure)는 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문이다. 즉, 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미한다.
📢 [네이버 지식백과] 자료구조 [Data Structure] (학문명백과 : 공학, 김태달)
쉽게 말하면 자료구조는 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 집합을 말합니다.
자료구조는 두가지로 분류할 수 있습니다.
- 선형 구조
- 비선형 구조
📏 선형 구조
▶ 배열(array)
메모리 상에 데이터를 연속으로 배치한 데이터 구조
특징
- 같은 타입의 데이터를 나열한 선형 자료구조이다.
- 연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
- 배열은 선언할 때 크기를 정하면 고정이 된다.
장점
- 인덱스로 인한 빠른 접근이 가능하다.
- 참조를 위한 추가적인 메모리가 필요하지 않는다.
단점
- 크기를 변경할 수 없다.
- 사용하지 않는 공간에 대한 메모리가 낭비된다.
▶ 스택(Stack)
늦게 들어온 데이터가 먼저 나가는 LIFO(Last In First Out) 형태의 데이터 구조
특징
- 한쪽 끝으로만 자료의 삽입, 삭제 작업
- LIFO(Last-In, Fisrt-Out)
장점
- 구조가 단순한 편이이서 구현이 쉽다.
- 데이터 저장, 읽기 속도가 빠르다.
단점
- 가장 위에 있는 데이터만 접근이 가능하다.
- 데이터 탐색을 위해서는 위에서 부터 하나씩 접근해야한다.
▶ 큐(Queue)
먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 형태의 데이터 구조
특징
- 한쪽에서는 삽입 작업, 다른 한쪽에서는 삭제 작업
- FIFO(First In First Out)
장점
- 순차적 처리가 필요할 때 유용하다.
- 데이터 삽입, 삭제 속도가 빠르다.
단점
- 배열로 구현하면 삽입, 삭제에 한계가 존재한다.
- 데이터 탐색을 위해서는 위에서 부터 하나씩 접근해야한다.
▶ 데크(Deque)
앞, 뒤 양쪽 방향에서 추가하거나 제거할 수 있는 데이터 구조
특징
- 앞, 뒤 어디서든 삽입, 삭제가 가능
- 데이터의 크기가 가변적일때 사용
장점
- 인덱스로 인한 빠른 접근이 가능하다.
- 데이터의 삽입, 삭제 속도가 빠르다.
단점
- 구현하기 쉽지 않다.
- 데이터 중간에 삽입, 삭제가 불가능하다.
▶ 링크드리스트(Linked List)
데이터 마다 다음 데이터를 가르키는 포인터를 연결하여 데이터를 연결한 구조
특징
- 각 원소가 데이터와 그 다음 데이터의 주소값으로 구성
- 데이터가 가변적임
장점
- 데이터의 크기가 가변적이다.
- 데이터의 삽입, 삭제 속도가 빠르다.
단점
- 주소값을 저장해야하기 때문에 추가적인 메모리 공간이 필요하다.
- 데이터 탐색을 위해서는 첫번째부터 하나씩 접근해야한다.
📊 비선형 구조
▶ 트리(Tree)
노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조
원을 ‘노드(node)’라 하고, 노드와 노드를 연결하는 선을 ‘링크(link) or 엣지(edge)’라 한다. 특히 가장 위에 위치한 노드를 ‘루트 노드(root node)’라 하는데, 이는 한 개만 있어야 한다.
📢 [네이버 지식백과] 트리 (컴퓨터 개론, 2013. 3. 10., 김종훈, 김종진)
트리에서 임의의 노드를 선택하면 이 노드와 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 ‘서브 트리(subtree)’라 한다. 임의의 노드의 조상과 자손을 지칭할 수 있는데, 임의의 노드 바로 위에 있는 노드를 ‘부모 노드(parent node)’라 하고, 바로 아래에 있는 노드를 ‘자식 노드(children node)’라 한다.
▶ 그래프(Graph)
그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
📢 [위키백과] 그래프(자료구조)
단순히 노드(node)와 그 노드를 연결한 간선을 하나로 모아놓은 자료 구조.
연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다.
Reference
