[JAVA] 컬렉션 - List 정리 (ArrayList, LinkedList)

1️⃣ List 란 ?

List 란 순서가 있고, 중복을 허용하는 자료 구조를 말합니다. 

List 인터페이스는 ArrayList, LinkedList 와 같은 여러 구현 클래스를 가지고 있습니다. 

 

이제, ArrayList 와 LinkedList 에 대해 자세히 알아보겠습니다.

---

2️⃣ ArrayList

ArrayList<Integer> list = new ArrayList<>();

 

자바에서 크기가 동적으로 변경되는 배열이 필요할 때는 ArrayList 를 사용합니다.

ArrayList 는 배열을 사용하여 데이터를 관리합니다. 기본 CAPACITY 는 10이며, 기존 CAPACITY 를 넘어가면 배열을 50% 증가합니다. 

 

ArrayList 는 배열을 사용하기 때문에 인덱스를 활용하여 한 번에 원하는 데이터를 찾을 수 있다는 장점이 있지만,  데이터를 추가할 때 다른 데이터의 이동이 필요합니다. ArrayList 는 메모리 고속 복사 연산을 사용(System.arraycopy())하여 배열의 요소 이동을 비교적 빠르게 수행합니다. 

 

배열과 리스트의 차이점은배열은 순서가 있고 중복을 허용하지만, 크기가 정적으로 고정됩니다. 리스트는 순서가 있고 중복을 허용하지만, 크기가 동적으로 변할 수 있습니다.

 

✅ 맨 앞에 데이터를 추가할 때   O(n)

위의 그림과 같이 배열에 1,2 라는 값이 들어가있는 상태에서 맨 앞에 3이라는 값을 추가하고 싶으면, 

인덱스 [0], [1] 에 있는 값을 뒤로 전부 밀어야 합니다. 

 

결과적으로는 이런 그림이 될 것이고, 맨 앞에 값을 찾는데는 O(1) 의 시간이 걸리지만, 

뒤에 있는 모든 값들을 이동시켜야 하기 때문에 결과적으로 맨 앞에 데이터를 추가할 때 O(n) 의 시간이 걸립니다. 

• 배열의 첫 번째 위치를 찾는데 걸리는 시간 O(1)
• 모든 데이터를 배열의 크기만큼 한 칸씩 이동하는데 걸리는 시간 O(n)
• 최종 : O (1 + n) ➡ O (n)

✅ 중간에 데이터를 추가할 때 O(n)

중간에 데이터를 추가할 때도 마찬가지로, 인덱스를 활용하여 중간위치를 찾는 건 O(1) 의 시간이 걸리지만,

중간부터 나머지의 값을 뒤로 밀어야 하기 때문에 중간에 데이터를 추가할 때도 마찬가지로 O(n)의 시간이 걸립니다.

 

• 배열의 위치를 찾는 데 걸리는 시간 O(1)
• index 의 오른쪽에 있는 데이터를 한 칸씩 이동하는데 걸리는 시간 O(n/2)
• 최종 : O (1 + n/2) ➡ O(n) 

✅ 맨 뒤에 데이터를 추가할 때 O(1)

 

반면, 맨 뒤에 데이터를 추가할 때는 인덱스를 찾는 데 걸리는 시간은 O(1) 이고, 

다른 데이터를 이동시킬 필요가 없기 때문에 맨 뒤에 데이터를 추가할 때 걸리는 시간은 O(1) 입니다. 

• 마지막 인덱스에 접근하는 데 걸리는 시간 O(1)
• 최종 : O(1)

✅ 데이터를 검색할 때 O(n)

 

ArrayList 에서 데이터를 검색할 때는 해당하는 데이터가 있는지 맨 앞에서부터 하나씩 찾아야하므로  O(n) 의 성능을 가집니다.

 

✅ 인덱스를 조회할 때 O(1)

 

