2026.02.22 - [Java] - [Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해
[Java] 컬렉션 프레임워크 - List(ArrayList, LinkedList)의 이해
[Java] 시간복잡도와 빅 오(Big-O) 표기의 이해알고리즘(Algorithm)이란?알고리즘이란 어떠한 문제를 해결하기 위한 단계적인 절차 또는 방법입니다. 저희는 단순히 문제를 해결하는 것만이 아닌, 더
min-soon.tistory.com
배열과 리스트
자료구조에서 데이터를 저장하는 방식에는 여러 가지가 있습니다.
그 중에서도 가장 기본적인 구조가 배열(Array)과 리스트(List) 입니다.
두 자료 구조는 데이터를 저장한다는 공통점이 있지만, 데이터를 저장하고 접근하는 방식에서 큰 차이가 있습니다.
배열(Array)
배열은 메모리의 연속된 공간에 데이터를 저장하는 자료 구조 입니다.
배열의 각 데이터는 인덱스(index)를 통해 접근할 수 있으며, 하나의 배열에는 같은 자료형의 데이터만 저장할 수 있습니다.

배열의 특징
| 특징 | 시간 복잡도 | 설명 |
| 인덱스를 이용한 빠른 접근 | O(1) | arr[i] 등을 이용하여 바로 값 접근 가능 |
| 삽입/삭제의 어려움 | O(n) | 값의 삽입 삭제에는 뒤에 있는 데이터를 이동 과정이 필요해서 느림 |
| 크기 고정 | 한 번 선언된 배열의 크기는 변경 불가 |
✔ 즉, 배열은 인덱스를 통한 빠른 접근이 가능하지만 삽입 및 삭제는 느린 자료 구조
배열의 삽입 및 삭제 과정



리스트(List)
리스트는 노드(Node)라는 단위로 데이터를 저장하는 자료 구조 입니다.
각 노드는 다음 두 가지 정보를 가지고 있습니다.
✔ 노드(Node) : 본인의 데이터 + 다음 노드를 가리키는 포인터
✔ 포인터 : 어떤 데이터를 직접 저장하는 것이 아닌, 그 데이터가 저장된 위치를 기억하는 값
*마지막 노드는 더 이상 연결된 노드가 없기에 null값

리스트의 특징
| 특징 | 시간 복잡도 | 설명 |
| 순차 접근 구조 | O(n) | 인덱스가 없기에, 데이터에 접근하려면 Head(첫 번째 노드)부터 순차적으로 탐색 |
| 빠른 삽입/삭제 | O(1) | 노드 간의 연결만 변경하면 되므로 삽입과 삭제가 매우 빠름 |
| 동적 크기 | 배열과 달리 크기를 미리 정할 필요 없음. | |
| 추가 메모리 사용 | 각 노드는 포인터를 함께 저장해야 하므로, 배열보다 더 많은 메모리 사용 *상대적으로 더 복잡한 구조 |
✔ 즉, 리스트는 연결 구조를 통해 삽입/삭제는 빠르지만, 조회는 느린 자료 구조
리스트와 배열의 차이
✔ 배열 : 데이터를 연속된 메모리 공간에 저장
↳ 중간에 값을 추가하거나 삭제할 경우 기존 데이터를 이동해야 하는 비용 발생
✔ 리스트 : 데이터를 노드로 나누고 연결
↳ 노드 간의 연결(포인터)만 변경하면 되기에 데이터 이동 없이 빠른 삽입/삭제 가능
구간 합(Prefix Sum)
구간 합은 배열에서 특정 구간의 합을 빠르게 구하기 위해 사용하는 알고리즘입니다.
일반적으로 배열의 합을 구할 때는 반복문을 사용하여 구하는데, 이 경우 시간 복잡도는 O(n)이고 이 연산을 여러번 수행하면 비효율적입니다.
이 문제를 해결하기 위한 것이 바로 구간 합 알고리즘입니다.
이를 활용하기 위해서는 먼저 합 배열을 이용해야 합니다.
✔️ 핵심 : 미리 누적된 합(합 배열)을 만들어 두고, 필요할 때 빠르게 계산한다.
이를 구간 합 알고리즘이라고 하는데, 이를 활용하기 위해서는 먼저 합 배열을 이용해야 합니다.
합 배열(Prefix Sum Array)
배열 A가 있을때는 합 배열 S는 다음과 같이 정의 합니다.
✔️합 배열 S : A[0] ~ A[i] 까지의 합
S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]
✔️합 배열 S를 만드는 공식
S[i] = S[i - 1] + A[i]

구간 합 공식
✔️구간 합 공식
S[j] - S[i - 1]
✔️ 합 배열 S는 0번부터 해당 인덱스까지의 누적 합을 의미합니다.
ex) S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
예시 문제 풀이
예시 문제를 통해 과정을 살펴보겠습니다.
❓ A 배열의 1 ~ 3 구간의 합 구하기
A = [3, 6, 7, 10, 14]
1. S 배열 생성
✔️ S 배열 생성(위 합배열 공식 이용)
S = [3, 9, 16, 26, 40]
2. 구간 합 확인
✔️ 구간 합 확인
A[1] + A[2] + A[3]
= 6 + 7 + 10
= 23
✔️ 구간 합 공식 사용
S[j] - S[i - 1]
= 26 - 3
= 23
공식을 사용해도 값이 동일한 것을 확인할 수 있습니다.
3. 과정 설명
✔️ 합배열 S는 0번부터 지정 인덱스까지의 누적 합
S[4] = A[0] + A[1] + A[2] + A[3] + A[4]
S[1] = A[0] + A[1]
✔️ 우리가 구하고 싶은 값은 1 ~ 3의 구간으로 S배열에는 필요 없는 값(S[0])이 포함되어 있음.
✔️ 합배열 공식 : S[j] - S[i - 1]
S[j] = A[0] ~ A[j]
S[i - 1] = A[0] ~ A[i - 1]
A = [3, 6, 7, 10, 14]
S = [3, 9, 16, 26, 40]

💡 정리
전체 합 : (0 ~ j)
앞 부분 : 앞 부분(0 ~ i - 1)
원하는 구간 : (i ~ j)
✔ 즉, 앞에서부터 누적된 합에서필요없는 앞부분만 뺴면 원하는 구간 합이 나옴
