인프런 커뮤니티 질문&답변

안녕하세요?
자바에서 ArrayList 와 LinkedList 의 차이는 이렇습니다.

(1) ArrayList
ArrayList 는 크기 조절이 가능한 배열로 구현되어 있습니다. 공원 벤치나 공항의 의자들처럼 쭉 나열된 형태로 연속적인 메모리 공간에 위치하고 있으므로 인덱스 기반의 빠른 무작위 접근(Random Access)이 가능합니다. 가령 아주 긴 의자에 10명이 붙어서 앉아 있을 때 3번, 5번 위치에 앉은 사람을 빠르고 쉽게 찾을 수 있죠.
하지만 중간에 어떤 데이터를 삽입하거나 삭제하면 시간이 조금 소요됩니다. 앞의 긴 의자에서 10명이 앉아 있었는데 3번 위치의 사람이 빠지게 되면 4번 이후의 모든 사람들이 한 칸씩 땡겨와야 한다고 이해하시면 됩니다. 또는 3번 위치에 새로운 사람이 와서 앉으려고 한다면 2번을 포함한 이후 모든 사람들이 일어서서 한 칸씩 땡겨야 하지요.

(2) LinkedList
LinkedList 는 이중 연결 리스트로 구현되어 있습니다. 이중 연결이란 말 그대로 연결이 이중으로 되어 있다는 것인데, 어떤 요소가 있으면 그 요소의 이전 항목, 그리고 다음 항목으로 각각 선이 이어져 있다고 보시면 됩니다. 그래서 3번 항목이 있으면 3번 항목으로부터 next 선을 따라가면 4번이 나오고, prev 선을 따라가면 2번이 나오게 됩니다.
사람 10명이 순서대로 손을 잡고 서 있다고 생각해볼까요? 가령 3번 사람은 2번과 4번 사람의 손을 잡고 있습니다. 그래서 3번 사람을 통해 2번과 4번 사람도 접근할 수 있게 됩니다. 이때 3번과 4번 사이에 A 라는 사람이 비집고 들어온다면 어떻게 될까요? 그냥 3번과 4번이 잠깐 손을 놓았다가 새롭게 들어온 A 와 각각 손을 잡으면 됩니다. 3번과 4번을 제외한 다른 사람들은 굳이 이동하거나 손을 놓거나 할 필요가 없게 되지요. 이처럼 중간에 새로운 데이터를 삽입하거나 삭제할 때 아주 빠르다는 장점이 있습니다.
하지만 요소를 찾을 때, 가령 3번, 5번 사람을 찾을 때 ArrayList 와 같이 인덱스로 바로 찾을 수는 없고 연결 리스트의 시작(또는 끝) 부터 시작해서 그 사람의 손을 따라 다음 사람, 또 다음 사람, 또 다음... 이렇게 순차접근(Sequential Access) 을 통해 찾아야 하기 때문에 탐색 속도가 느리다는 단점이 있습니다. 마치 얽히고 얽힌 실타래를 풀려면 실의 시작이나 끝을 찾아서 하나씩 따라가며 풀어야 하는 것처럼 말이죠.

📌 정리하자면,
ArrayList 는 데이터를 조회하는 작업이 많은 경우에 적합합니다.
LinkedList 는 데이터 삽입/삭제 작업이 많은 경우에 적합합니다.

🔥 현실적으로,
대부분의 경우 ArrayList 를 사용하시면 크게 문제는 없습니다. '어떤 것을 쓰면 좋을지 잘 모르겠다' 하시는 경우 큰 고민하지 마시고 ArrayList 의 사용을 권장드립니다.

LinkedList 를 만드신 분이 트위터에 남긴 글을 인용하며 마칩니다 😊
감사합니다.

출처 : https://twitter.com/joshbloch/status/583813919019573248