자료구조 (Data Structure)
자주 사용되는 자료구조의 종류
- 리스트
- 연결 리스트
- 배열
- 스택
- 큐
- 덱
- 트리와 힙
- 그래프
스택, 큐, 덱, 트리는 리스트로도 구현할 수 있고, 연결 리스트로도 구현할 수 있다. 큐의 경우에는 리스트, 연결 리스트 외에 힙을 이용해서 구현하기도 한다.
자료구조의 분류
단순 구조
T/F, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형을 사용하는 경우. 기본 자료형을 여러 개 모아서 사용자가 필요한 자료형을 선언하는 경우도 여기에 속한다.
선형 구조
데이터들이 일렬로 쭉 저장되어있는 형태를 가진다. 일렬로 저장하는 방식은 리스트와 각 데이터가 다음 데이터의 위치를 가지는 연결 리스트 두 가지 방식이 있다. 일렬로 쭉 저장되어 있는 데이터를 사용하는 방법은 리스트와 연결 리스트 외에 사용 방법에 따라 스택, 큐, 데크가 추가된다.
비선형구조
데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조이다. 구조의 종류는 트리와 그래프가 있다. 트리와 그래프도 물리적으로 보면 연결 리스트를 이용하여 구현하지만 사용 방법이 다르므로 별도로 분리하여 생각한다.
파일구조
다양한 자료구조의 데이터를 파일에 저장하는 방식이다.
자료구조의 구현
자료구조의 종류는 많지만, 실제 자료구조를 구현하는 기술은 리스트와 연결 리스트 두 가지가 있다. 리스트와 연결 리스트를 이용해서 다양한 자료구조가 만들어진다.
References
- 그림으로 정리한 알고리즘과 자료구조