배열
- 배열은 입력된 데이터들이 메모리 공간에서 연속된 메모리 주소를 할당받는 자료구조이다.
- 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에, index를 통한 접근이 용이하다.
- 배열의 크기는 처음 생성할 때 정하며, 이후에는 변경할 수 없다. 또한 해당 배열 크기 이상의 데이터를 저장할 수 없다.
- 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당이다.
- Stack 영역에 메모리 할당이 된다.
시간 복잡도
- 탐색:
- 인덱스를 통한 탐색: O(1)
- 순차 탐색: O(n)
- 삽입/삭제:
- 배열의 처음 또는 중간에 삽입 및 삭제: O(n)
- 배열의 끝에 삽입 및 삭제: O(1)
연결 리스트
- 연결 리스트는 여러개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
- 배열과는 다르게 메모리를 연속적으로 사용하지 않는다. -> 처음부터 순차적으로 탐색해야 한다.
- 크기의 제한이 없다.
- 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
- Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을때 그 유용성이 드러난다.
- 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
- Heap 영역에 메모리 할당이 된다.
시간 복잡도
- 탐색: O(n)
- 삽입/삭제:
- 연결 리스트의 처음에 삽입/삭제: O(1)
- 연결 리스트의 중간에 삽입/삭제: O(n)
- 연결 리스트의 끝에 삽입/삭제:
- 끝을 가리키는 별도의 포인터를 갖는 경우: O(1)
- 끝을 가리키는 별도의 포인터를 갖지 않는 경우: O(n)
이중 연결 리스트
- 이중 연결 리스트는 연결 리스트와 다르게 전/후로 탐색이 가능한 구조이다.
- 즉, 단순 연결 리스트의 노드는 데이터와 다음 노드의 주소를 저장한다면, 이중 연결 리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.
- 장점: 단순 연결 리스트에서는 최악의 경우 n번의 탐색을 해야하지만, 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝자면 tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.
원형 연결 리스트
- 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 -> 마지막 노드의 링크필드가 NULL이 아닌, 첫번째 노드의 주소이다.
- 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적이다. -> 해드 포인터에서 시작하여 모든 노드를 거쳐 마지막에 삽입하는 것이 아니라, 헤드 포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음과 끝에 노드를 삽입할 수 있다.
배열 vs 연결 리스트
| 배열 | 연결리스트 |
|---|---|
| 정적 자료구조 | 동적 자료구조 |
| 미리 크기를 정해 놓음 | 크기를 정할 필요가 없음 |
| 연속된 메모리 주소를 할당 받음 | 연속된 메모리 주소를 할당 받지 않음 |
| 접근, 탐색 용이 | 추가, 삭제 용이 |
| index 존재 | node 존재 |
장점
- 배열
- 인덱스를 통한 빠른 접근 가능하다.
- 구현이 간단하다.
- 연결 리스트
- 삽입/삭제 용이하다.
단점
- 배열
- 삽입/삭제가 오래 걸린다.
- 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.
- 동적으로 크기를 늘리거나 줄이는 것이 힘들다.
- 연결 리스트
- 임의 접근이 불가능하여 처음부터 탐색을 진행해야 함
용도
- 배열: 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 -> 데이터 접근이 주 업무일 경우 (달력 날짜 접근)
- 연결 리스트: 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 -> 데이터 수정이 주 업무일 경우 (음악 플레이리스트. 이전 곡과 다음 곡 연결)
예상 질문
Q. 배열, 연결 리스트의 특징과 장단점은?
A. 배열은 정적 자료구조이고 구현이 간단하며 구현이 간단하다. 하지만 삽입/삭제가 오래걸리고 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다. 연결 리스트는 동적 자료구조이고 삽입/삭제가 용이하다. 하지만 임의 접근이 불가능하여 처음부터 탐색을 진행해야 한다.
Q. 배열 또는 연결 리스트를 사용하면 좋을 데이터의 예시와 이유
A. 배열은 인덱스를 통한 임의 접근이 가능하기 때문에 데이터 접근이 주 업무일 경우, 연결 리스트는 동적 자료구조로 삽입 삭제가 용이하기 때문에 데이터 수정이 주 업무일 경우 적합하다.
Q. 이진 트리를 구현할 때 배열과 연결 리스트 중 적합한 것과 이유
A. 연결 리스트. 배열은 연속적인 공간을 할당하기 때문에, 이진 트리를 구현할 경우 메모리 낭비가 심해질 수 있다.
참고
https://velog.io/@xxhaileypark/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Array-LinkedList
https://blacklobster.tistory.com/8
