배열과 연결 리스트

배열

---

특징

• 같은 타입의 변수들로 구성
• 크기가 정해져 있음
• 인접한 메모리에 위치한 데이터를 모아놓은 집합, 따라서 랜덤 접근(direct access or random access)이 가능
• 탐색에 O(1), 삽입과 삭제에 O(n)의 시간복잡도를 가짐
• 메모리 재사용 불가 - 초기 사이즈 만큼 할당됨, 데이터 없어도 메모리 차지

연결 리스트

---

특징

• 데이터를 감싼 노드를 포인터로 연결, 따라서 랜덤 접근이 불가능
• 크기가 가변적
• 탐색에 O(n), 삽입과 삭제가 O(1)의 시간복잡도를 가짐
• 메모리 재사용 가능 - 삭제 시 해당 노드의 참조가 사라지고 GC에 의해 사용가능한 메모리로 전환됨.