배열의 인덱스를 통해서 한 번에 원하는 인덱스를 찾을 수 있으므로 O(1) 의 성능을 가집니다. 

---

3️⃣ LinkedList

LinkedList<Integer> list = new LinkedList<>();

 

LinkedList 란 노드와 연결 구조를 통해 구현한 리스트를 말합니다. 

자바에서 제공하는 LinkedList 는 이중 연결 구조로 이루어져 있습니다.

이 구조를 통해 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있습니다. 

LinkedList 구조

 

✅ 맨 앞에 데이터를 추가할 때  O(1)

 

LinkedList 에서 맨 앞에 데이터를 추가할 때는 Node first 라는 맨 앞을 가리키고 있는 노드가 있기 때문에 빠르게 위치를 찾을 수 있습니다. 

또한 배열과는 다르게 next 와 prev 의 참조값만 변경하면 되기 때문에 O(1) 의 시간으로 맨 앞에 데이터를 추가할 수 있습니다. 

 

✅ 중간에 데이터를 추가할 때 O(n)

 

중간에 데이터를 추가하는 경우에는 해당하는 데이터를 찾으러 맨 처음부터 찾아야 합니다. 여기서 O(n) 의 시간이 발생합니다. 데이터를 찾은 후, 추가할 때는 참조값만 변경하면 되기 때문에 O(1) 의 시간이 발생합니다. 따라서 O(1+n) ➡ O(n) 의 성능을 제공합니다.  

 

✅ 맨 뒤에 데이터를 추가할 때 O(1)

 

LinkedList 는 맨 뒤를 가리키는 Node last 를 가지고 있기 때문에, 맨 뒤의 값을 O(1) 로 빠르게 찾을 수 있습니다. 또한, 추가할 때는 참조값만 변경하면 되기 때문에 최종적으로 맨 뒤에 데이터를 추가할 때는 O(1) 의 성능을 갖습니다. 

✅ 데이터를 검색할 때 O(n)

 

LinkedList 에서 데이터를 검색할 때 맨 앞에서부터 원하는 값이 있는지 찾아야하므로 O(n) 의 성능을 갖습니다. 

 

✅ 인덱스를 조회할 때 O(n)

 

인덱스를 조회할 때도 마찬가지로, 맨 앞에서 노드를 인덱스 수 만큼 이동해야하므로 O(n) 의 성능을 갖습니다. 

---

4️⃣ ArrayList 와 LinkedList 의 성능 비교 (속도)

기능	ArrayList	LinkedList
앞에 추가(삭제)	O(n) - 231ms	O(1) - 5ms
평균 추가(삭제)	O(n) - 118ms	O(n) - 1818ms
뒤에 추가(삭제)	O(1) - 8ms	O(1) - 4ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 200ms
검색	O(n) - 평균 600ms	O(n) - 평균 800ms

 

 코드를 돌려보면 ArrayList 와 LinkedLIst 는 위와 같은 성능을 보이는 것을 확인할 수 있습니다. 

이론적으로 LinkedList 의 중간 삽입 연산은 ArrayList 보다 빠를 수 있습니다. 

그러나, 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다앙한 요소에 의해서 영향을 받습니다. 

 

실제, ArrayList 는 한칸씩 이동하지 않고 메모리 고속 복사를 사용하여 속도가 훨씬 빠르고, 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠릅니다.

 

반면에,  LinkedList 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있습니다. 

 

맨 앞에 데이터를 추가해야할 경우가 많은 경우, LinkedList 를 사용하는게  더 좋을 순 있지만 데이터의 양이 매우 많은 경우 차이를 실감할 수 있습니다. 

 

따라서 !!!! 대부분의 경우 ArrayList 가 성능상 유리하기 때문에 실무에서는 주로 ArrayList 를 기본으로 사용합니다. 

---

 

 

🔍 참고글

인프런 [김영한의 실전 자바 - 중급 2편]  섹션 6 컬렉션 프레임워크 - List 강의를 참고하여 작성했습니다.