728x90
반응형
Dynamic Array (Array List) vs Linked List
Data Structure - 두 번째 스터디 : Dynamic Array (Array List)와 Linked List
Dynamic Array (Array List) 기본 개념
- 내부적으로 배열을 사용하지만 List 인터페이스를 상속받아 크기가 가변적으로 변할 수 있는 순차리스트
- Java : ArrayList / C++ : Vector
- 배열의 크기를 변경하는(가변) resize() 연산 가능
- 동기화를 지원하지 않음 → Vector보다 속도가 빠름
- [특징 1] 검색 : 배열처럼 인덱스를 가지고 있어서 데이터 검색에 적합하고 속도가 빠름 → O(1)
- [특징 2] 삽입/삭제 : 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성해 복사하여 속도가 느림 → O(n)
Linked List 기본 개념
- 노드(데이터, 링크)로 구성되어 있어, 링크에 다음 데이터의 주소를 가리키고 있는 자료구조
- 논리적 저장순서와 물리적 저장순서 다름 → 검색 시 불편
- 사용자는 제일 첫 번재 노드의 위치만 알고 있고, 다른 노드들은 흩어져있음! 크기는 가변
- [종류] 링크드리스트(단일연결리스트), 이중연결리스트, 원형연결리스트, 다중연결리스트
- [특징 1] 검색: 원소를 찾기 위해 리스트를 순회해야하므로 → O(n) 그래도 Array보다 빠르긴 함!
- [특징 2] 삽입/삭제: 임의의 원소를 찾기 위해 순회 후 작업을 수행하므로 순회로 인해 → O(n)
Dynamic Array 와 Linked List의 비교
- 데이터의 검색 - Dynamic Array (Array List) 권장
- 데이터의 삽입, 삭제 - Linked List 권장
728x90
반응형
