ArrayList
내부적으로 데이터를 배열에서 관리하며, 요소 삽입 시 배열의 크기를 넘어설 경우 새 배열을 만들고 기존 배열의 데이터를 모두 새 배열로 복사하기 때문에 O(n)이 걸린다. 따라서 많은 양의 자료를 추가/삭제하는 경우 데이터 복사가 빈번히 일어나므로 성능 저하를 일으킨다.
데이터를 배열로 관리하므로 인덱스를 통한 검색의 경우 O(1)이 걸린다.
LinkedList
한 개의 노드에 내가 갖고 있는 데이터와 다른 노드에 대한 정보를 갖고 있다.
단방향 링크드리스트의 경우 다음 노드에 대한 정보만 갖고 있고 양방향의 경우 이전 노드에 대한 정보도 갖고 있다.
LinkedList는 시작 요소나 가운데 요소를 삭제/삽입할 때 O(n) 시간이 걸리는 ArrayList와는 달리 다음 노드, 이전 노드에 대한 정보들만 변경하면 되므로 O(1)이 걸린다.
인덱스를 통해 요소에 접근하는 방식이 아니라 노드를 순차적으로 방문하며 요소를 찾기 때문에 조회의 경우 O(n) 시간이 걸린다.
https://en.wikipedia.org/wiki/Dynamic_array
Dynamic array - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search List data structure to which elements can be added/removed Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for e
en.wikipedia.org
'알고리즘, 자료구조' 카테고리의 다른 글
| 해시 (0) | 2022.07.06 |
|---|---|
| 완주하지 못한 선수 (0) | 2022.07.04 |
| 기능 개발 (0) | 2022.07.01 |
| 124 나라의 숫자 (0) | 2022.06.25 |
| 멀쩡한 사각형( 파이썬 ) - 프로그래머스 (0) | 2022.06.24 |