자료구조(data struture)란?
- 컴퓨터에서 여러 자료들을 조직적, 체계적으로 저장하는 방법을 말한다
- 보통 동일한 자료형을 여럿 저장하는 구조를 의미한다
- 자료구조에 따라 요소들 사이의 관계를 정의하는 규칙이 있다.
- 상황마다 효율적인 자료구조가 존재한다
- 데이터에 접근하는 빈도가 높은 경우
- 데이터에 접근하는 방법(예 : 삽입, 검색, 읽기, 지우기 등)
자료구조의 효율성
- 효율성은 주로 시간 복잡도(time complexity)를 말함
- 공간 복잡도(space complexity)를 포함하는 경우도 있음
- 따라서 주로 빅오(Big-O) 표기법을 사용
- 보통 효율성을 논할 때는 하드웨어 최적화를 고려 안 한 이론이 전부
- 대용량의 데이터를 사용할 때는 그래도 맞는 경우가 많다
- 적은 용량의 데이터는 그렇지 않을 수도 있다
C에서 자료구조를 배우는 이유
- 배열을 제외한 자료구조는 하드웨어 위에서 프로그래머가 만든 개념
- 다른 언어에서는 이런 자료구조들을 라이브러리로 제공하기에 프로그래머가 제대로 구현하며 배울 기회가 적다
- 자칫하면 추상적으로만 이해해서 ‘이건 마법처럼 도는구나’라고 믿고 넘어갈 수 있는 부분을 제대로 이해할 좋은 기회
자료구조의 시간 복잡도
|
검색 |
삽입 |
삭제 |
검색 |
삽입 |
삭제 |
| 배열 |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| 스택 |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| 큐 |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| 연결리스트 |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| 해시 테이블 |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |