배열과 연결 리스트
배열 특징 같은 타입의 변수들로 구성 크기가 정해져 있음 인접한 메모리에 위치한 데이터를 모아놓은 집합, 따라서 랜덤 접근(direct access or random access)이 가능 탐색에 O(1), 삽입과 삭제에 O(n)의 시간복잡도를 가짐 메모리 재사용 불가 - 초기 사이즈 만큼 할당됨, 데이터 없어도 메모리 차지 연결 리스트 특징 데이터를 감싼 노드를 포인터로 연결, 따라서 랜덤 접근이 불가능 크기가 가변적 탐색에 O(n), 삽입과 삭제가 O(1)의 시간복잡도를 가짐 메모리 재사용 가능 - 삭제 시 해당 노드의 참조가 사라지고 GC에 의해 사용가능한 메모리로 전환됨.
CS/Data Structure
2022. 2. 20. 19:27