Java Collection
Java는 개발자들이 다양한 자료구조를 사용하게 할 수 있도록 Collection 프레임워크를 지원한다. 이 프레임워크는 데이터를 저장하고 다루는 방식을 추상화하여, 상황에 맞는 자료구조를 손쉽게 선택할 수 있도록 도와준다.
그 중에서도 List는 순서가 있는 데이터 저장에 적합하며, 실무에서 가장 자주 사용되는 컬렉션 중 하나다.
Java에서는 대표적으로 ArrayList와 LinkedList가 List 인터페이스를 구현하고 있으며, 기능은 유사하지만 내부 구조와 성능 특성은 크게 다르다.
ArrayList란?
ArrayList는 List 인터페이스를 상속받은 클래스이다. int[], string[] 같이 정적 배열과는 다르게 크기가 변할 수 있다.
내부적으로 Object[] 배열을 사용해서 데이터를 저장한다. 원래 기본값은 10개의 데이터 칸을 가지고 있으며, 만약 더 삽입을 하게되어 자리가 부족할 경우 배열을 복사하여 1.5배를 늘려 사용한다.
그럼 왜 Object[]를 사용하지 않고 ArrayList를 사용하는가?
- Object[]는 정적 배열이며, 크기가 정해져 있어 더 데이터를 삽입할 경우 문제가 생긴다. ArrayList는 자동으로 크기를 확장시켜 줄 수 있다.
- ArrayList<>는 제네릭(Generic)을 지원하기 때문에 특정 타입의 객체를 지정해서 저장해야 해서 따로 형변환이 필요하지 않다.
- get(int index), add(int index), remove(int index) 같이 여러가지 기능을 사용할 수 있다.
LinkedList란?
Java의 LinkedList는 노드(Node)들이 서로 연결되어 있는 구조의 자료구조로, List와 Deque의 특성을 모두 가지고 있다. 보통 연결리스트를 linkedlist라고 하지만 Java에서 지원하는 LinkedList는 그 중에서 이중연결리스트를 지원한다.
기존 배열 기반 자료구조는 크기를 미리 지정해야 하기 때문에, 남는 공간이 생기면 메모리 낭비가 발생할 수 있다.
이와 달리 LinkedList는 필요한 만큼의 데이터를 순차적으로 연결해 저장하기 때문에, 메모리 공간을 보다 유동적으로 활용할 수 있다.
내부 구조
- 각 데이터는 Node 객체로 구성되어 있으며, 각각 데이터(data)와 이전/다음 노드에 대한 참조(prev, next)를 가진다.
- Java의 LinkedList는 이중 연결 리스트로 구현되어 있어 양방향 탐색이 가능하다.
ArrayList와 LinkedList의 차이는 무엇인가?
두 자료구조 모두 List 인터페이스를 구현하고 있지만, 내부 구조와 연산 성능, 사용 목적이 다르다. 아래 표를 통해 주요 차이점을 비교할 수 있다
| 항목 | ArrayList | LinkedList |
| 내부 구조 | 동적 배열 | 이중 연결 리스트 |
| 메모리 구조 | 연속적인 공간에 저장 | 비연속적인 노드를 참조로 연결 |
| 인덱스 접근 | O(1) (빠름) | O(n) (느림) |
| 삽입/삭제 (중간) | O(n) (뒤 요소들 이동 필요) | O(1) (참조만 변경) |
| 삽입/삭제 (앞/뒤) | 앞: 느림 / 뒤: 빠름 | 앞/뒤 모두 빠름 (addFirst, addLast) |
| 메모리 사용 | 상대적으로 효율적 | 노드마다 포인터 추가 저장으로 오버헤드 발생 |
언제 어떤 리스트를 써야 할까?
| 상황추천 | 자료구조 | 이유 |
| 인덱스를 자주 사용해 접근할 경우 | ArrayList | 배열 기반이므로 랜덤 접근 속도가 빠름 |
| 중간에 데이터를 자주 삽입/삭제할 경우 | LinkedList | 노드의 참조만 변경하면 되므로 효율적 |
| 데이터 추가/삭제는 거의 없고 조회 위주일 경우 | ArrayList | 전체적으로 더 가볍고 빠름 |
| 큐 또는 덱(Deque) 형태로 사용해야 할 경우 | LinkedList | addFirst, removeLast 등 Deque 기능 지원 |
'자료구조' 카테고리의 다른 글
| [자료구조] (5) Deque(덱)이란 무엇인가? (0) | 2025.04.27 |
|---|---|
| [자료구조] (4) Stack 두 개로 Queue 구현하기 (0) | 2025.04.25 |
| [자료구조] (3) 해시테이블(Hash Table)이란? (0) | 2025.04.25 |
| [자료구조] (2) 레드블랙 트리(Red-Black Tree)와 이진 트리(Binary Tree)의 차이점 (0) | 2025.04.24 |