정적 배열 (Array)
정적 배열은 연관된 데이터를 메모리상에 연속적이며 순차적으로, 미리 할당된 크기만큼 저장하는 자료구조이다. 인덱스를 통해 접근이 용이하여 빠른 조회가 가능하지만, 크기를 미리 정해야 하므로 메모리 낭비나 추가적인 오버헤드가 발생할 수 있다.
특징:
- 고정된 저장 공간
- 순차적 데이터 저장
- 인덱스만 알고 있으면 조회가 빠름 (시간복잡도: O(1))
- 특정 조건을 충족하는 값을 찾는 탐색은 느림 (시간복잡도: O(n))
시간 복잡도:
- 탐색: O(1) (인덱스 접근 시), O(n) (순차적 탐색 시)
- 삽입/삭제: O(n) (처음 또는 중간), O(1) (끝)
- 동적 배열 (Dynamic Array)
- 동적 배열은 저장 공간이 가득 차면 자동적으로 크기를 늘려 데이터를 추가/저장할 수 있는 유동적인 자료구조이다. 정적 배열의 한계를 극복하고자 고안되었다.
특징:
- 데이터 접근과 할당이 빠름
- 메모리 낭비 가능성 있음
- 추가: 끝에 데이터를 추가 (append)
- 삽입: 아무 위치에나 데이터를 삽입 (insertion)
차이점:
- 정적 배열: 크기가 고정되어 변하지 않음, 낭비되는 공간이 없음
- 동적 배열: 크기가 변할 수 있음, 낭비되는 공간이 생길 수 있음
연결 리스트 (Linked List)
연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태의 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.
특징:
- 배열과 달리 메모리를 연속적으로 사용하지 않음
- 순차적으로 접근해야 하므로 불리할 수 있지만, 삽입/삭제가 용이함
트리 구조의 근간이 되는 자료구조
시간 복잡도:
- 탐색: O(n)
- 삽입/삭제: O(1) (연결 리스트의 처음), O(n) (연결 리스트의 중간, 탐색 시간 소요)
연결 리스트의 종류:
- 단일 연결 리스트 (Singly Linked List): 다음 노드의 주소만 저장
- 이중 연결 리스트 (Doubly Linked List): 이전 및 다음 노드의 주소 저장, 탐색 시간이 단축될 수 있음
- 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 노드를 가리킴
배열과 연결 리스트 비교:
- 장점:
배열: 인덱스를 통한 빠른 접근 가능
연결 리스트: 삽입/삭제 용이
- 단점:
배열: 삽입/삭제가 오래 걸림, 배열 중간에 데이터 삭제 시 공간 낭비 발생
연결 리스트: 임의 접근 불가, 처음부터 탐색 필요
- 용도:
배열: 빠른 접근이 요구되고 데이터의 삽입과 삭제가 적을 때
연결 리스트: 삽입과 삭제 연산이 잦고 검색 빈도가 적을 때
