연결리스트와 배열의 비교

 

장점 

• 연결 리스트: 데이터 삽입 및 삭제가 유연하며, 크기의 제한 없이 사용할 수 있다.
• 배열: 인덱스를 통한 빠른 데이터 접근이 가능하며, 연속된 메모리 공간에 데이터를 저장하므로 캐시 효율성이 좋다.

단점

• 연결 리스트: 특정 위치에 접근할 때 순차적으로 노드를 따라가야 하므로 접근 속도가 느리다.
• 배열: 크기를 미리 설정해야 하고, 크기 변경이 어려워 메모리 낭비가 발생할 수 있다. 

특성	배열	연결 리스트
메모리 사용	고정 크기 (초기 할당 시 전체 크기를 설정)	동적으로 할당 (필요한 만큼만 사용)
삽입 및 삭제	중간 삽입/삭제 시 뒤의 원소를 모두 이동 (O(N))	앞이나 중간 삽입이 용이
인덱싱	O(1) 인덱스를 통한 즉시 접근 가능	O(n)  (연결을 따라가야 함)
메모리 효율성	데이터만 저장하므로 메모리 사용 효율적	각 노드마다 포인터를 저장해야 하므로 추가 메모리 필요
데이터 크기 변화	크기 변경이 어렵거나 불가능(재할당 필요)	자유롭게 크기를 조정 가능

(reference : 허니C코딩)