JAVA에서 ArrayList와 LinkedList에 관해, 그리고 vector

JAVA에서 ArrayList와 LinkedList에 관해, 그리고 vector

ArrayList클래스

java의 Collection중 하나이다.

ArrayList는 기존 자바 List와 달리 동적으로 크기가 할당된다.

ArrayList는 java 메모리의 주소를 사용하여 데이터를 저장시킨다.
실질 ArrayList의 내부는 배열의 형태를 갖고 있기 때문이다.
그렇기 때문에 데이터를 검색할 때에도 바로 검색할 수 있다.
알아보기 쉽게 표현하자면 다음과 같다.

이런 식으로 각각의 data들이 하나씩 존재한다.

---

그럼 여기서 값을 추가하려면 어떻게 될까?

이런 식으로 새로운 값을 넣어주려면, 저 노란 색의 데이터가 들어가기 위해 뒤의 값들을 하나하나 옮겨주어야 할 것이다.

1. 해당 위치를 찾아가서
2. 값을 넣어준 뒤
3. 배열을 복사하여 옮기는 로직이다.

---

그럼 값을 찾으려면 어떻게 해야 할까?
해당 위치에서 노란색 값을 찾으려면 그냥 노란색 값의 위치를 찾아가면 된다.

1. 단순히 해당 위치를 찾아가면 된다.

---

값을 삭제하는 경우는?
노란색 값을 삭제하면 다음과 같다.

1. 해당 위치를 찾아가서
2. 값을 삭제해준 뒤
3. 뒤에 있던 값들을 하나씩 가져오는 연산이다.

---

값의 변경의 경우는 해당 위치만을 찾아 변경하면 된다.

1. 해당 위치를 찾아가서
2. 바꿈

---

이를 통해 알 수 있는 것은
ArrayList의 경우

get / set은 O(1)
add, remove는 O(n) -> 해당위치를 찾는시간(O(1)+배열을 복사하여 옮기는 시간O(n))
에 해당하는 시간 복잡도를 갖는다고 할 수 있다.

다만, 실제로 add연산을 하는 경우 사실은 이보다 복잡한 연산이 이루어진다고 한다.

실제 add연산의 경우
기본 capacity를 10으로 할당하고, 이보다 데이터가 많은 경우 기존 capacity의 50%를 증가시키는 순으로 진행한다.

1. 기본 10의 용량
2. 데이터를 11개 집어넣게 된다.
3. 10개의 데이터가 들어가고, 데이터는 15개의 용량을 갖게되며 11개의 데이터가 들어가는 순서.

이렇게 진행되는 이유는 데이터가 필요할 때 마다 용량을 늘려 주면 O(n)만큼의 시간 복잡도가 추가로 소요되어 총 O(n^2)의 시간 복잡도가 요구되겠지만하지만, 이렇게 50%만큼 증가하게 되면 급격히 줄어들어 O(상수시간)만큼의 시간복잡도만이 필요하게 되고, add가 O(n)의 시간복잡도를 갖도록 할 수 있기 때문이다.

LinkedList 클래스

java의 Collection중 하나이다.
이름에서 알 수 있듯, 연결 리스트 형태이다.
LinkedList는 Node를 서로 연결하여 만들어낸 선형 자료구조이다.

이런 식으로 data들이 연결되어 있음을 볼 수 있다.

---

그럼 여기서 값을 추가할 때 어떻게 할까?

노란색을 추가하기 위해서는

1. 해당 위치에 도착할 때 까지 앞에서부터 이동한다.
2. 그 위치에 도달하면 값을 넣어준다.
3. 뒤에 값들은 연결되어 있으므로 한꺼번에 뒤로 옮겨준다.

---

다음으로 값을 찾아가는 로직 또한

1. 바로 해당하는 위치로 도달할 수는 없고, 앞에서부터 탐색해나가며 도달한다.

---

값을 삭제하는 로직은 다음과 같다.

1. 해당 위치로 찾아가서
2. 값을 제거하고
3. 뒤의 값은 한번에 앞의 값에 붙일 수 있다.

---

값의 변경 로직은 당연히

1. 해당 위치를 찾아가서
2. 변경해주면 된다.

---

이를 통해 알 수 있는 것은
LinkedList의 경우

get / set은 O(n) -> 해당위치를 찾아가는데에 걸리는 시간
add, remove는 O(n) -> 해당위치를 찾는시간(O(n)+데이터를 옮기는 시간O(1))
에 해당하는 시간 복잡도를 갖는다고 할 수 있다.

---

비교

위에서 정리한 내용을 바탕으로 확인해 보면

	ArrayList	LinkedList
Add	O(n)	O(n)
get	O(1)	O(n)
remove	O(n)	O(n)
set	O(1)	O(n)

