ArrayList

List 의 종류 (3가지)

1. ArrayList

2. LinkedList

• 2-1 Single LinkedList
• 2-2 Double LinkedList 

Array(배열)기반의 List. 메모리를 연속적으로 사용

ArrayList는 실제 메모리 공간 상(물리적 공간)에서도 연속적으로, 데이터가 할당된다.(Array 특성과 동일)

 

 

ArrayList의 생성은 다음과 같은 구문들로 가능.

ArrayList<Integer> integers1 = new ArrayList<Integer>(); // 타입 지정
ArrayList<Integer> integers2 = new ArrayList<>(); // 타입 생략 가능
ArrayList<Integer> integers3 = new ArrayList<>(10); // 초기 용량(Capacity) 설정
ArrayList<Integer> integers4 = new ArrayList<>(integers1); // 다른 Collection값으로 초기화
ArrayList<Integer> integers5 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); // Arrays.asList()

 

다음 그림은 ArrayList인 int grade[3] 가 메모리 상에서 어떻게 저장되는지를 보여줍니다.

위의 그림처럼 배열의 이름은 ⇒ 배열의 첫 번째 요소와 같은 주소를 가리키고 있다. (grade = grade[0])

데이터 1개당 4칸의 주소를 가지고 있으며, 각 인덱스는 해당 데이터의 첫번째 주소를(0x10, 0x14, 0x18) 가리키고 있다.

 

ArrayList 의 get(검색) 은 랜덤 엑세스 방식 이며, List에 데이터가 얼마나 있든 인덱스만 알고 있으면 동일한 시간을 소요하여 데이터를 찾아 올수 있다. (Array 특성과 동일)

 

Array와 ArrayList의 가장 큰 차이점

• Array의 경우, Array의 크기를 꼭 선언해야 한다.
• ArrayList는 크기를 꼭 선언하지 않아도 된다.

=> 일반적으로 Array에 데이터가 몇개가 들어갈지 모르는 경우가 대부분이기 때문에, ArrayList를 사용하는 경우가 더 많음.

---

ArrayList 는 왜 검색(get) 이 빠른걸까? (랜덤엑세스, 인덱스)

1. 랜덤 엑세스 방식

랜덤 엑세스의 정의

 

해석하면, 랜덤 엑세스는 (때로는 직접 엑세스라고도 함)는 메모리 주소를 통해 모든 메모리에 저장된 데이터들에게 동일한 시간에 액세스하는 능력입니다. 데이터는 임의의 것인 지라 예측이 불가능 합니다. 하여 "랜덤"이라는 용어로 랜덤 엑세스 라고 한다. 그와 반대인 경우를 순차 엑세스.

 

랜덤,순차 엑세스의 차이는

• 고대 두루마리(순차, 원하는 데이터를 찾기 위하여 모든 자료를 찾아 보아야 함)
• 책(랜덤, 모든 데이터에 무작위로 직접 엑세스 할 수 있음)의 비교로 해석 할 수 있습니다.

또 다른 예를 들면

• 카세트 테이프(순차, 첫 노래를 들은 후에야만 다음 노래를 들을 수 있음)
• 축음기 레코드(렌덤, 원하는 노래에 직접 엑세스 할 수 있음)의 차이 입니다.

2. 인덱스(색인)

Array 는 인덱스만 따로 저장하는 공간을 가지고 있다. 각 인덱스는 해당 데이터를 가지고 있는 메모리 주소를 가지고 있다. 정렬되어 있는 int형 인덱스를 통해, 찾고자 하는 인덱스 부분만 Scan 하여 탐색 시간을 줄인다.

이렇게 인덱스를 통해, 메모리 주소를 알아내여 접근하여 데이터 추출 = 검색속도가 빠른이유

 

그래서 ArrayList.get[int index] 하게 되면

1. 인덱스가 저장된 공간에서 인덱스 검색
2. (검색될 만한 범위만 인덱스 검색 = 정렬 되어 있으니 173번 인덱스에 접근하고 싶으면 100번부터 검색한다. 책의 색인 개념)
3. 찾은 인덱스 안에서 메모리 주소값 추출
4. 메모리 주소에 접근해서 데이터 추출

ArrayList는 검색 속도가 빠르다 =  읽기(Reading[데이터1개]) 기능이 주로 필요한 경우 사용.

---

ArrayList 시간복잡도

add : List 맨 마지막에 추가 : O(1)

⇒ 상수시간 O(1) 만에 위치 찾아서, 바로 데이터 추가

 

insert : 중간삽입 : O(N)

⇒ 상수시간 O(1) 만에 위치 찾은 후, N개 개수 만큼 데이터를 뒤로 밀고 그 중간에 데이터 추가

 

get(index) : 인덱스를 통한 검색 : O(1)

⇒ 상수시간 O(1) 만에 위치 찾는다.

 

delete by value: 중간삭제 [값] : O(N^2)

⇒ 탐색으로 N번 만큼 데이터를 찾아다니고 데이터 삭제후, N개 개수 만큼 앞으로 땡겨야 함

 

delete by index : 중간삭제 [index] : O(N)

⇒ 상수시간 O(1) 만에 위치 찾은 후, N개 개수 만큼 앞으로 땡겨야 함