ArrayList 란?
ㄴ 데이터를 추가하는데로 사이즈가 늘어나는 자료구조
ㄴ 기본적으로 자바에서 제공되는 Array 의 경우에는 객체 생성시 배열의 크기를 지정해주어야한다.
ㄴ ArrayList 를 이용하면 데이터를 추가하는데로 사이즈가 늘어나 크기를 지정해주지 않고도 사용가능하다.
ArrayList 특징
ArrayList 는 배열 방이 다 차면, 배열의 크기를 2배로 늘려준다.
현재 배열보다 2배 큰 크기로 새로운 배열을 생성하고, 기존 배열에 있었던 데이터를 전부 복사하는 작업을 진행하는데 이를 더블링 이라 한다. 더블링 소요시간은 기존 가지고 있던 데이터 길이가 n 이라 할 때 O(n) 만큼이 소요된다.
ArrayList 성능
검색시간은 고정된 배열에서 검색되기 때문에 O(1) 이다.
입력시간 또한 더블링 이슈가 있음에도 O(1) 으로 표현할 수 있다.
더블링 시, 기존 배열의 크기는 새로운 배열 크기의 절반이다. 즉, 새로운 배열에 복사해야되는 양은 현재 배열방의 크기의 절반인 셈이다.
2/n + 4/n + 8/n + 16/n ... 2 + 1
직전 그 전 직전 그 전 직전의 직전 2개일 때 1개일 때
이를 다 더해도 합이 n 보다 작다. 합이 n에 다가가더라도 2배씩 커지기 때문에 복사하는 총 데이터가 n 보다 커지지 않는다.
하지만, 최악의 경우 값을 추가할 때 더블링 이슈가 발생하면 n개만큼 복사하는 시간을 기다려야 해서 이 경우에는 입력 시간복잡도가 O(n) 으로 표현할 수 있다.
LinkedList 란?
ㄴ 길이가 정해져있지 않은 데이터의 연결된 집합
ㄴ 단방향/양방향 연결리스트가 있다.
단방향 연결리스트
- header 주소 하나만 가지고 있고, 한쪽으로만 이동이 가능하다.
- 각각의 노드는 다음 노드의 주소를 가지고 있다.
- 자바의 경우 tail 주소도 저장하고 있어, 시작과 끝 노드의 삽입 삭제시 O(1) 의 시간복잡도를 가질 수 있는 것이다.
양방향 연결리스트
- header, tail 주소를 저장하고 있어, 맨 끝에 노드를 삽입할 때 끝까지 찾아가는 번거로움을 줄일 수 있다.
- 각 노드는 이전 노드의 주소와 다음 노드의 주소를 가지고 있어 양 방향으로 움직 일 수 있다는 특징을 가지고 있다.
LinkedList 구현
https://hyokeun0419.tistory.com/48
LinkedList 특징
ㄴ 특정 인덱스를 상수시간에 접근할 수 없다.
(특정 K 번째 원소를 찾고싶으면, K 번 루프를 돌아야한다.)
ㄴ 시작과 끝 지점에서 추가, 삭제 연산을 상수시간에 할 수 있다.
Array vs ArrayList vs LinkedList
5. Script
데이터를 추가하는데로 사이즈가 늘어나는 자료구조이다.
ArrayList는 내부적으로 데이터가 가득 차면 현재 배열보다 2배 큰 크기로 새로운 배열을 생성하고 기존배열에 있던 데이터를 전부 복사하는 작업을 진행하는데 이를 더블링이라 한다.
데이터 입력시 더블링이 발생하면, 소요시간은 기존 가지고 있던 데이터 길이가 n 이라 할 때 O(n) 만큼이 소요되는데, 평균적으로는 데이터 입력은 O(1) 으로 표현 할 수 있다. 기존 배열의 크기는 새로운 배열 크기의 절반인데, 복사되는 총 데이터가 새로운 배열보다 클 수 없기 때문이다. 그럼에도 최악의 경우에는 더블링이 발생되는 순간에는 O(n) 의 시간복잡도를 가질 수 있다.
LinkedList는 배열 길이가 정해져있지 않은 데이터의 연결된 집합이다.
배열과 달리 특정 인덱스를 찾고 싶으면 처음부터 순회를 해야하며, 시작과 끝 지점에 추가&삭제 연산을 상수시간에 할 수 있다는 특징이 있다.
'자료구조' 카테고리의 다른 글
| 그래프(Graph) 설명과 DFS, BFS 구현 (0) | 2021.10.30 |
|---|---|
| 트리(Tree) 설명과 구현 (0) | 2021.10.30 |
| LinkedList (0) | 2021.09.10 |
| HashTable (0) | 2021.08.21 |