ArrayList vs LinkedList

LinkedList

- 노드를 포인터로 서로 연결하여 만든 리스트

- 데이터의 수정, 삭제가 빈번할 경우 빠른 속도를 보장함 => O(1)의 속도

- 인덱스 X => 조회 시 첫번째 노드부터 순차적으로 탐색 => O(N)의 속도

※ ArrayList의 경우 반대로 수정과 삭제 = O(N)의 속도지만 조회 = O(1)의 속도

=> 조회는 인덱스를 이용하여 빠르지만 수정/삭제의 경우 해당 명령 수행 후 뒷 순서 원소들의 인덱스를 조정하기 때문

ArrayList와 비교

	ArrayList	LinkedList
크기 제한	O	X
접근 방식	무작위(랜덤) 접근 가능 (인덱스 O)	순차 접근만 가능 (인덱스 X)
조회 속도	O(1)	O(N)
수정/삭제 속도	O(N)	O(1)

조회 시에는 ArrayList를 수정/삭제 시에는 LinkedList를 사용하는 것이 효율적