컬렉션 프레임워크 - 배열 리스트 VS 연결 리스트
이번 글에서 배열 리스트와 연결 리스트를 정리 및 비교해 보려고 한다.
그 전에 자료구조의 기본이 되는 배열을 간단히 살펴보고 가자!
배열
배열이란?
동일한 타입의 값들을 하나의 묶음으로 저장한 자료 구조이다.
int[] r = new int[5];배열을 처음 선언할 때 크기를 지정하는 정적 할당의 방식으로 이후 크기를 변경할 수 없다.
이러한 정적 할당으로 크기를 설정하는 배열은 데이터의 크기가 정해져 있어 메모리 관리에 용이하다.
뿐만 아니라 배열은 메모리 속에 연속적으로 나열되어 있어 index를 통해 데이터의 입력, 변경, 조회를 한 번의 계산으로 수행할 수 있다는 장점이 있다.
배열 index 사용 예시
배열의 상황
- 4byte를 차지하는 int 타입 데이터들의 묶음
- 100번지(예시)부터 나열된 상태
여기서 arr[2]에 위치한 데이터를 조회한다면 간단한 공식으로 한 번에 접근할 수 있다.
공식 : 배열의 시작 참조 + (데이터의 크기 * index의 위치) => 100(번지) + (4byte(int) * 2) = 108 (번지)
배열의 상황과 위의 계산을 통해 메모리 속 108번지 속 값이 arr[2]의 값을 의미한다는 것을 확인할 수 있다.
이러한 과정으로 배열은 index를 통해 값을 입력, 변경, 조회하는 것을 빠르게 수행할 수 있다.
다만 배열에 들어있는 데이터를 찾는 검색은 배열 속 데이터를 하나하나 비교해야하기 때문에 평균적으로 배열의 크기에 비례한 수행 시간이 걸린다.
또한 배열의 특정 위치에 데이터를 추가할 때 배열의 크기에 비례한 오랜 수행 시간 뿐만 아니라 배열의 마지막 위치에 추가하는 것이 아니라면 특정 위치의 뒤쪽에 위치한 데이터를 한 칸씩 다시 뒤로 이동시키는 불편함을 감수해야 한다.
이들을 빅오(O)표기법으로 표시하면 다음과 같다.
index를 통한 배열의 입력, 변경, 조회
-> O(1) : 상수 시간 - 입력 데이터의 크기와 관계없이 알고리즘의 실행시간이 일정함
배열의 검색, 배열 속 특정 위치에 데이터 추가
-> O(n) : 선형 시간 - 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가함
따라서 index를 활용할 수 있으면 최대한 활용하는 것이 효율적이다.
배열의 한계
이렇게 index를 사용할 때 효율이 가장 좋은 배열이지만 데이터를 추가할 때 위치에 따라 데이터를 모두 이동시켜야 하는 불편함이 있다. 하지만 이것이 배열이 가지는 한계의 전부가 아니다.
배열의 가장 큰 한계는 배열을 선언할 때 미리 배열의 크기가 정해진다는 것이다. 이러한 배열의 특성은 배열의 크기를 크게 설정했을 때는 메모리의 낭비를 초래하고, 작게 설정했을 때는 공간의 부족 문제를 초래한다.
정리하자면 배열은 데이터를 추가할 때의 불편하고 배열의 크기를 동적으로 변경할 수 없다.
이러한 단점들은 List라는 자료구조를 활용함으로써 해결할 수 있다.
List는 배열과 같이 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다는 점에서 차이를 가진다.
따라서 배열을 활용한 List 형태의 자료 구조를 통해 기존 배열의 한계를 보완해 볼 수 있다.
ArrayList(배열 리스트)
배열 리스트의 특징을 살펴보면 다음과 같다.
- 연속적인 데이터의 리스트 (중간에 빈 공간 허용 x)
- ArrayList 내부적으로 Object[] 배열을 사용하여 데이터를 저장
- 배열을 이용함으로써 index를 통해 데이터에 대한 빠른 접근이 가능
- 정적 할당으로 크기가 고정된 배열과 달리 데이터의 양에 따라 크기를 가변적으로 조절이 가능함 => 동적 할당
- 이에 대한 과정으로 배열 공간이 가득 찰 때 배열을 복사하여 공간을 확장시키기 때문에 지연이 발생
- 데이터를 리스트 중간에 삽입/삭제 할 경우, 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문에 삽입/삭제 동작은 느림
이러한 배열리스트는 배열과 달리 크기를 가변적으로 조절할 수 있지만 메모리에 연속적으로 나열되어있지 않고 주소로 연결되어있는 형태이기 때문에 index를 통한 색인(접근)속도가 배열보다는 느리다.
이외에 배열을 사용하기 때문에 배열이 갖는 문제점도 배열리스트에서 단점으로 부각된다.
배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.
배열은 배열의 크기를 미리 확보해야 하는데 데이터가 얼마나 추가될지 예측할 수 있는 상황에서 데이터가 없는 나머지 공간은 사용되지 않고 낭비된다고 볼 수 있다.
또한 배열의 중간에 데이터를 추가할 때 데이터가 들어갈 공간을 확보하기 위해 기존 데이터들을 오른쪽 공간으로 이동시켜야 하며 삭제할 때는 데이터가 지워진 빈 공간을 채우기 위해 왼쪽으로 이동시켜야 한다.
이렇게 데이터를 이동시키는 행위는 성능에 부정적인 영향을 미친다.
만약 메모리를 낭비하지 않고 필요한 만큼의 공간만 사용하고 싶거나 데이터의 추가 및 삭제로 인해 비효율적인 수행 과정을 겪고 싶지 않다면 노드를 사용한 자료구조를 선택하는 것도 하나의 방법이다.
LinkedList (연결 리스트)
ArrayList와 같이 index로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다.
ArrayList는 내부적으로 배열을 이용하여 메서드로 조작이 가능한 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.
public class Node {
Object item; // 데이터를 저장
Node next; // 다음 노드 주소를 저장
}
이러한 LinkedList는 공간의 제약이 없고 자료의 삽입과 삭제가 용이하며 이 과정에서의 자료 이동이 불필요하다는 장점이 있다.
하지만 데이터들을 불연속적인 단위로 저장하여 노드들에 접근하는데 긴 지연시간을 소비해 성능 측면에서 ArrayList에 비해 아쉬운 모습을 가진다.
배열리스트 VS 연결리스트
| 배열리스트 | 연결리스트 | |
| 컬렉션 구성 | 배열을 사용 | 노드를 연결 |
| 데이터 접근 시간 | 모든 데이터 상수 시간O(1) 접근 | 위치에 따른 이동시간 발생 |
| 삽입 / 삭제 시간 | 삽입 / 삭제 자체는 상수 시간 | |
| 삽입/삭제 시 데이터 이동이 필요한 경우 추가 시간 발생 |
삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생 | |
| 리사이징 필요 | 공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생 | - |
| 데이터 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | |
| CPU Cache | 캐시 이점 활용 | - |
🧱 자바 ArrayList 구조 & 사용법 정리
ArrayList 컬렉션 자바의 컬렉션 프레임워크를 접한다면 가장 먼저 배우는 컬렉션이 ArrayList 일 것이다. 자료구조(Data Structure) 이라고 해서 무언가 방대하게 느껴져 접근이 어려울 것 처럼 느끼겠지
inpa.tistory.com
🧱 자바 LinkedList 구조 & 사용법 - 정복하기
LinkedList 컬렉션 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하
inpa.tistory.com
🧱 ArrayList vs LinkedList 특징 & 성능 비교
LinkedList vs ArrayList 특징 비교 LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성한 이유는 ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해
inpa.tistory.com