💡 배열 VS 연결리스트 기본 차이
| 구분 | 배열(Array) | 연결리스트(Linked List) |
|---|---|---|
| 메모리 구조 | 연속된 메모리 공간에 저장 | 각 노드가 데이터 + 다음 노드의 포인터를 가짐 |
| 랜덤 접근(Random Access) | 가능 (O(1)) → 인덱스로 바로 접근 | 불가능 (O(n)) → 처음부터 순차 탐색 |
| 삽입/삭제 | 중간에 삽입/삭제 시 뒤 원소들을 이동해야 함 → O(n) | 포인터 변경만 하면 됨 (노드만 수정) → O(1) (단, 위치 탐색이 O(n)) |
| 캐시 친화성 | 메모리가 연속적이라 CPU 캐시 효율 높음 | 포인터 기반이라 캐시 효율 낮음 |
| 메모리 오버헤드 | 데이터만 저장 → 효율적 | 포인터(주소) 추가 저장 → 메모리 낭비 가능 |
- 랜덤 접근 : 임의의 인덱스(위치)에 바로 접근 할 수 있는 능력
💡접근/삽입/삭제 속도 및 성능 비교
✅1. 접근 속도(읽기)
🔸배열
- arr[5]처럼 인덱스로 바로 접근 가능 → 주소 계산으로 O(1)
🔸연결 리스트
- 5번째 원소를 찾으려면 처음(head)부터 차례대로 따라가야함 → O(n)
✅2. 삽입/삭제
🔸배열
- 맨 뒤에 추가 : O(1) (단, 할당된 용량 초과시 재할당 필요)
- 중간 삽입/삭제 : O(n) 원소들을 한칸씩 밀거나 당겨야함
🔸연결 리스트
- 맨 앞 삽입/삭제 : O(1)
- 중간 삽입/삭제 : O(1) (포인터만 수정하면 된다!)
하지만 위치 탐색 O(n)이 필요하므로 결국 평균은 O(n)
➡️ 읽기 위주라면 배열, 삽입/삭제가 잦으면 연결리스트가 유리
💡실제 백엔드 환경에서의 사용 예시
🔸배열
- 조회가 많은 경우(DB 조회 결과 리스트, 캐시된 사용자 목록)
- 고정 길이나 사이즈 예측이 가능한 경우
- CPU 캐시 친화적이라 성능이 중요한 경우
🔸연결 리스트
- 삽입/삭제가 빈번한 큐, 스택 구현 시
- 큰 데이터에서 중간 원소가 자주 제거/삽입 되는 경우
💡캐시 구현 시 차이
🔸배열 기반 캐시
- 인덱스로 바로 접근 가능 → 조회 성능 뛰어남
- 중간 원소 제거 시 비효율적 (O(n))
- 예시 : LRU 캐시를 배열만으로 구현하면 비효율적
🔸연결 리스트 기반 캐시
- 삽입/삭제 용이(노드 포인터만 조정하면 되므로)
- 자주 쓰이는 구조 : HashMap + Double Linked List
- HashMap으로 O(1) 조회
- LinkedList로 O(1) 삽입/삭제
- 실제 LRUCache 구현 방식이 이 패턴이다.
- LRU 캐시 : 가장 오래 사용되지 않은 데이터를 제거하는 캐시 알고리즘
1. 배열과 연결리스트의 가장 큰 차이는?
➡️메모리 연속성과 랜덤 접근 가능 여부
배열은 연속된 공간이라 인덱스로 접근 가능하지만, 연결리스트는 포인터로 연결되어 있어 순차 탐색 해야한다.
2. 배열은 왜 O(1) 접근이 가능하고, 연결리스트는 O(n)인가요?
배열은 시작주소와 크기가 결정되어 있어 바로 계산 가능하지만, 연결 리스트는 포인터를 따라가야하므로 선형 탐색이 필요합니다.
3. 삽입/삭제 성능 비교는?
배열은 중간에서 삽입/삭제가 일어나게 되면 원소들의 이동이 필요하므로 O(n)이고, 연결리스트는 포인터만 수정하면 되므로 O(1)입니다. 단, 탐색은 선형탐색이므로 O(n)입니다.
4. 실제 백엔드에서 배열과 연결리스트는 언제 쓰나요?
조회가 많은 경우엔 배열을, 삽입 삭제가 많으면 연결리스트를 사용합니다.
5. 배열과 연결리스트로 캐시 구현시 어떤 차이가 있나요?
가장 오래 사용되지 않은 데이터를 제거하는 캐시 알고리즘인 LRU 캐시는 HashMap + LinkedList 조합으로 O(1) 조회/삽입/삭제 보장합니다. 하지만 단순 배열로 구현하게된다면 중간 삭제 때문에 성능 저하.
6. 메모리 관리 관점에서 배열과 연결 리스트의 차이는 무엇인가요?
배열은 연속된 메모리 공간에 저장 -> 인덱스로 바로 접근 가능
연결리스트는 분산된 공간에 노드 저장 -> 메모리 접근이 비연속적이므로 캐시 효율 떨어짐
7. 배열과 연결리스트의 메모리 효율성은 어떻게 다른가요?
배열은 원소만 저장하므로 메모리 효율이 높지만, 연결리스트는 각 노드마다 포인터를 함께 저장해야하므로 그만큼 메모리 오버 헤드 발생
8. 동적 크기 조정이 필요한 상황에서는 어떤 자료구조를 선택하나요?
배열은 크기가 고정되어 있어 크기 조정이 필요하면 크기 재할당이 필요하지만, 연결리스트는 노드를 추가만 하면 되므로 연결 리스트가 더 적합
9. 캐시 적중률(Cache locality)측면에서는 어떤 자료구조가 유리?
배열은 연속된 메모리 구조이므로 CPU 캐시에 잘 적중해서 순차 탐색 시 속도가 빠름. 연결 리스트는 메모리가 흩어져 있어 캐시 효율이 떨어지고, 실제 실행 시간이 느린 경우가 많음
10. 더블 링크드 리스트와 싱글 링크드 리스트의 차이는?
싱글 링크드 리스트는 한쪽 방향으로만 연결됨.
더블 링크드 리스트는 양쪽 포인터 모두 가지고 있어 양방향 탐색이 가능하지만, 포인터를 하나 더 저장하므로 메모리 사용량 증가
11. 배열 기반 스택/큐와 연결리스트 기반 스택/큐의 차이는?
배열 기반 : 인덱스를 활용하여 구현이 단순, 메모리 사용 효율적이지만 크기 제한
연결리스트 기반 : 크게 제한 없고 삽입/삭제가 빠르지만 포인터로 인한 메모리 오버헤드 발생.
-> 고정 크기라면 배열, 동적 크기라면 연결리스트가 유리
12. 원형 연결 리스트의 장점은?
원형 연결리스트는 마지막 노드가 첫 노드를 가리키는 구조.
리스트의 시작과 끝을 구분 할 필요 없고 원형 큐 구현할때 유리
라운드 로빈에 자주 사용됨
13. 멀티스레드 환경에서 배열과 연결리스트의 장단점?
배열 : 크기가 고정되어 있어 스레드 간 공유 시 동기화 단순하지만, 크기를 늘려야 할 경우 재할당 과정에서 충돌 위험 있음
연결 리스트 : 삽입/삭제가 자유롭지만 포인터 수정이 필요한 만큼 동기화 비용이 크고 오류 발생 가능성 높음
