⚡ 자료구조 - 배열과 연결 리스트

🔹 배열(Array)

• 메모리에 연속적으로 저장됨
• 인덱스를 통해 빠르게 접근할 수 있음
• 크기가 고정되어 있음
• 삽입과 삭제는 느리며 CPU 캐시 효율이 좋음
• 접근 속도에 강점

🔹 연결 리스트(Linked-List)

• 각 요소가 다음 요소의 주소를 포함
• 메모리에 비연속적으로 저장됨
• 순차 접근만 가능
• 삽입과 삭제는 빠르지만 임의 접근은 불가능
• 각 노드가 포인터를 포함하므로 메모리 오버헤드 발생
• 중간 삽입 삭제에 강점

🔹 공통점

• 둘 다 탐색은 느림

🔹 특징 비교

구분	배열	연결 리스트
메모리 저장 방식	메모리에 연속적으로 저장됨	메모리에 비연속적으로 저장됨
접근 방식	인덱스를 통한 빠른 접근 가능	순차적으로 접근해야 함
삽입과 삭제	삽입과 삭제가 느림	삽입과 삭제가 빠름
크기 조절	크기 변경이 어려움	유동적으로 크기 조절 가능
캐시 효율	캐시 효율이 좋음	캐시 효율이 좋지 않음
메모리 사용	고정된 메모리를 사용	각 노드가 포인터를 포함하므로 메모리 오버헤드 발생

🔹 시간 복잡도 비교

연산	배열	연결 리스트
접근	O(1)	O(n)
탐색	O(n)	O(n)
삽입 (끝)	O(1) 또는 O(n)	O(n) (단일 리스트 기준)
삽입 (중간)	O(n)	O(n)
삭제 (끝)	O(1) 또는 O(n)	O(n)
삭제 (중간)	O(n)	O(n)

• 배열은 끝 삽입 시 공간이 남아있다면 O(1), 없으면 재할당으로 O(n)
• 연결 리스트는 끝 삽입 시 마지막 노드 탐색이 필요하므로 O(n)