ArrayList 특징
- 구현 방법
- 배열을 이용하는 방식
- 조회
- 데이터가 연속된 공간에 저장된다.
- 배열
0번째 주소 + (배열원소타입 크기 x 인덱스)를 계산하여 데이터 조회한다. - 시간복잡도:
O(1)
- 삽입
- 데이터를 삽입하려는 위치부터 모든 데이터를 한 칸 씩 미루고, 데이터를 삽입한다.
- 배열은 크기가 정적으로 고정되어 있어, 배열이 꽉 차면 동적으로 배열 크기를 늘린다.
- 시간복잡도: 최악의 경우
O(n)
- 삭제
- 원하는 데이터를 삭제하고, 다음 위치부터 데이터를 한 칸씩 앞으로 당긴다.
- 공간 낭비를 하지 않도록 동적으로 배열의 크기를 줄인다.
- 시간복잡도: 최악의 경우
O(n)
ArrayList 삽입/삭제
이미지 출처 :: 🧱 ArrayList vs LinkedList 특징 & 성능 비교
- 배열 공간(
capacity)이 꽉 차거나, 요소 중간에 삽입을 행하려 할때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 한다.- 이러한 부가적인 연산이 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다.
- 자료들이 지속적으로 삭제되는 과정에서
ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 리사이징 처리에서 시간이 소모된다.
Linked List 특징
- 구현 방법
- 여러 노드를 연결하는 방식
- 노드 : 데이터, 다음 노드 주소를 관리하는 객체
- 조회
- 노드들은 불연속적인 공간에 저장된다.
- 첫번째 노드부터 인덱스에 해당하는 노드에 도착할 때까지 순회한다.
- 시간복잡도: 최악의 경우
O(n)
- 삽입
- 새로운 노드를 삽입하고, 노드 간의 연결관계를 업데이트한다.
- 시간복잡도:
O(1)(맨 앞이나 맨 뒤 요소만)
- 삭제
- 노드를 삭제하고, 노드 간의 연결관계를 업데이트한다.
- 시간복잡도:
O(1)(맨 앞이나 맨 뒤 요소만)
LinkedList의 장점
- 불연속적으로 존재하는 데이터를 서로 연결(
link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않는다. - 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다.
LinkedList의 단점
이미지 출처 :: 🧱 ArrayList vs LinkedList 특징 & 성능 비교
- 조회 시,
LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어ArrayList보다 당연히 긴 지연 시간이 소모되게 된다. - 참조자를 위해 추가적인 메모리를 할당해야 한다.
- 배열은 데이터를 그대로 저장하면 되지만,
LinkedList의 노드 같은 경우 데이터 이외에next나prev같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요하다.
연산별 시간복잡도 비교
첫번째 위치에 insert / remove
LinkedList (doubly):O(1)ArrayList:O(N)
마지막 위치에 insert / remove
LinkedList (doubly):O(1)ArrayList:O(1)/O(N)
중간에 insert / remove
LinkedList (doubly):O(N) / search time + O(1)ArrayList:O(1)/O(N)
값으로 search
LinkedList (doubly):O(N)ArrayList:O(1)/O(N)
인덱스로 값 get
LinkedList (doubly):O(N)ArrayList:O(1)
값으로 remove
LinkedList (doubly):O(N)ArrayList:O(N)
시간복잡도 차수 낮은 순서 🧶🪡
:O(1)>O(log n)>O(n)>O(n log n)>O(n^2)>O(n!)
보통
ArrayList와LinkedList중에 어느걸 사용하면 되냐고 묻는다면, 삽입 / 삭제가 빈번하면LinkedList를, 요소 가져오기가 빈번하면ArrayList를 사용하면 된다고 한다. 🥽
-> 이에 대한 다른 의견들이 많아서 뭐가 맞는 건지 모르겠음 . . .
출처
🧱 ArrayList vs LinkedList 특징 & 성능 비교
연결리스트 vs 배열리스트 선택하기 (+성능 향상 사례)
💻 ⚾️ 🐻