ArrayList
ArrayList는 주소 공간이 쭉 나열되어 있는
배열과 같은 형태이지만, 크기를 동적으로 할당 할 수 있다는 장점이 있다.
조회
원하는 데이터에 무작위로 접근할 수 있어서 조회 성능이 좋다.
시간 복잡도: O(1)
추가
맨뒤가 아닌 곳에 추가 하기 위해서는 추가 하고나서 추가한곳보다 뒤에 있는 배열은 한칸씩 다 뒤로 밀어야 한다.
맨뒤가 아닐 경우 시간 복잡도: O(n)
맨 뒤일 경우: O(1)
삭제
추가와 마찬가지로 맨 뒤가 아니라면 삭제 한 뒤 모두 앞으로 땡겨줘야 한다.
맨뒤 값 삭제: O(1)
나머지 : O(n)
LinkedList
LinkedList는 각 node마다 앞,뒤 노드의 주소 값을 가지고 있어서, 내부 적으로 연결 되어 있고, 순차적으로 접근하게 되어 있다.
조회
연결리스트는 맨 앞에서부터 순차적으로 탐색하게 되어 있기 때문에
시간복잡도: O(n)
추가
추가하려는 위치를 맨 앞에서부터 하나씩 탐색해서 가야 하므로, 맨 앞이라면 O(1)
뒤로 간다면 O(n)이 된다.
삭제
추가와 마찬가지로 삭제하려는 데이터가 맨 앞이면 O(1), 아니라면 O(n)이다.
결국 연결리스트는 추가, 삭제 할때도 탐색으로 인해 시간복잡도가 생긴다.