일단 이런 식으로 나오기 때문에...이것만 보면 LinkedList는 무조건 ArrayList보다 시간복잡도가 안좋은거 아닐까? 라고 생각할 수 있다.

그런데 실제로 알고리즘을 할 때에는 중간에서만 데이터 작업을 진행하지는 않을 것이다.

그럼 뭐가 있는데?

하다못해 곤충도 머리 가슴 배 세부분으로 나누는데, 데이터도 처음 중간 끝 세가지로는 나눠줘야 하지 않을까??

1. List의 처음에서 작업하는 경우
2. List의 중간에서 작업하는 경우
3. List의 끝에서 작업하는 경우

이렇게 총 3가지 경우로 뭉뚱그려 나눌 수 있다.

앞서 설명했듯, 둘의 차이를 만들어내는 요소는

• ArrayList
  • 찾아가기
    • 바로 해당 위치로 찾아감
  • 다른 값을 이동하기
    • 하나씩 옮김
• LinkedList
  • 찾아가기
    • 하나씩 이동하며 찾아감
  • 다른 값을 이동하기
    • 한번에 옮김

이렇게 있다고 했다.
그러면 만약 처음 부분에 대해 작업한다면??

---

ArrayList에서 처음 위치에 대해 add하면

1. 해당 위치를 찾아가서
2. 변경하고
3. 다른 값들을 하나씩 옮겨서
4. O(1) + O(n)의 시간 복잡도가 걸릴 것이다.

LinkedList에서 처음 위치에 대해 add하면

1. 해당 위치를 찾아가서(처음위치니까 O(1))
2. 변경하고
3. 다른 값들을 한번에 옮겨서
4. O(1) + O(1) -> O(1)의 시간 복잡도가 걸릴 것이다.

당연하지만 이는 remove도 마찬가지이다.

---

그렇다면 마지막 위치라면?
ArrayList에서 마지막 위치에 대해 add하면

1. 해당 위치를 찾아가서
2. 변경하여
3. O(1) + O(1)의 시간 복잡도가 걸릴 것이다.

LinkedList에서 마지막 위치에 대해 add하면

1. 해당 위치를 찾아가서(마지막위치니까 O(1))
2. 변경하고
3. 다른 값들을 한번에 옮겨서
4. O(1) + O(1) -> O(1)의 시간 복잡도가 걸릴 것이다.

---

이렇게 확인해 보면, List의 시작과 끝 부분에서 작업을 할 경우 LinkedList가 ArrayList보다 상대적으로 효율적인 시간 복잡도를 가짐을 확인할 수 있다.

---

결론

• 처음

	ArrayList	LinkedList
Add	O(n)	O(1)
get	O(1)	O(1)
remove	O(n)	O(1)
set	O(1)	O(1)

---

• 중간

	ArrayList	LinkedList
Add	O(n)	O(n)
get	O(1)	O(n)
remove	O(n)	O(n)
set	O(1)	O(n)

---

• 끝

	ArrayList	LinkedList
Add	O(1)	O(1)
get	O(1)	O(1)
remove	O(1)	O(1)
set	O(1)	O(1)

---

이렇게 되므로, 상황에 맞춰 잘 선택해 주기 바란다.

추가적으로 공간복잡도(메모리 용량)의 측면에서는 ArrayList가 더 우월하다.
LinkedList는 노드와 포인터로 관리되기 때문에, 다음/이전값을 찾아가기 위한 오버헤드가 발생하기 때문이다.

번외) Vector클래스

java의 Collection중 하나이다.
예에에에에전 자바 초창기부터 있던 클래스이다.
사실 그동안 자바를 해왔던 사람들 중, 이 클래스가 익숙치 않은 사람들이 많을 것이라 생각한다...나도 그렇고.

그 이유는 단순히, 이거 이제 잘 안쓰이기 떄문이다.

그냥 말하자면 동기화가 지원되는 ArrayList라고 생각하면 된다.
ArrayList는 thread-safe하지 않은데, 이 Vector클래스는 작업 도중 thread-safe를 유지시켜 주기 위해 동기화를 진행시키는 것이다.

근데 문제는...무조건 다른곳에서의 접근을 차단시켜 버리기 때문에 성능이 매우 떨어진다.
마치 여기에 있는 HashTable과 같은 친구라 생각하면 편할 것 같다.
요즘은 Collection. synchronizedCollection(Collection c)나synchronizedList/Map같은 친구에게 밀린다고 하니 그걸 사용하면 될 것 같다.

추가로, 아까 설명했다시피 ArrayList는 인덱스 증가시 최대 크기의 50%가 증가하는데 이 vector은 최대 크기의 100%가 증가하게 된다.