자료구조

사전적 의미: 자료의 집합; 자료들이 논리적으로 정의된 규칙에 의해 나열되어 있는 것

 

자료구조를 이용해 데이터를 잘 정리정돈 해 놓는다면 데이터를 효율적으로 저장하고 관리할 수 있습니다.

그리고 코드의 실행시간을 단축하거나 메모리 용량을 절약하기 위해 자료구조를 이용하게 됩니다.

 

이점

 - 코드의 처리 시간을 단축

 - 데이터 크기를 줄이고 메모리 용량을 절약

 - 데이터 활용 빈도가 높아짐

 - 데이터를 수정/관리하기 쉬워짐

 - 프로그램이 쉽고 간결

 

자료구조는 간단하게 말해서 '자료를 잘 정리해 놓을 수 있는 메뉴얼'이라고 생각하면 됩니다.

 

자료구조의 종류

컴퓨터가 다룰 수 있는 기본 자료구조는 딱 세 가지 밖에 없습니다. (숫자, 문자, True/False)

하지만 컴퓨터는 더 다양하고 세밀한 연산을 수행해야 하며 기본 자료형 세 가지를 조합해서 수행하므로 더 다양한 자료구조가 필요합니다.

 

자료구조는 크게 '선형 자료구조'와 '비선형 자료구조'로 나눌 수 있습니다.

• 선형 자료구조 : 데이터가 일렬로 나열되어 있는 것
• 비선형 자료구조 : 데이터가 일렬로 나열되어 있지 않고 특정한 형태를 띄고 있는 것

자료 구조의 종류

 

1. 선형 자료구조 : 한 원소 뒤에 하나의 원소만이 존재하는 자료구조

• 자료들이 직선 형태로 나열되어 있음
• 원소 간의 순서가 고려됨
• 데이터를 저장하고 꺼내는 것에 초점이 맞춰져 있음

1-1. 선형 리스트(Linear List) 

• 프로그래밍에서 배열(Array) 타입으로 정의하게 됨
• 배열: 데이터가 많아지고 속성이 같은 데이터를 그룹으로 관리할 필요가 있을 때 씀
• 장점: 접근이 빠르고 간단하다.
• 단점: 배열 요소의 순서를 바꾸고 데이터를 삭제한 후 빈 배열을 처리하는 것이 어렵다.

1-2. 연결 리스트(Linked List)

• 데이터 값과 next node의 address값을 동시에 갖으며 하나의 데이터로 관리함
• 장점: 배열은 fixed-size의 특성상 배열의 크기가 가변적이지 않아서 크기가 모자라면 메모리를 더 할당하고 배열의 데이터를 복사해야 해서 비효율적입니다. 하지만 연결 리스트의 경우 다음 데이터의 주소 값을 추가만 하면 되니 크기를 마음대로 늘릴 수 있습니다.
• 단점: 배열처럼 접근 속도가 빠르지 않기 때문에 조회보다 수정, 삭제가 잦은 데이터의 경우 연결 리스트를 사용합니다.

1-3. 스택(Stack)

• 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조를 갖음
• 활용 예시: 웹페이지의 뒤로가기 버튼

1-4. 큐(Queue)

• 처음 들어간 데이터가 가장 먼저 나가는 FIFO(First In First Out)
• 활용 예시: 은행에서 대기표를 가장 먼저 뽑은 사람이 가장 먼저 은행 업무를 보고 나갈 수 있는 것

---

2. 비선형 자료구조 : 한 원소 뒤에 여러 개의 원소가 존재할 수 있는 자료구조

• 인접한 전/후 원소 간에 다대다 관계가 성립됨
• 선형 자료구조에 비해 데이터들의 관계를 표현하기에 적합
• 데이터를 표현하는데 초점이 맞춰져 있음

2-1. 트리(Tree) 

• 데이터를 노드(정점)로 표현하고 연결된 관계를 에지(간선)로 표현한 비선형 계층적 자료구조
• 대표적 예시: 컴퓨터의 디렉토리 구조

2-2. 그래프(Graph)

• 노드(정점), 에지(간선)으로 이루어진 자료구조
• 트리는 그래프의 한 종류
• 트리와 달리 그래프는 노드마다 간선이 있을 수도 있고 없을 수도 있음
• 부모 노드와 자식 노드라는 개념이 존재하지 않음 (비계층적임)
• 모델이나 객체, 이에 대한 관계를 유연한 방식으로 표현하는데 사용 됨