[Java] 알고리즘 기초 : 배열과 리스트, 언제 무엇을 쓸까?

배열은 크기가 고정되고 접근이 빠르며, 리스트는 크기 변경과 삽입/삭제가 용이하다.

코딩 테스트에서 배열과 리스트 중 무엇을 선택해야 할까? 

 

이미지 생성 : 릴리스 AI

 

코딩 테스트에서 배열과 리스트는 가장 흔하게 사용되는 자료 구조이며, 문제 유형에 따라 적절히 선택하는 것이 중요하다. 

---

1. 배열(Array): 정해진 크기와 빠른 접근

 

배열은 메모리의 연속적인 공간에 데이터가 일렬로 배치되는 자료구조입니다. 한 번 생성하면 그 크기를 변경할 수 없는 '정적(Static)'인 특징을 가진다.

// 배열 선언 방식의 예
int[] arr = new int[5]; // 크기가 5인 배열 선언

 

주요 특징

• 빠른 접근 : 인덱스(Index)를 통해 데이터의 위치에 즉시 접근할 수 있습니다. (O(1))
  • 예를 들어, arr 배열에서 값 4에 접근하려면 인덱스 3을 사용하여 arr[3]으로 표현한다. 
• 고정된 크기 : 선언 시점에 크기를 정해야하며, 실행 도중 크기를 늘리거나 줄일 수 없다.
• 비효율적인 삽입/삭제: 중간에 값을 추가하거나 삭제하려면, 나머지 요소들의 위치를 모두 이동시켜야 하므로 비효율적이다 (O(n))
  • 예를 들어, 배열의 두 번째 자리에 있는 값을 삭제하려면 뒤에 있는 값들을 앞으로 한 칸씩 당겨야 한다. 
    
  • 값을 삽입할 때도 기존 데이터를 뒤로 밀어 공간을 확보해야 한다
• 구조가 간단하여 코딩 테스트에서 가장 많이 사용된다. 

 

Java 배열 선언 및 사용 코드

// 1. 크기를 지정하여 선언 (기본값 0으로 초기화됨)
int[] arr1 = new int[5];

// 2. 선언과 동시에 데이터 초기화 (크기는 자동으로 5가 됨)
int[] arr2 = {10, 20, 30, 40, 50};

// 3. 데이터 접근 및 수정
arr1[0] = 100;            // 0번 인덱스에 100 할당
int firstItem = arr2[0];  // 0번 인덱스의 값(10) 읽기

// 주의: 배열의 길이를 초과하는 인덱스에 접근하면 에러(ArrayIndexOutOfBoundsException) 발생
// arr1[5] = 60; // Error

---

2. 리스트(List): 유연한 크기와 편리한 편집

 

리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료 구조이다. 각 노드는 자신의 값(데이터)과 다음 노드를 가리키는 포인터로 구성된다. 

 

** 참고

자바에서는 List 인터페이스를 구현한 ArrayList를 가장 널리 사용한다.

ArrayList는 내부적으로 배열을 사용하지만, 공간이 꽉 차면 자동으로 더 큰 배열을 만들어 데이터를 복사하는 방식으로 가변적인 크기를 지원한다.

 

주요 특징

 

• 빠른 삽입 및 삭제:  중간에 데이터를 추가하거나 삭제할 때, 물리적인 데이터를 이동시킬 필요 없이 해당 위치 앞뒤 노드의 포인터(연결 고리)만 새로운 방향으로 바꿔주면 된다.(O(1))
• 느린 조회 속도: 데이터가 메모리상에 흩어져 있고 포인터로만 연결되어 있기 때문에, 인덱스를 통한 직접 접근이 불가능하다.
  • 특정 위치의 데이터를 찾으려면 항상 리스트의 처음(Head)부터 포인터를 따라 순차적으로 탐색해야 한다.(O(n))
• 가변적인 크기: 데이터가 추가될 때마다 메모리를 동적으로 할당하여 연결하므로, 선언 시점에 전체 크기를 미리 알 필요가 없다.
  • 선언 시 크기를 별도로 지정하지 않아도 되며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다. 
