📌 ArrayList
배열을 사용해서 List를 구현한다.
자바의 ArrayList의 예시를 보며 확인해보자.
List<Integer> list = new ArrayList<>();
list.add(10); // [10]
list.add(20); // [10, 20]
list.add(0, 30); // [30, 10, 20]
list.add(10); // [30, 10, 20, 10]
list.get(2); // 20
list.add(40); // [30, 10, 20, 10, 40]
list.contains(50); // false
list.remove(Integer.valueOf(10)); // 첫 번째 10 제거 → [30, 20, 10, 40]
list.remove(2); // 인덱스 2의 값(10) 제거 → [30, 20, 40]위와 같이 코드가 있을 경우,
- add(10) :배열로 만들어진 리스트에 아무것도 없기때문에 맨 앞 쪽에 10에 값을 추가해준다. [10]
- add(20) :그 다음 배열에 값을 추가해준다. [10,20]
- add(0,30) :0번째 인덱스에 30이라는 값을 추가하는 것이다. 하지만 현재 0위치에는 10이라는 값이 들어있기 때문에, 0인덱스에 30이라는 값을 넣고 나머지 값들을 오른쪽으로 시프트 연산이 일어나 한칸한칸씩 옆으로 이동한다 [30,10,20]
- get(2) :는 상수시간으로 인덱스 2번으로 접근할 수 있다. 20
- add(40) : 그 다음 배열에 값을 추가해준다. [30,10,20,40]
- contains(50) : 해당 배열에 50이 있는지 젤 앞에서부터 탐색을 하기때문에, 최악의 경우 O(n)의 시간이 발생한다.
- remove(Integer.valueOf(10) : 해당 배열에 10이 있는지 탐색하기 때문에, 최악의 경우 O(n)의 시간이 발생한다.
- remove(2) : 2인덱스를 삭제한다. 이는 상수시간의 접근 시간으로 삭제함.
📌 LinkedList
LinkedList는 노드를 연결시키는 형태로 구현한다. ArrayList는 배열에 저장이 되므로 연속적인 메모리 공간에 저장이 되며, LinkedList는 노드 각각이 포인트를 통해서 다음 노드를 가르키는 형태로 관리 되기 때문에, 연속이 아닌 띄엄띄엄 저장이 된다. 즉, 메모리에 어떻게 저장되는가가 차이점이다.
List<Integer> list = new LinkedList<>();
list.add(10); // [10]
list.add(20); // [10, 20]
list.add(0, 30); // [30, 10, 20]
list.add(10); // [30, 10, 20, 10]
list.get(2); // 20
list.add(40); // [30, 10, 20, 10, 40]
list.contains(50); // false
list.remove(Integer.valueOf(10)); // 첫 번째 10 제거 → [30, 20, 10, 40]
list.remove(2); // 인덱스 2의 값(10) 제거 → [30, 20, 40]이는 LinkedList로 표현한 코드입니다.
- add(10) : 리스트가 비어 있으므로 처음 노드로 10을 추가한다.
- add(20) : 다음 노드로 20을 추가한다.
- add(0, 30) : 인덱스 0에 30을 삽입한다. LinkedList는 인덱스로 직접 접근할 수 없기 때문에, 0번째 위치를 찾아갈 때까지 O(n) 시간이 걸린다. 찾은 뒤에는 포인터만 조작해서 삽입하므로 삽입 자체는 빠르다.
- add(10) : 맨 뒤에 값을 추가한다. 연결 리스트는 마지막 노드에 대한 참조만 있다면 바로 추가 가능하다.
- get(2) : 인덱스 2의 값을 가져오려면, 0 → 1 → 2로 노드를 따라가야 하므로 O(n) 시간이 걸린다.
- add(40) : 맨 뒤에 40을 추가한다. tail 참조가 있으면 O(1)에 가능하다.
- contains(50) : 앞에서부터 노드를 따라가며 50이 있는지 검사해야 하므로 최악의 경우 O(n).
- remove(Integer.valueOf(10)) : 값이 10인 노드를 찾아서 제거한다. 처음으로 발견된 노드를 지우며, 탐색 + 삭제가 필요하므로 O(n) 시간.
- remove(2) : 인덱스 2의 노드를 삭제하기 위해 0 → 1 → 2로 이동해야 하므로 O(n) 시간.
📌 ArrayList VS LinkedList
| 항목 | ArrayList 설명 | LinkedList 설명 |
|---|---|---|
| 구현 | 배열(array) 사용 | 노드를 연결(linked) |
| 데이터 접근 시간 | 모든 데이터 상수 시간 접근 (O(1)) | 위치에 따라 이동 시간 발생 (O(n)) |
| 삽입/삭제 시간 | 삽입/삭제 자체는 상수 시간 삽입/삭제 시 데이터 시프트가 필요한 경우 추가 시간 발생 | 삽입/삭제 자체는 상수 시간 삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생 |
| 리스트 크기 확장 | 배열 확장이 필요한 경우 새로운 배열에 복사하는 추가 시간 발생 | - |
| 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 |
| CPU cache | CPU cache 이점 활용 | - |
| 구현 예 | Java의 ArrayList, CPython의 list | Java의 LinkedList |
그래서 뭘 써야하는지에 대해서 굉장한 고민들이 있다. 하지만 결론부터 말하자면 그냥 ArrayList를 써라 이다.
ArrayList를 사용하면 삽입,삭제시 시프트 연산의 추가 시간과, 삽입시 배열이 꽉찼을 경우, 더 큰 배열을 만들어서 원래있던 데이터들을 복사하는 추가 시간이 발생한다. 하지만 이는 자바에서 매우 업그레이드 되며 튜닝이 되면서 매우 빠르게 성능이 실행된다고 한다.
또한, LinkedList구현체를 만든 개발자 또한 그냥 ArrayList를 쓰라고 한다.
결론 그냥, ArrayList가 좋다. 그냥 이거 써라!!이다.
면접에서 매우 많은 데이터 삽입이 있을 경우, ArrayList,LinkedList중 뭐가 쓰는게 맞을까라는 질문이 있었었고 그에 대답을 제대로 못한 것 같아 공부를 진행했다.
