글 쓰기에 앞서, ArrayList와 LinkedList의 자료구조적 기본에 대해선 서술하지 않겠다.
1. Time Complexity
| Method | ArrayList | LinkedList | |
| add at last index | add() | O(1) | O(1) |
| add at given index | add(index, value) | O(N) | O(1) |
| remove by index | remove(index) | O(N) | O(1) |
| remove by value | remove(value) | O(N) | O(1) |
| get by index | get(index) | O(1) | O(N) |
| search by value | indexOf(value) | O(N) | O(N) |
ArrayList는 연속적으로 메모리 상에 존재하고, LinkedList는 각 Node들이 포인터로 연결되어 있기에 생기는 시간 차이이다.
ArrayList에서 given index에 값을 추가하려면, 각 값들을 전부 옮겨주는 작업을 해야하기 때문에
포인터 하나를 바꾸면 되는 LinkedList에 비해 느릴 수 밖에 없다.
삭제도 위와 같은 이유로 시간 적으로 LinkedList가 확실한 이점을 갖는다.
반면, get을 수행할 때는 연속된 메모리인 ArrayList가 빠를 수 밖에 없을 것이다.
n번째 인덱스라면 배열 첫 원소의 메모리값 + (n-1) * 데이터 타입 크기를 하면,
Node를 쭉 따라가 찾아내야하는 LinkedList와 달리 한 번에 값을 찾아낼 수 있기 때문이다.
결론적으로, 삽입,삭제가 빈번한 자료구조를 원한다면 LinkedList, 인덱스의 값을 조회하는 일을 자주 수행한다면 ArrayList가
Time Complexity에 있어 유리할 것이다.
2. Space Complexity
Memory Usage의 측면에서 봤을 때는 ArrayList가 LinkedList에 비해 유리하다.
LinkedList는 노드와 포인터로 관리되기 때문에, prev, next를 유지하는 포인터라는 오버헤드가 발생하게 된다.