Part 4. 밥벌이 자료구조의 시작입니다.
자료구조는 코딩 테스트뿐만 아니라, "이 상황에서 어떤 컬렉션을 써야 성능이 나올까?"를 판단하는 실무 감각의 척도입니다.
가장 기본이지만 의외로 많은 개발자가 "그냥 편해서" ArrayList만 쓰는 경우가 많습니다. 왜 LinkedList가 존재하는지, 두 녀석의 태생적 차이를 통해 확실하게 구분해 드립니다.
[자료구조] ArrayList vs LinkedList, 아직도 아무거나 쓰시나요?
"List면 다 똑같은 거 아닌가요?"
자바에서 List 인터페이스를 구현한 클래스는 많습니다. 하지만 우리는 습관적으로 이렇게 씁니다.
List<String> list = new ArrayList<>();왜 LinkedList는 잘 안 쓸까요? 아니, 애초에 LinkedList는 언제 써야 할까요?
이 둘의 차이를 모르면, 데이터가 수십만 개 쌓였을 때 프로그램 속도가 수백 배 차이 날 수 있습니다.
오늘은 자바 컬렉션 프레임워크(JCF)의 양대 산맥, 배열 기반 리스트와 연결 기반 리스트의 결정적 차이를 파헤쳐 봅니다.
1. ArrayList: "붙어 있어서 빠르다"
ArrayList는 이름 그대로 Array(배열)의 업그레이드 버전입니다.
- 구조: 메모리상에 데이터들이 연속적으로 다닥다닥 붙어 있습니다.
- 특징: 빈틈없이 채워져 있어서 인덱스(Index)로 관리합니다.
👍 장점: 조회(Search)가 빛의 속도다
데이터들이 순서대로 붙어있기 때문에 get(100)을 호출하면 계산 한 번으로 바로 100번째 위치를 찾아갑니다.
- 시간 복잡도:
O(1)(무조건 한 번에 찾음)
👎 단점: 중간에 끼어들기가 힘들다
이미 꽉 찬 지하철 의자(배열)를 생각해보세요.
중간에 한 명이 앉으려면, 그 뒤에 앉은 모든 사람이 엉덩이를 들고 한 칸씩 옆으로 이동해야 합니다.
- 중간 삽입/삭제: 데이터를 뒤로 밀거나 당기는 연산(Shifting)이 필요해서 느립니다.
- 시간 복잡도:
O(n)(데이터 개수만큼 이동)
2. LinkedList: "흩어져 있어서 유연하다"
LinkedList는 데이터들이 메모리 여기저기에 흩어져 있고, 서로를 줄(Link)로 연결하고 있습니다.
- 구조: Node(노드)라는 바구니에 '데이터'와 '다음 데이터의 주소'를 담고 있습니다.
- 특징: 물리적으로 붙어있지 않고 논리적으로 연결되어 있습니다.
👍 장점: 삽입/삭제가 너무 쉽다
중간에 데이터를 넣고 싶으면?
줄(참조)을 끊고 새 노드를 연결만 해주면 끝입니다. 뒤에 있는 데이터를 밀고 당길 필요가 없습니다.
- 삽입/삭제: 위치만 안다면 매우 빠릅니다.
O(1)
👎 단점: 조회(Search)가 느리다
"5번째 데이터 내놔"라고 하면?
ArrayList처럼 한 번에 못 갑니다. 첫 번째 노드부터 "다음... 그다음... 그다음..." 하면서 줄을 타고 5번 이동해야 합니다. (보물찾기랑 똑같습니다.)
- 조회: 데이터가 많을수록 오래 걸립니다.
O(n)
3. 한 눈에 보는 성능 비교 (면접용)
| 기능 | ArrayList (배열) | LinkedList (연결) | 승자 🏆 |
|---|---|---|---|
| 조회 (get) | O(1) | O(n) | ArrayList 압승 |
| 순차 추가 (add) | O(1) (공간 충분 시) | O(1) | 무승부 |
| 중간 삽입/삭제 | O(n) (밀어내기 발생) | O(1) (노드 연결만 변경) | LinkedList 압승 |
4. 실무에서는 뭘 써야 할까?
"99%의 상황에서 그냥 ArrayList 쓰세요."
이유가 뭘까요?
- 웹 개발은 조회가 많다: DB에서 데이터를 가져와서 뿌려주는(Read) 작업이 90%입니다.
- 메모리 효율:
LinkedList는 다음 주소를 저장해야 해서 메모리를 더 많이 먹습니다. - 캐시 지역성(Locality):
ArrayList는 데이터가 붙어있어서 CPU 캐시 효과를 잘 받지만,LinkedList는 흩어져 있어서 캐시 효율이 떨어집니다.
💡 그럼 LinkedList는 언제 써요?
- 데이터의 삽입/삭제가 빈번하게 일어나는 경우 (특히 앞/뒤가 아닌 중간에서).
- 알고리즘 문제 풀 때 큐(Queue)나 데크(Deque)를 구현해야 하는 경우.
5. 실전 면접 대비: 3초 요약
Q. ArrayList와 LinkedList의 차이를 설명해주세요.
A.
"데이터 접근 속도와 삽입/삭제 효율의 차이입니다.
ArrayList는 인덱스를 기반으로 하여 데이터 조회(Search)가O(1)로 매우 빠르지만, 중간에 데이터를 삽입하거나 삭제할 때는 데이터를 이동시켜야 하므로O(n)이 걸립니다.
반면 LinkedList는 노드 간의 연결로 이루어져 있어 삽입/삭제는 참조값만 변경하면 되므로 빠르지만, 특정 데이터를 찾으려면 처음부터 순회해야 하므로 조회가O(n)으로 느립니다."
🚀 다음 글 예고
"배열은 꽉 차면 에러가 나는데, 자바의 Map은 어떻게 데이터를 무한정 넣을까요?"
자바 개발자가 가장 사랑하는 자료구조이자, 면접 질문 난이도 최상위권인 '해시맵(HashMap)'.
키(Key)와 값(Value)이 저장되는 마법 같은 원리를 아주 쉽게 뜯어보겠습니다.
Next Topic: [자료구조] HashMap의 동작 원리,
equals()와hashCode()의 관계
