[JAVA] ArrayList와 LinkedList의 차이

※ ArrayList와 LinkedList 모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체이다.

 

ArrayList란?

ArrayList(선형리스트)는 List 인터페이스를 구현한 클래스로, 크기가 가변적으로 변하는 선형리스트입니다.

일반적인 배열과 같이 인덱스로 내부의 객체를 관리한다는 점 등이 유사하지만, 한 번 생성되면 크기가 변하지 않는 배열과는 달리, ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고 있습니다.
하지만 추가되었을 때 기존 배열이 동적으로 늘어나는 것이 아니라, 기존 배열의 용량보다 더 큰 용량의 배열을 생성하여 내용을 복사하는 작업을 수행하게 됩니다.
즉, ArrayList는 내부에 고정된 크기를 갖는 배열을 가지고 있고, 어떤 요소를 추가할 때 그 배열의 크기를 넘어가게 되면 늘린 크기의 배열을 새로 할당해 줍니다.

---

LinkedList란?

https://www.geeksforgeeks.org/data-structures/linked-list/

LinkedList(연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.

노드는 LinkedList에 객체를 추가하거나 삭제하면, 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않기 때문에 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없습니다. 그렇기 때문에 ArrayList에 비해서 데이터의 추가나 삭제가 용이합니다.
하지만 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

 

※ ArrayList와 LinkedList의 차이

ArrayList는 크기가 고정된 배열과 달리 동적으로 크기를 늘릴 수 있고, LinkedList와는 달리 특정 인덱스 배열에 빠르게 접근할 수 있다는 특징이 있습니다.
동적으로 크기를 늘릴 때의 특징은 지정된 크기를 벗어났을 때, 더 큰 크기의 배열을 새로 생성하여 복사한 후 새로 할당한다는 것입니다.

LinkedList 또한 크기를 동적으로 늘릴 수 있다는 특징이 있습니다.
LinkedList는 데이터를 추가하거나 삭제할 때, 앞뒤의 링크만 변경되고 나머지 링크는 변경되지 않기 때문에 전체의 인덱스가 밀리거나 당겨지는 일이 없습니다.
하지만 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어지게 됩니다.

그러므로 탐색 또는 정렬을 자주 하는 경우엔 ArrayList를 사용하고, 데이터의 추가/삭제가 많은 경우에는 LinkedList를 사용하는 것이 좋습니다.

 

 

[참고]

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

https://ttungbab.tistory.com/167