코딩초보의 자바(Java)공부 25일차 { 컬렉션프레임워크 - ArrayList와LinkedList }

ArrayList와
LinkedList에 대해
간략히 알아보겠습니다!

---

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 한다.

자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.

컬렉션 프레임워크와 자료 구조를 설명하기 전에 먼저 자료 구조의 가장 기본이 되는 배열의 특징을 알아보자.

 

**배열의 특징**

1.배열에서 자료를 찾을 때 인덱스(index)를 사용하면 매우 빠르게 자료를 찾을 수 있다.

2.인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.

 

3.배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하다.

**배열의 크기가 n이면 연산도 n만큼 필요하다.**

 

**배열 정리**

배열의 인덱스 사용: O(1)

배열의 순차 검색: O(n)

 

빅오표기법

*빅오 표기법의 예시**

**O(1)** - 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정한다.

예) 배열에서 인덱스를 사용하는 경우

 

**O(n)** - 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.

예) 배열의 검색, 배열의 모든 요소를 순회하는 경우

 

**O(n²)** - 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.

n²은 `n * n` 을 뜻한다.

예) 보통 이중 루프를 사용하는 알고리즘에서 나타남

 

**O(log n)** - 로그 시간: 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.

예) 이진 탐색

 

**O(n log n)** - 선형 로그 시간:

예) 많은 효율적인 정렬 알고리즘들

---

배열에 데이터를 추가할 때 위치에 따른 성능 변화**

 

배열의 첫번째 위치에 추가

배열의 첫번째 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.

모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다. 따라서 O(n) 만큼의 연산이 걸린다.

O(1 + n) O(n)이 된다.

 

배열의 중간 위치에 추가

배열의 위치를 찾는데는 O(1)이 걸린다.

index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 한다. 따라서 평균 연산은 O(n/2)이 된다.

O(1 + n/2) O(n)이 된다.

 

배열의 마지막 위치에 추가

이 경우 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계

산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.

---

배열의문제점

배열의 길이를 동적으로 변경할 수 없다.

데이터를 추가하기 불편하다.

데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 밀어야 한다. (이런 코드를 직접 작성해야 한다.)

 

**List 자료 구조**

순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.

 

 

ArrayList

 

데이터추가

 

---

앞에 추가

앞에 데이터를 추가하려면 리스트의크기만큼 데이터를 오른쪽으로 밀어야 함 o(n)

 

뒤에추가

위치를 이동할 필요가 없다!! o(1)

 

삭제의경우도 마찬가지인데 한번 그림으로 보자

---

뒤에 삭제

데이터이동필요X , O(1)

 

앞에삭제

앞에 빈 데이터를 뒤에데이터가 채워줘야함

(리스트는 순서가있는 자료구조)

데이터이동필요 , O(n)

---

ArrayList의 빅오 정리**

데이터 추가

마지막에 추가: O(1)

앞, 중간에 추가: O(n)

 

데이터 삭제

마지막에 삭제: O(1)

앞, 중간에 삭제: O(n)

 

인덱스 조회: O(1)

ㅣ

데이터 검색: O(n)

 

배열 리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가하거

나 삭제할 때는 성능이 좋지 않다.

 

 

 이런 단점을 해결한 자료 구조인 링크드 리스트(`LinkedList` )에 대해 알아보자.

 

---

LinkedList

배열리스트의 문제점

데이터를 중간에 추가하거나 삭제하면

데이터이동을 해야하는데 중간에 추가or삭제 시

엄청난 데이터 이동== 성능 Down

 

연결 리스트는 배열 리스트의 단점인,

메모리 낭비, 중간 위치의 데이터 추가에 대한 성능 문제를 어느정도 극복할 수 있다.

 

주요메서드

**void add(Object e)**

마지막에 데이터를 추가한다.

새로운 노드를 만들고, 마지막 노드를 찾아서 새로운 노드를 마지막에 연결한다.

만약 노드가 하나도 없다면 새로운 노드를 만들고 `first` 에 연결한다.

 

**Object set(int index, Object element)**

특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.

`getNode(index)` 를 통해 특정 위치에 있는 노드를 찾고, 단순히 그 노드에 있는 `item` 데이터를 변경한다.

 

**Object get(int index)**

특정 위치에 있는 데이터를 반환한다.

`getNode(index)` 를 통해 특정 위치에 있는 노드를 찾고, 해당 노드에 있는 값을 반환한다.

 

**int indexOf(Object o)**

데이터를 검색하고, 검색된 위치를 반환한다.

모든 노드를 순회하면서 `equals()` 를 사용해서 같은 데이터가 있는지 찾는다.

 

**데이터 추가하기**

void add(Node node, String param) {

Node lastNode = getLastNode(node);

lastNode.next = new Node(param);

}

데이터를 추가할 때는 새로운 노드를 만들고, 마지막 노드에 새로 만든 노드를 연결하면 된다.

순서대로 설명하면 먼저 마지막 노드를 찾고, 마지막 노드의 `next` 에 새로운 노드를 연결하면 된다.

 

구조예시

 

조회에 단점 존재

 

인덱스 수 만큼 반복해서 이동해야 조회가능!

 

---

첫 번째 위치에 데이터 추가 (O(1))

노드에 다음과 같은 데이터가 있다고 가정해보자.

`[a->b->c]`

첫 번째 항목에 `"d"` 를 추가해서 `[d->a->b->c]`

로 만드는 코드를 분석해보자.

배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는

새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다

 

연결 리스트의 첫 번째 항목에 값을 추가하는 것은 매우 빠르다. O(1)로 표현할 수 있다

 

---

첫번째 위치 데이터 삭제

`[d->a->b->c]`로 만들어진 노드를

`[a->b->c]`로 변경

더는 Node0을 참조하는곳이없다 (GC에 의해 삭제됨)

 

배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만

연결 리스트는 일부 참조만변경하면 된다. 

 

연결 리스트의 첫 번째 항목에 값을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

---

중간 데이터삭제

 

O(n)의 성능이다.

연결 리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸린다.

연결 리스트에서 항목을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

---

 

배열 리스트 vs 연결 리스트 사용**

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 앞쪽의 데이

터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.