ArrayList vs LinkedList

ArrayList

• 연속된 메모리 공간에 저장이 된다
• 인덱스를 통한 접근(Random Access)가 가능하다
• CPU Cache를 통해 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있다.
• 데이터의 삽입/삭제시 데이터시프트에 의한 O(N)의 시간이 소요될 수 있다.
• 동적배열의 추가적인 크기증가를 위한 기존배열을 복사하는데 시간이 소요된다.
• 데이터탐색에는 O(N)의 시간이소요된다.

삽입/삭제

맨앞에 데이터를 삽입/삭제시 데이터시프트에 의한 O(N)의 시간소요
맨뒤에서 데이터를 삽입/삭제시 배열의 확장이 필요하지 않다면 O(1)의 시간소요
중간에 데이터를 삽입/삭제시 O(N)의 시간소요. 메모리에 빈공간이 존재한다고 배열의 사이즈를 줄이지는 않는다.

LinkedList

• 메모리상에 각 노드들이 산재되어 생성되어 있으며 현재노드와 다음노드를 가리키는 포인터로 노드들을 연결시키는 형태로 구현
• 데이터에 접근할 때 head혹은 tail로 부터 순차적인 접근이 가능하다
• 데이터 삽입/삭제시 해당 데이터위치까지 이동하기 위한 시간 O(N)이 소요된다.
• 데이터탐색에는 O(N)의 시간이소요된다.

삽입/삭제

맨앞에 데이터를 삽입/삭제시 O(1)의 시간소요
맨뒤에서 데이터를 삽입/삭제시 tail이 존재한다면 O(1), tail이 존재하지 않는다면 데이터위치까지 접근하기 위한 O(N)의 시간소요
중간에 데이터를 삽입/삭제시 해당지점까지 도달하기위한 시간소요

비교

	ArrayList	LinkedList
구현	배열로 구현	노드와 포인터
데이터접근시간	O(1)	O(N)
삽입/삭제	O(N)	O(N)
크기확장	O(N)	O(1)
검색	O(N)	O(N)
CPU CACHE	CPU CACHE 이점활용	x