ArrayList VS LinkedList

정태규·2023년 12월 21일
0

자료구조

목록 보기
9/9

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)이다.

결국 연결리스트는 추가, 삭제 할때도 탐색으로 인해 시간복잡도가 생긴다.

0개의 댓글