4.3 리스트¶
리스트(list)는 순서가 있는 원소의 모음을 나타내는 추상적인 자료 구조 개념이다. 원소 접근, 수정, 추가, 삭제, 순회 등의 연산을 지원하며, 사용자가 용량 제한을 신경 쓰지 않아도 된다. 리스트는 연결 리스트나 배열로 구현할 수 있다.
- 연결 리스트는 원소의 삽입, 삭제, 탐색, 갱신을 지원하고 유연하게 용량을 늘릴 수 있으므로 자연스럽게 리스트로 볼 수 있다.
- 배열도 원소의 삽입, 삭제, 탐색, 갱신을 지원하지만 길이를 바꿀 수 없으므로 길이가 제한된 리스트로 볼 수 있다.
배열로 리스트를 구현하면 길이를 바꿀 수 없다는 특성 때문에 실용성이 낮아진다. 보통 저장할 데이터 양을 미리 알 수 없어 적절한 길이를 정하기 어렵기 때문이다. 길이가 너무 짧으면 필요를 충족하지 못하고, 너무 길면 메모리 공간을 낭비한다.
이 문제는 동적 배열(dynamic array)로 리스트를 구현하여 해결할 수 있다. 동적 배열은 배열의 장점을 이어받으면서도 프로그램 실행 중에 용량을 동적으로 늘릴 수 있다.
실제로 많은 프로그래밍 언어의 표준 라이브러리가 제공하는 리스트는 동적 배열로 구현된다. Python의 list, Java의 ArrayList, C++의 vector, C#의 List 등이 그 예다. 이후 설명에서는 ‘리스트’와 ‘동적 배열’을 같은 개념으로 다룬다.
4.3.1 리스트의 기본 연산¶
1. 리스트 초기화¶
보통 ‘초깃값 없음’과 ‘초깃값 지정’의 두 가지 초기화 방식을 사용한다.
코드 시각화
2. 원소 접근¶
리스트는 본질적으로 배열이므로 원소에 접근하고 갱신하는 데 \(O(1)\) 시간이 걸려 매우 효율적이다.
코드 시각화
3. 원소 삽입과 삭제¶
배열과 달리 리스트는 원소를 자유롭게 추가하고 삭제할 수 있다. 끝에 원소를 추가하는 시간 복잡도는 \(O(1)\)이지만, 삽입과 삭제의 효율은 배열과 같아 시간 복잡도가 \(O(n)\)이다.
list_test.go
/* 리스트 비우기 */
nums = nil
/* 끝에 원소 추가 */
nums = append(nums, 1)
nums = append(nums, 3)
nums = append(nums, 2)
nums = append(nums, 5)
nums = append(nums, 4)
/* 중간에 원소 삽입 */
nums = append(nums[:3], append([]int{6}, nums[3:]...)...) // 인덱스 3에 숫자 6 삽입
/* 원소 삭제 */
nums = append(nums[:3], nums[4:]...) // 인덱스 3의 원소 삭제
코드 시각화
4. 리스트 순회¶
배열처럼 리스트도 인덱스로 순회하거나 각 원소를 직접 순회할 수 있다.
코드 시각화
5. 리스트 연결¶
새 리스트 nums1이 주어지면 기존 리스트의 끝에 이어 붙일 수 있다.
코드 시각화
6. 리스트 정렬¶
리스트를 정렬하면 배열 관련 알고리즘 문제에 자주 등장하는 ‘이진 탐색’과 ‘투 포인터’ 알고리즘을 사용할 수 있다.
코드 시각화
4.3.2 리스트 구현¶
Java, C++, Python 등 많은 프로그래밍 언어는 리스트를 내장하고 있다. 이들의 구현은 비교적 복잡하며 초기 용량, 확장 배수 등의 매개변수도 정교하게 설정되어 있다. 관심 있는 독자는 소스 코드를 살펴보며 학습할 수 있다.
리스트의 작동 원리를 더 깊이 이해하기 위해 간단한 리스트를 구현해 보자. 핵심 설계는 다음 세 가지다.
- 초기 용량: 배열의 초기 용량을 적절히 선택한다. 이 예에서는 10을 초기 용량으로 정한다.
- 개수 기록: 현재 원소 수를 기록하는 변수
size를 선언하고, 삽입과 삭제에 따라 즉시 갱신한다. 이 변수를 통해 리스트의 끝을 찾고 용량 확장이 필요한지 판단할 수 있다. - 용량 확장 방식: 원소를 삽입할 때 리스트가 가득 찼으면 용량을 늘려야 한다. 확장 배수에 따라 더 큰 배열을 만든 뒤 기존 원소를 모두 차례로 옮긴다. 이 예에서는 매번 배열 용량을 이전의 2배로 늘린다.
my_list.py
class MyList:
"""리스트 클래스"""
def __init__(self):
"""생성자"""
self._capacity: int = 10 # 리스트 용량
self._arr: list[int] = [0] * self._capacity # 배열(리스트 원소 저장)
self._size: int = 0 # 리스트 길이(현재 원소 개수)
self._extend_ratio: int = 2 # 리스트의 용량을 확장할 때마다 적용하는 배수
def size(self) -> int:
"""리스트 길이(현재 원소 개수) 반환"""
return self._size
def capacity(self) -> int:
"""리스트 용량 반환"""
return self._capacity
def get(self, index: int) -> int:
"""원소 접근"""
# 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if index < 0 or index >= self._size:
raise IndexError("인덱스가 범위를 벗어났다")
return self._arr[index]
def set(self, num: int, index: int):
"""원소 갱신"""
if index < 0 or index >= self._size:
raise IndexError("인덱스가 범위를 벗어났다")
self._arr[index] = num
def add(self, num: int):
"""맨 뒤에 원소 추가"""
# 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if self.size() == self.capacity():
self.extend_capacity()
self._arr[self._size] = num
self._size += 1
def insert(self, num: int, index: int):
"""중간에 원소 삽입"""
if index < 0 or index >= self._size:
raise IndexError("인덱스가 범위를 벗어났다")
# 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if self._size == self.capacity():
self.extend_capacity()
# 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for j in range(self._size - 1, index - 1, -1):
self._arr[j + 1] = self._arr[j]
self._arr[index] = num
# 원소 개수를 갱신한다
self._size += 1
def remove(self, index: int) -> int:
"""원소 삭제"""
if index < 0 or index >= self._size:
raise IndexError("인덱스가 범위를 벗어났다")
num = self._arr[index]
# 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for j in range(index, self._size - 1):
self._arr[j] = self._arr[j + 1]
# 원소 개수를 갱신한다
self._size -= 1
# 삭제한 원소를 반환한다
return num
def extend_capacity(self):
"""리스트 용량 확장"""
# 원래 배열 길이의 _extend_ratio 배인 새 배열을 만들고 원래 배열을 새 배열에 복사한다
self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
# 리스트 용량을 갱신한다
self._capacity = len(self._arr)
def to_array(self) -> list[int]:
"""유효한 길이만큼의 리스트 반환"""
return self._arr[: self._size]
my_list.cpp
/* 리스트 클래스 */
class MyList {
private:
int *arr; // 배열(리스트 원소 저장)
int arrCapacity = 10; // 리스트 용량
int arrSize = 0; // 리스트 길이(현재 원소 개수)
int extendRatio = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
public:
/* 생성자 */
MyList() {
arr = new int[arrCapacity];
}
/* 소멸자 */
~MyList() {
delete[] arr;
}
/* 리스트 길이(현재 원소 개수) 반환*/
int size() {
return arrSize;
}
/* 리스트 용량 반환 */
int capacity() {
return arrCapacity;
}
/* 원소 접근 */
int get(int index) {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= size())
throw out_of_range("인덱스가 범위를 벗어났다");
return arr[index];
}
/* 원소 갱신 */
void set(int index, int num) {
if (index < 0 || index >= size())
throw out_of_range("인덱스가 범위를 벗어났다");
arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
void add(int num) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size() == capacity())
extendCapacity();
arr[size()] = num;
// 원소 개수를 갱신한다
arrSize++;
}
/* 중간에 원소 삽입 */
void insert(int index, int num) {
if (index < 0 || index >= size())
throw out_of_range("인덱스가 범위를 벗어났다");
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size() == capacity())
extendCapacity();
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (int j = size() - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = num;
// 원소 개수를 갱신한다
arrSize++;
}
/* 원소 삭제 */
int remove(int index) {
if (index < 0 || index >= size())
throw out_of_range("인덱스가 범위를 벗어났다");
int num = arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (int j = index; j < size() - 1; j++) {
arr[j] = arr[j + 1];
}
// 원소 개수를 갱신한다
arrSize--;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
void extendCapacity() {
// 길이가 기존 배열의 extendRatio배인 새 배열 생성
int newCapacity = capacity() * extendRatio;
int *tmp = arr;
arr = new int[newCapacity];
// 원래 배열의 모든 원소를 새 배열에 복사한다
for (int i = 0; i < size(); i++) {
arr[i] = tmp[i];
}
// 메모리 해제
delete[] tmp;
arrCapacity = newCapacity;
}
/* 출력을 위해 리스트를 Vector로 변환 */
vector<int> toVector() {
// 유효한 길이 범위 안의 리스트 원소만 변환한다
vector<int> vec(size());
for (int i = 0; i < size(); i++) {
vec[i] = arr[i];
}
return vec;
}
};
my_list.java
/* 리스트 클래스 */
class MyList {
private int[] arr; // 배열(리스트 원소 저장)
private int capacity = 10; // 리스트 용량
private int size = 0; // 리스트 길이(현재 원소 개수)
private int extendRatio = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
public MyList() {
arr = new int[capacity];
}
/* 리스트 길이(현재 원소 개수) 반환 */
public int size() {
return size;
}
/* 리스트 용량 반환 */
public int capacity() {
return capacity;
}
/* 원소 접근 */
public int get(int index) {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났다");
return arr[index];
}
/* 원소 갱신 */
public void set(int index, int num) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났다");
arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
public void add(int num) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size == capacity())
extendCapacity();
arr[size] = num;
// 원소 개수를 갱신한다
size++;
}
/* 중간에 원소 삽입 */
public void insert(int index, int num) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났다");
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size == capacity())
extendCapacity();
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (int j = size - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = num;
// 원소 개수를 갱신한다
size++;
}
/* 원소 삭제 */
public int remove(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("인덱스가 범위를 벗어났다");
int num = arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (int j = index; j < size - 1; j++) {
arr[j] = arr[j + 1];
}
// 원소 개수를 갱신한다
size--;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
public void extendCapacity() {
// 길이가 원래 배열의 extendRatio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
arr = Arrays.copyOf(arr, capacity() * extendRatio);
// 리스트 용량을 갱신한다
capacity = arr.length;
}
/* 리스트를 배열로 변환 */
public int[] toArray() {
int size = size();
// 유효한 길이 범위 안의 리스트 원소만 변환한다
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = get(i);
}
return arr;
}
}
my_list.cs
/* 리스트 클래스 */
class MyList {
private int[] arr; // 배열(리스트 원소 저장)
private int arrCapacity = 10; // 리스트 용량
private int arrSize = 0; // 리스트 길이(현재 원소 개수)
private readonly int extendRatio = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
public MyList() {
arr = new int[arrCapacity];
}
/* 리스트 길이(현재 원소 개수) 반환*/
public int Size() {
return arrSize;
}
/* 리스트 용량 반환 */
public int Capacity() {
return arrCapacity;
}
/* 원소 접근 */
public int Get(int index) {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= arrSize)
throw new IndexOutOfRangeException("인덱스가 범위를 벗어났다");
return arr[index];
}
/* 원소 갱신 */
public void Set(int index, int num) {
if (index < 0 || index >= arrSize)
throw new IndexOutOfRangeException("인덱스가 범위를 벗어났다");
arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
public void Add(int num) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (arrSize == arrCapacity)
ExtendCapacity();
arr[arrSize] = num;
// 원소 개수를 갱신한다
arrSize++;
}
/* 중간에 원소 삽입 */
public void Insert(int index, int num) {
if (index < 0 || index >= arrSize)
throw new IndexOutOfRangeException("인덱스가 범위를 벗어났다");
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (arrSize == arrCapacity)
ExtendCapacity();
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (int j = arrSize - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = num;
// 원소 개수를 갱신한다
arrSize++;
}
/* 원소 삭제 */
public int Remove(int index) {
if (index < 0 || index >= arrSize)
throw new IndexOutOfRangeException("인덱스가 범위를 벗어났다");
int num = arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (int j = index; j < arrSize - 1; j++) {
arr[j] = arr[j + 1];
}
// 원소 개수를 갱신한다
arrSize--;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
public void ExtendCapacity() {
// 길이가 arrCapacity * extendRatio인 배열을 만들고 기존 배열을 새 배열에 복사
Array.Resize(ref arr, arrCapacity * extendRatio);
// 리스트 용량을 갱신한다
arrCapacity = arr.Length;
}
/* 리스트를 배열로 변환 */
public int[] ToArray() {
// 유효한 길이 범위 안의 리스트 원소만 변환한다
int[] arr = new int[arrSize];
for (int i = 0; i < arrSize; i++) {
arr[i] = Get(i);
}
return arr;
}
}
my_list.go
/* 리스트 클래스 */
type myList struct {
arrCapacity int
arr []int
arrSize int
extendRatio int
}
/* 생성자 */
func newMyList() *myList {
return &myList{
arrCapacity: 10, // 리스트 용량
arr: make([]int, 10), // 배열(리스트 원소 저장)
arrSize: 0, // 리스트 길이(현재 원소 개수)
extendRatio: 2, // 리스트의 용량을 확장할 때마다 적용하는 배수
}
}
/* 리스트 길이(현재 원소 개수) 반환 */
func (l *myList) size() int {
return l.arrSize
}
/* 리스트 용량 반환 */
func (l *myList) capacity() int {
return l.arrCapacity
}
/* 원소 접근 */
func (l *myList) get(index int) int {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if index < 0 || index >= l.arrSize {
panic("인덱스가 범위를 벗어났다")
}
return l.arr[index]
}
/* 원소 갱신 */
func (l *myList) set(num, index int) {
if index < 0 || index >= l.arrSize {
panic("인덱스가 범위를 벗어났다")
}
l.arr[index] = num
}
/* 맨 뒤에 원소 추가 */
func (l *myList) add(num int) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if l.arrSize == l.arrCapacity {
l.extendCapacity()
}
l.arr[l.arrSize] = num
// 원소 개수를 갱신한다
l.arrSize++
}
/* 중간에 원소 삽입 */
func (l *myList) insert(num, index int) {
if index < 0 || index >= l.arrSize {
panic("인덱스가 범위를 벗어났다")
}
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if l.arrSize == l.arrCapacity {
l.extendCapacity()
}
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for j := l.arrSize - 1; j >= index; j-- {
l.arr[j+1] = l.arr[j]
}
l.arr[index] = num
// 원소 개수를 갱신한다
l.arrSize++
}
/* 원소 삭제 */
func (l *myList) remove(index int) int {
if index < 0 || index >= l.arrSize {
panic("인덱스가 범위를 벗어났다")
}
num := l.arr[index]
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for j := index; j < l.arrSize-1; j++ {
l.arr[j] = l.arr[j+1]
}
// 원소 개수를 갱신한다
l.arrSize--
// 삭제한 원소를 반환한다
return num
}
/* 리스트 용량 확장 */
func (l *myList) extendCapacity() {
// 길이가 원래 배열의 extendRatio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
l.arr = append(l.arr, make([]int, l.arrCapacity*(l.extendRatio-1))...)
// 리스트 용량을 갱신한다
l.arrCapacity = len(l.arr)
}
/* 유효한 길이만큼의 리스트 반환 */
func (l *myList) toArray() []int {
// 유효한 길이 범위 안의 리스트 원소만 변환한다
return l.arr[:l.arrSize]
}
my_list.swift
/* 리스트 클래스 */
class MyList {
private var arr: [Int] // 배열(리스트 원소 저장)
private var _capacity: Int // 리스트 용량
private var _size: Int // 리스트 길이(현재 원소 개수)
private let extendRatio: Int // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
init() {
_capacity = 10
_size = 0
extendRatio = 2
arr = Array(repeating: 0, count: _capacity)
}
/* 리스트 길이(현재 원소 개수) 반환*/
func size() -> Int {
_size
}
/* 리스트 용량 반환 */
func capacity() -> Int {
_capacity
}
/* 원소 접근 */
func get(index: Int) -> Int {
// 인덱스가 범위를 벗어나면 오류를 발생시킨다. 아래에서도 동일하다
if index < 0 || index >= size() {
fatalError("인덱스가 범위를 벗어났다")
}
return arr[index]
}
/* 원소 갱신 */
func set(index: Int, num: Int) {
if index < 0 || index >= size() {
fatalError("인덱스가 범위를 벗어났다")
}
arr[index] = num
}
/* 맨 뒤에 원소 추가 */
func add(num: Int) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if size() == capacity() {
extendCapacity()
}
arr[size()] = num
// 원소 개수를 갱신한다
_size += 1
}
/* 중간에 원소 삽입 */
func insert(index: Int, num: Int) {
if index < 0 || index >= size() {
fatalError("인덱스가 범위를 벗어났다")
}
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if size() == capacity() {
extendCapacity()
}
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for j in (index ..< size()).reversed() {
arr[j + 1] = arr[j]
}
arr[index] = num
// 원소 개수를 갱신한다
_size += 1
}
/* 원소 삭제 */
@discardableResult
func remove(index: Int) -> Int {
if index < 0 || index >= size() {
fatalError("인덱스가 범위를 벗어났다")
}
let num = arr[index]
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for j in index ..< (size() - 1) {
arr[j] = arr[j + 1]
}
// 원소 개수를 갱신한다
_size -= 1
// 삭제한 원소를 반환한다
return num
}
/* 리스트 용량 확장 */
func extendCapacity() {
// 길이가 원래 배열의 extendRatio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
arr = arr + Array(repeating: 0, count: capacity() * (extendRatio - 1))
// 리스트 용량을 갱신한다
_capacity = arr.count
}
/* 리스트를 배열로 변환 */
func toArray() -> [Int] {
Array(arr.prefix(size()))
}
}
my_list.js
/* 리스트 클래스 */
class MyList {
#arr = new Array(); // 배열(리스트 원소 저장)
#capacity = 10; // 리스트 용량
#size = 0; // 리스트 길이(현재 원소 개수)
#extendRatio = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
constructor() {
this.#arr = new Array(this.#capacity);
}
/* 리스트 길이(현재 원소 개수) 반환*/
size() {
return this.#size;
}
/* 리스트 용량 반환 */
capacity() {
return this.#capacity;
}
/* 원소 접근 */
get(index) {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= this.#size) throw new Error('인덱스가 범위를 벗어났다');
return this.#arr[index];
}
/* 원소 갱신 */
set(index, num) {
if (index < 0 || index >= this.#size) throw new Error('인덱스가 범위를 벗어났다');
this.#arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
add(num) {
// 길이가 용량과 같으면 용량을 확장해야 한다
if (this.#size === this.#capacity) {
this.extendCapacity();
}
// 새 원소를 리스트 맨 뒤에 추가한다
this.#arr[this.#size] = num;
this.#size++;
}
/* 중간에 원소 삽입 */
insert(index, num) {
if (index < 0 || index >= this.#size) throw new Error('인덱스가 범위를 벗어났다');
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (this.#size === this.#capacity) {
this.extendCapacity();
}
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (let j = this.#size - 1; j >= index; j--) {
this.#arr[j + 1] = this.#arr[j];
}
// 원소 개수를 갱신한다
this.#arr[index] = num;
this.#size++;
}
/* 원소 삭제 */
remove(index) {
if (index < 0 || index >= this.#size) throw new Error('인덱스가 범위를 벗어났다');
let num = this.#arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (let j = index; j < this.#size - 1; j++) {
this.#arr[j] = this.#arr[j + 1];
}
// 원소 개수를 갱신한다
this.#size--;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
extendCapacity() {
// 길이가 원래 배열의 extendRatio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
this.#arr = this.#arr.concat(
new Array(this.capacity() * (this.#extendRatio - 1))
);
// 리스트 용량을 갱신한다
this.#capacity = this.#arr.length;
}
/* 리스트를 배열로 변환 */
toArray() {
let size = this.size();
// 유효한 길이 범위 안의 리스트 원소만 변환한다
const arr = new Array(size);
for (let i = 0; i < size; i++) {
arr[i] = this.get(i);
}
return arr;
}
}
my_list.ts
/* 리스트 클래스 */
class MyList {
private arr: Array<number>; // 배열(리스트 원소 저장)
private _capacity: number = 10; // 리스트 용량
private _size: number = 0; // 리스트 길이(현재 원소 개수)
private extendRatio: number = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
constructor() {
this.arr = new Array(this._capacity);
}
/* 리스트 길이(현재 원소 개수) 반환*/
public size(): number {
return this._size;
}
/* 리스트 용량 반환 */
public capacity(): number {
return this._capacity;
}
/* 원소 접근 */
public get(index: number): number {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= this._size) throw new Error('인덱스가 범위를 벗어났다');
return this.arr[index];
}
/* 원소 갱신 */
public set(index: number, num: number): void {
if (index < 0 || index >= this._size) throw new Error('인덱스가 범위를 벗어났다');
this.arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
public add(num: number): void {
// 길이가 용량과 같으면 용량을 확장해야 한다
if (this._size === this._capacity) this.extendCapacity();
// 새 원소를 리스트 맨 뒤에 추가한다
this.arr[this._size] = num;
this._size++;
}
/* 중간에 원소 삽입 */
public insert(index: number, num: number): void {
if (index < 0 || index >= this._size) throw new Error('인덱스가 범위를 벗어났다');
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (this._size === this._capacity) {
this.extendCapacity();
}
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (let j = this._size - 1; j >= index; j--) {
this.arr[j + 1] = this.arr[j];
}
// 원소 개수를 갱신한다
this.arr[index] = num;
this._size++;
}
/* 원소 삭제 */
public remove(index: number): number {
if (index < 0 || index >= this._size) throw new Error('인덱스가 범위를 벗어났다');
let num = this.arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (let j = index; j < this._size - 1; j++) {
this.arr[j] = this.arr[j + 1];
}
// 원소 개수를 갱신한다
this._size--;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
public extendCapacity(): void {
// 길이가 size인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
this.arr = this.arr.concat(
new Array(this.capacity() * (this.extendRatio - 1))
);
// 리스트 용량을 갱신한다
this._capacity = this.arr.length;
}
/* 리스트를 배열로 변환 */
public toArray(): number[] {
let size = this.size();
// 유효한 길이 범위 안의 리스트 원소만 변환한다
const arr = new Array(size);
for (let i = 0; i < size; i++) {
arr[i] = this.get(i);
}
return arr;
}
}
my_list.dart
/* 리스트 클래스 */
class MyList {
late List<int> _arr; // 배열(리스트 원소 저장)
int _capacity = 10; // 리스트 용량
int _size = 0; // 리스트 길이(현재 원소 개수)
int _extendRatio = 2; // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
MyList() {
_arr = List.filled(_capacity, 0);
}
/* 리스트 길이(현재 원소 개수) 반환*/
int size() => _size;
/* 리스트 용량 반환 */
int capacity() => _capacity;
/* 원소 접근 */
int get(int index) {
if (index >= _size) throw RangeError('인덱스가 범위를 벗어났다');
return _arr[index];
}
/* 원소 갱신 */
void set(int index, int _num) {
if (index >= _size) throw RangeError('인덱스가 범위를 벗어났다');
_arr[index] = _num;
}
/* 맨 뒤에 원소 추가 */
void add(int _num) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (_size == _capacity) extendCapacity();
_arr[_size] = _num;
// 원소 개수를 갱신한다
_size++;
}
/* 중간에 원소 삽입 */
void insert(int index, int _num) {
if (index >= _size) throw RangeError('인덱스가 범위를 벗어났다');
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (_size == _capacity) extendCapacity();
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (var j = _size - 1; j >= index; j--) {
_arr[j + 1] = _arr[j];
}
_arr[index] = _num;
// 원소 개수를 갱신한다
_size++;
}
/* 원소 삭제 */
int remove(int index) {
if (index >= _size) throw RangeError('인덱스가 범위를 벗어났다');
int _num = _arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (var j = index; j < _size - 1; j++) {
_arr[j] = _arr[j + 1];
}
// 원소 개수를 갱신한다
_size--;
// 삭제한 원소를 반환한다
return _num;
}
/* 리스트 용량 확장 */
void extendCapacity() {
// 길이가 원래 배열의 _extendRatio배인 새 배열을 생성한다
final _newNums = List.filled(_capacity * _extendRatio, 0);
// 원래 배열을 새 배열에 복사한다
List.copyRange(_newNums, 0, _arr);
// _arr의 참조를 갱신한다
_arr = _newNums;
// 리스트 용량을 갱신한다
_capacity = _arr.length;
}
/* 리스트를 배열로 변환 */
List<int> toArray() {
List<int> arr = [];
for (var i = 0; i < _size; i++) {
arr.add(get(i));
}
return arr;
}
}
my_list.rs
/* 리스트 클래스 */
#[allow(dead_code)]
struct MyList {
arr: Vec<i32>, // 배열(리스트 원소 저장)
capacity: usize, // 리스트 용량
size: usize, // 리스트 길이(현재 원소 개수)
extend_ratio: usize, // 리스트의 용량을 확장할 때마다 적용하는 배수
}
#[allow(unused, unused_comparisons)]
impl MyList {
/* 생성자 */
pub fn new(capacity: usize) -> Self {
let mut vec = vec![0; capacity];
Self {
arr: vec,
capacity,
size: 0,
extend_ratio: 2,
}
}
/* 리스트 길이(현재 원소 개수) 반환*/
pub fn size(&self) -> usize {
return self.size;
}
/* 리스트 용량 반환 */
pub fn capacity(&self) -> usize {
return self.capacity;
}
/* 원소 접근 */
pub fn get(&self, index: usize) -> i32 {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if index >= self.size {
panic!("인덱스가 범위를 벗어났다")
};
return self.arr[index];
}
/* 원소 갱신 */
pub fn set(&mut self, index: usize, num: i32) {
if index >= self.size {
panic!("인덱스가 범위를 벗어났다")
};
self.arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
pub fn add(&mut self, num: i32) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if self.size == self.capacity() {
self.extend_capacity();
}
self.arr[self.size] = num;
// 원소 개수를 갱신한다
self.size += 1;
}
/* 중간에 원소 삽입 */
pub fn insert(&mut self, index: usize, num: i32) {
if index >= self.size() {
panic!("인덱스가 범위를 벗어났다")
};
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if self.size == self.capacity() {
self.extend_capacity();
}
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for j in (index..self.size).rev() {
self.arr[j + 1] = self.arr[j];
}
self.arr[index] = num;
// 원소 개수를 갱신한다
self.size += 1;
}
/* 원소 삭제 */
pub fn remove(&mut self, index: usize) -> i32 {
if index >= self.size() {
panic!("인덱스가 범위를 벗어났다")
};
let num = self.arr[index];
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for j in index..self.size - 1 {
self.arr[j] = self.arr[j + 1];
}
// 원소 개수를 갱신한다
self.size -= 1;
// 삭제한 원소를 반환한다
return num;
}
/* 리스트 용량 확장 */
pub fn extend_capacity(&mut self) {
// 길이가 원래 배열의 extend_ratio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
let new_capacity = self.capacity * self.extend_ratio;
self.arr.resize(new_capacity, 0);
// 리스트 용량을 갱신한다
self.capacity = new_capacity;
}
/* 리스트를 배열로 변환 */
pub fn to_array(&self) -> Vec<i32> {
// 유효한 길이 범위 안의 리스트 원소만 변환한다
let mut arr = Vec::new();
for i in 0..self.size {
arr.push(self.get(i));
}
arr
}
}
my_list.c
/* 리스트 클래스 */
typedef struct {
int *arr; // 배열(리스트 원소 저장)
int capacity; // 리스트 용량
int size; // 리스트 크기
int extendRatio; // 리스트 용량을 확장할 때마다 적용하는 배수
} MyList;
/* 생성자 */
MyList *newMyList() {
MyList *nums = malloc(sizeof(MyList));
nums->capacity = 10;
nums->arr = malloc(sizeof(int) * nums->capacity);
nums->size = 0;
nums->extendRatio = 2;
return nums;
}
/* 소멸자 */
void delMyList(MyList *nums) {
free(nums->arr);
free(nums);
}
/* 리스트 길이 구하기 */
int size(MyList *nums) {
return nums->size;
}
/* 리스트 용량 반환 */
int capacity(MyList *nums) {
return nums->capacity;
}
/* 원소 접근 */
int get(MyList *nums, int index) {
assert(index >= 0 && index < nums->size);
return nums->arr[index];
}
/* 원소 갱신 */
void set(MyList *nums, int index, int num) {
assert(index >= 0 && index < nums->size);
nums->arr[index] = num;
}
/* 맨 뒤에 원소 추가 */
void add(MyList *nums, int num) {
if (size(nums) == capacity(nums)) {
extendCapacity(nums); // 용량 확장
}
nums->arr[size(nums)] = num;
nums->size++;
}
/* 중간에 원소 삽입 */
void insert(MyList *nums, int index, int num) {
assert(index >= 0 && index < size(nums));
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size(nums) == capacity(nums)) {
extendCapacity(nums); // 용량 확장
}
for (int i = size(nums); i > index; --i) {
nums->arr[i] = nums->arr[i - 1];
}
nums->arr[index] = num;
nums->size++;
}
/* 원소 삭제 */
// 주의: stdio.h가 remove라는 이름을 사용한다
int removeItem(MyList *nums, int index) {
assert(index >= 0 && index < size(nums));
int num = nums->arr[index];
for (int i = index; i < size(nums) - 1; i++) {
nums->arr[i] = nums->arr[i + 1];
}
nums->size--;
return num;
}
/* 리스트 용량 확장 */
void extendCapacity(MyList *nums) {
// 먼저 공간 할당
int newCapacity = capacity(nums) * nums->extendRatio;
int *extend = (int *)malloc(sizeof(int) * newCapacity);
int *temp = nums->arr;
// 기존 데이터를 새 공간에 복사
for (int i = 0; i < size(nums); i++)
extend[i] = nums->arr[i];
// 기존 데이터 공간 해제
free(temp);
// 새 데이터로 갱신
nums->arr = extend;
nums->capacity = newCapacity;
}
/* 출력을 위해 리스트를 Array로 변환 */
int *toArray(MyList *nums) {
return nums->arr;
}
my_list.kt
/* 리스트 클래스 */
class MyList {
private var arr: IntArray = intArrayOf() // 배열(리스트 원소 저장)
private var capacity: Int = 10 // 리스트 용량
private var size: Int = 0 // 리스트 길이(현재 원소 개수)
private var extendRatio: Int = 2 // 리스트의 용량을 확장할 때마다 적용하는 배수
/* 생성자 */
init {
arr = IntArray(capacity)
}
/* 리스트 길이(현재 원소 개수) 반환 */
fun size(): Int {
return size
}
/* 리스트 용량 반환 */
fun capacity(): Int {
return capacity
}
/* 원소 접근 */
fun get(index: Int): Int {
// 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
if (index < 0 || index >= size)
throw IndexOutOfBoundsException("인덱스가 범위를 벗어났다")
return arr[index]
}
/* 원소 갱신 */
fun set(index: Int, num: Int) {
if (index < 0 || index >= size)
throw IndexOutOfBoundsException("인덱스가 범위를 벗어났다")
arr[index] = num
}
/* 맨 뒤에 원소 추가 */
fun add(num: Int) {
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size == capacity())
extendCapacity()
arr[size] = num
// 원소 개수를 갱신한다
size++
}
/* 중간에 원소 삽입 */
fun insert(index: Int, num: Int) {
if (index < 0 || index >= size)
throw IndexOutOfBoundsException("인덱스가 범위를 벗어났다")
// 원소 개수가 용량을 초과하면 용량 확장을 수행한다
if (size == capacity())
extendCapacity()
// 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for (j in size - 1 downTo index)
arr[j + 1] = arr[j]
arr[index] = num
// 원소 개수를 갱신한다
size++
}
/* 원소 삭제 */
fun remove(index: Int): Int {
if (index < 0 || index >= size)
throw IndexOutOfBoundsException("인덱스가 범위를 벗어났다")
val num = arr[index]
// 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for (j in index..<size - 1)
arr[j] = arr[j + 1]
// 원소 개수를 갱신한다
size--
// 삭제한 원소를 반환한다
return num
}
/* 리스트 용량 확장 */
fun extendCapacity() {
// 길이가 원래 배열의 extendRatio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
arr = arr.copyOf(capacity() * extendRatio)
// 리스트 용량을 갱신한다
capacity = arr.size
}
/* 리스트를 배열로 변환 */
fun toArray(): IntArray {
val size = size()
// 유효한 길이 범위 안의 리스트 원소만 변환한다
val arr = IntArray(size)
for (i in 0..<size) {
arr[i] = get(i)
}
return arr
}
}
my_list.rb
### 리스트 클래스 ###
class MyList
attr_reader :size # 리스트 길이(현재 원소 개수) 반환
attr_reader :capacity # 리스트 용량 반환
### 생성자 ###
def initialize
@capacity = 10
@size = 0
@extend_ratio = 2
@arr = Array.new(capacity)
end
### 원소 접근 ###
def get(index)
# 인덱스가 범위를 벗어나면 예외를 발생시킨다. 아래에서도 동일하다
raise IndexError, "인덱스가 범위를 벗어났다" if index < 0 || index >= size
@arr[index]
end
### 원소 접근 ###
def set(index, num)
raise IndexError, "인덱스가 범위를 벗어났다" if index < 0 || index >= size
@arr[index] = num
end
### 맨 뒤에 원소 추가 ###
def add(num)
# 원소 개수가 용량을 초과하면 용량 확장을 수행한다
extend_capacity if size == capacity
@arr[size] = num
# 원소 개수를 갱신한다
@size += 1
end
### 중간에 원소 삽입 ###
def insert(index, num)
raise IndexError, "인덱스가 범위를 벗어났다" if index < 0 || index >= size
# 원소 개수가 용량을 초과하면 용량 확장을 수행한다
extend_capacity if size == capacity
# 인덱스 index와 그 뒤의 원소를 모두 한 칸씩 뒤로 이동한다
for j in (size - 1).downto(index)
@arr[j + 1] = @arr[j]
end
@arr[index] = num
# 원소 개수를 갱신한다
@size += 1
end
### 원소 삭제 ###
def remove(index)
raise IndexError, "인덱스가 범위를 벗어났다" if index < 0 || index >= size
num = @arr[index]
# 인덱스 index 뒤의 원소를 모두 한 칸씩 앞으로 이동한다
for j in index...size
@arr[j] = @arr[j + 1]
end
# 원소 개수를 갱신한다
@size -= 1
# 삭제한 원소를 반환한다
num
end
### 리스트 용량 확장 ###
def extend_capacity
# 길이가 원래 배열의 extend_ratio배인 새 배열을 생성하고, 원래 배열을 새 배열에 복사한다
arr = @arr.dup + Array.new(capacity * (@extend_ratio - 1))
# 리스트 용량을 갱신한다
@capacity = arr.length
end
### 리스트를 배열로 변환 ###
def to_array
sz = size
# 유효한 길이 범위 안의 리스트 원소만 변환한다
arr = Array.new(sz)
for i in 0...sz
arr[i] = get(i)
end
arr
end
end