자료구조(data structure)란?
자료구조란 컴퓨터에서 여러 데이터를 조직적, 체계적으로 저장하는 방법이다.
보통 동일한 자료형을 여럿 저장하는 구조를 의미한다. 자료구조에 따라 요소들 사이의 관계를 정하는 규칙이 따로 존재한다. 그리고 데이터에 접근하는 빈도나 데이터에 접근하는 방법 (예: 검색, 삽입, 삭제 등)에 따라 보다 효율적인 자료구조가 존재한다.
자료구조의 효율성
효율성은 주로 시간 복잡도(time complexity)를 의미한다.
공간 복잡도는 메모리의 용량이 늘어남에 따라 어느 정도 해소가 되었다.
때문에 시간 복잡도를 나타내는 빅오(big-O)표기법을 많이 사용한다. 하지만, 여기서 논하는 효율성은 하드웨어의 최적화를 고려 안 한 이론이 대부분이다. 그래서 적은 용량의 데이터로는 정반대의 결과가 나올 수 있음에 유의하자.
대용량 데이터를 사용할 때는 그래도 어느정도 맞는 이론이다.
기초 자료구조
자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉜다.
아주 간략히 설명하자면 선형 자료구조는 앞뒤 데이터의 관계가 1:1 이고, 비선형 자료구조는 1:N 또는 N:M 관계이다.
이번 시리즈에서는 우선 가장 기초가 되는 선형 자료구조를 먼저 다루고, 비선형 자료구조를 다루어보려고 한다.
- 선형 자료구조
- 배열
- 스택 / 큐
- 연결리스트
- 해시 테이블
자료구조의 시간복잡도
참고로 여기서 공간 복잡도는 모두 O(N)이다.
References
Slow but steady wins the race🏃♂️