• 실제 코딩 테스트에서는 ArrayList나 LinkedList와 같이 기본적으로 제공되는 리스트를 주로 사용한다. 
  • 이러한 구현체들은 삽입, 삭제, 접근 등의 기능이 내부적으로 구현되어 있다. 
  • 리스트의 내부 동작 방식을 깊이 이해해야 하는 경우는 매우 어렵고 난이도가 높은 문제에 한정된다. 

 

Java 리스트 선언 및 사용 코드

import java.util.ArrayList;
import java.util.List;

// 1. 크기 지정 없이 동적 선언
List<Integer> arrayList = new ArrayList<>();

// 2. 데이터 추가 (끝에 추가) - 평균적으로 빠름
arrayList.add(10);
arrayList.add(20);

// 3. 특정 위치 삽입 및 삭제 - O(n) (데이터 이동 발생)
arrayList.add(1, 15); // 1번 위치에 15 삽입 (뒤로 한 칸씩 밀림)
arrayList.remove(0);  // 0번 위치 삭제 (앞으로 한 칸씩 당겨짐)

// 4. 데이터 조회 - O(1) 인덱스 기반의 빠른 접근
int target = arrayList.get(1);

 

 

---

3. 비교 요약과 선택 기준

연산	배열 (Array)	ArrayList (배열 기반 리스트)	LinkedList (연결 리스트)
조회 (Access)	O(1)	O(1)	O(n)
수정 (Update)	O(1)	O(1)	O(n)
삽입 (Insert)	O(n)	O(n)	O(1)
삭제 (Delete)	O(n)	O(n)	O(1)
크기 할당	고정 (Static)	동적 (Dynamic)	동적 (Dynamic)

 

배열은 다음과 같은 경우에 사용하는 것이 유리하다. 

• 데이터의 크기가 늘어나거나 줄어들지 않고 고정되어 있을 때 사용한다. 
• 데이터에 접근하는 경우가 많을 때 사용한다. 

 

리스트(ArrayList, LinkedList 등)는 다음과 같은 경우에 사용하는 것이 좋다. 

• 크기가 변하는 데이터를 다룰 때 사용한다. 
• 데이터의 삽입 및 삭제가 빈번하게 일어날 때 사용한다.

---

4. 마치며

최근 자바 언어를 새롭게 학습하기 시작했다.

 

그런데 본격적인 문법을 채 익히기도 전에 이틀 뒤, 급하게 코딩 테스트를 자바로 응시해야 하는 상황이 있었다.

 

기존에는 파이썬을 주력으로 알고리즘 스터디를 진행해 왔던 터라, 그동안 쌓아왔던 경험들을 바탕으로 문제에 접근했다.

 

하지만 결과는 처참했다. 로직의 문제가 아니라, 자바에서 '배열'과 '리스트'를 다루는 방법에 대한 이해 부족이 발목을 잡았다. 파이썬의 유연한 자료구조에만 익숙해져 있다 보니, 자바의 엄격한 타입과 메모리 구조 앞에서는 코드를 시작조차 하기 어려웠다.

 

이번 실패를 교훈 삼아 자바의 배열과 리스트를 다시 공부해보니, 데이터의 성격에 따라 어떤 자료구조를 선택해야 하는지 그 기준을 명확히 이해할 수 있었다.

 

앞으로는 파이썬으로 이미 풀어보았던 익숙한 알고리즘 문제들을 자바로 다시 구현해 볼 계획이다.

 

이러한 훈련을 반복하다 보면, 문제의 요구사항을 읽자마자 적절한 배열과 리스트를 떠올리는 감각이 자연스럽게 쌓이고 한 단계 더 성장할 수 있을 것이라 생각한다.

 

(참고 링크 - Github)

https://github.com/jung-jinyoung/java-algo-study

GitHub - jung-jinyoung/java-algo-study: Language : Java