LinkedList
삭제에 용이
-
제일 뒤에 추가시: O(N) -> 추가시 뒤까지 다 찾아가야 함.
- 제일 앞에 추가시: O(1) -
중간에 삽입하는 경우: O(N) -> 데이터를 찾아가야함.
-
삭제: O(1) -> 데이터를 밀어주는 작업 없이 포인터만 옮김.
-
검색: O(N) -> 한번씩 다 순회해야함.
ArrayList
검색에 용이
-
제일 뒤에 추가시: 인덱스로 찾아갈 시 O(1).
- 단, 배열이 꽉 차있는 경우 배열의 사이즈를 재할당해서 옮겨야하므로 O(N) -
삽입, 삭제: 시간복잡도 O(N) -> 찾아가는 건 인덱스로 한 번에 찾지만, 땡겨주고 밀어주는 작업 해줘야함.
-
검색: 시간복잡도 O(1) -> 랜덤액세스, 인덱스로 바로 찾음.
