ArrayList와 LinkedList의 차이

Java에서 List 인터페이스 구현체들의 차이점을 알아보자.

List 인터페이스의 대표적인 구현 클래스로 ArrayList와 LinkedList가 있다.

앞서 살펴봤듯이 List 인터페이스는 기존 Java Array 기본 객체의 여러 한계('크기가 정해져있다', '대량의 데이터 사용에는 성능이나 기능이 떨어진다')를 보완하고 여러 기능을 추가하여 리스트 관리에 보다 효율적인 인터페이스이다. 

List 인터페이스를 실제 클래스로 구현한 것들 중 ArrayList와 LinkedList가 있다. 어떤 차이가 있고 언제 왜 이걸 쓰는지 살펴보자.

ArrayList : 일렬로 줄서있다

물건이 일렬로 나열되어 있는 리스트를 생각해보자. 쉽게 생각하면, 도서관의 책장에 꽂혀있는 책들을 생각해보자. 책들이 순서대로 꽂혀있다. 책이 많아지면 책장을 더 늘린다. 어떤 특정 책을 찾고 싶으면 '몇째줄 몇칸'을 찾아가면 금방 찾을 수 있다. 하지만 만약 꽉 차있는 책장에 신규 책이 들어와서 1권을 중간에 끼워넣고 싶으면 그 뒤에 책들을 모조리 다 한칸씩 이동시켜야 된다. 

ArrayList는 이런 도서관 책장과 닮았다. 주요 특징은 다음과 같다.

동적으로 크기가 변경된다. 추가하거나 삭제하는 만큼 크기가 달라진다.

중간에 값을 추가하거나 값을 삭제하는 것이 느리다.

조회하는 속도가 빠르다.

ArrayList는 추가하는 만큼 동적으로 크기가 변경된다. 처음 생성되면 10개의 빈칸을 미리 확보를 한다. 그래서 하나씩 채우다가, 늘어나면 또 그만큼 빈칸을 확보하는 식이다. 그리고 만약 1000개의 데이터가 있는데 501번째 값을 추가하거나 삭제해야 된다고 하면 그만큼 다른 값들을 옮겨줘야 하기에 추가 및 삭제 처리속도가 느리다. 제일 끝의 값을 추가하거나 삭제하는건 괜찮다. 또한 조회할때는 '00번째' 라고 바로 접근할 수 있기 때문에 접근 조회가 빠르다. 

LinkedList : 내 이전과 다음 정보를 알고 있다

보물찾기를 할때를 생각해보자. 어느 지점에 가서 쪽지를 열어보면 '다음엔 어디로 가시오' 라고 적혀있다. LinkedList도 비슷하다. 각각의 아이템들이 이전과 다음에 대한 값을 참조하고 있다. 하지만 원하는 쪽지를 발견하기까지는 한번에 접근하긴 어렵고 다른 참조값들을 참조해야지만 도착할 수 있다. 즉, 한번에 조회하기가 어렵다. 그리고 만약, 중간에 보물을 추가하고 싶으면 이전값과 다음값만 참조값을 바꿔주면 된다. 즉, 추가 및 삭제가 용이하다.

LinkedList의 주요 특징은 다음과 같다.

동적으로 크기가 변경된다

중간에 값을 추가하거나 값을 삭제할때 빠르다.

조회하는 속도가 느리다.

메모리 사용량이 더 많다. ArrayList는 연속된 메모리 공간을 사용하지만, LinkedList는 각 노드가 별도의 메모리 공간을 사용하므로 더 많은 메모리를 사용한다.

조회를 자주 해야 한다면 ArrayList

값을 빈번하게 추가하거나 삭제할 일이 많다면 LinkedList

1년동안 학생의 수가 거의 동일한 학교 학생 리스트같으면 ArrayList가 더 적절할 것이다. 추가되거나 삭제되는 일은 거의 없기 때문이다. 하지만 만약 Todo 리스트같이 삭제나 추가가 빈번한 리스트는 LinkedList가 적합할 것이다.