[JAVA Collection 1] ArrayList 와 LinkedList 의 차이

1. Collection 구조

• List 인터페이스 구현체로는 ArrayList , Vector , Stack 이 있다,
• LinkedList 는 List 인터페이스와 Queue 인터페이스를 구현한 Deque 인터페이스의 구현체이다.

 

 

2.  ArrayList 란?

• 중복을 허용한다
• 순서를 유지하며 인덱스로 원소를 관리한다
• 배열과 다르게 그 용량이 정해져있지 않다

List 인터페이스 만을 구현하는 ArrayLsit 는 내부적으로 자료를 배열 형태로 저장합니다. 배열과의 차이로는 배열은 최초 생성시 용량이 정해져있는데 반해 ArrayList는 크기가 가변적이라는 것입니다.

 

사실 ArrayList 도 내부적으로는 생성시 최대 용량이 정해져있고(10으로 고정) 해당 용량을 초과할시 새로운 배열로 옮기게 되어 있습니다.

 

3. LinkedList 란?

: 링크드리스트는 양방향의 연결 리스트로 구성되어 있는 자료구조 형태입니다.  이에따라 앞에서부터 혹은 뒤에서부터 순회하여 원소를 찾아내야하지만 데이터의 추가 삭제에 있어서 큰 이점을 보입니다.

 

 

4. ArrayList vs LinkedList 

위의 특징들을 종합하여 비교해보았을때

 

ArrayList 는 인덱스로 접근하기에 조회에 있어 빠르지만 추가/삭제시 새로운 배열을 생성하고 옮기는 과정을 거치기에비효율적인 면이 있습니다

 

반면 LinkedList 는 순차적인 조회로 인해 조회가 느리지만 추가 삭제시 새로운 배열로 옮기는 과정이 필요가 없기 때문에 빠르게 추가하고 삭제할 수 있는 이점을 가집니다. 만약 순회하면서 추가 삭제를 진행한다면 매우 좋은 선택일 것입니다

 

클래스	조회	추가 / 삭제	기타
ArrayList	빠르다	느리다	순차적인 추가 삭제는 더 빠름 , 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많아질 수록 접근성이 떨어짐

 

5. 시간복잡도의 비교

 

😀😀질문 : 맨앞 혹은 맨뒤가 아닌 가운데 값에 대한 추가 / 삭제에도 LinkedList 가 ArrayList 에 시간복잡도적 이점이 있을까?

 

시간복잡도 관점에서는 둘다 O(n) 으로 같게 됩니다.

실질적 LinkedList 가 doubly로 구현 되어 있으므로 앞뒤로 접근하여 속도적인 차이가 있을 수 있겠지만

 

linkedList 는 해당 위치까지 찾아가는데 O(n) , 추가 / 삭제시 O(1)로 최종적으로 O(n)이고

ArrayList 는 해당 위치 접근 O(1) , 추가 / 삭제시 배열의 앞의 원소를 두고 뒤에 원소들을 한개씩 연산하는 과정을 통해 O(n)으로 같은 O(n) 의 시간복잡도를 갖습니다.