[Algorithm] 02. 리스트 (List)

리스트 (List)

 

리스트(List)란 순서를 가지고 원소를 저장하는 자료구조로 Array List나 Linked List로 구현이 가능하다.

 

• Array List는 요소를 빈번히 검색해야 하거나, 중간 삽입과 삭제가 적은 경우에 적합하다.
• Linked List는 삽입과 삭제가 빈번하고, 데이터의 물리적 위치가 중요하지 않은 경우에 유리하다.

 

---

 

Array List

 

배열을 기반으로 구성된 List형 자료구조로 정적배열(Static Array)이나 동적배열(Dynamic Array)로 구현이 가능하다.

 

 

💡  Static Array

 

Static Array는 다음과 같은 두 가지 특징을 가진다.

• 고정된 크기의 저장 공간을 가진다.
• 연속된 메모리에 순차적으로 데이터를 저장한다.

즉, 배열을 선언할 때 선언한 크기만큼 연속된 메모리를 할당 받아 연속적으로 데이터를 저장한다.

 

 

📍  Random access

 

메모리에 저장된 데이터에 접근하려면 해당 데이터의 주소값을 알아야 한다.

배열은 연속적이므로 첫 번째 주소값만 알고 있다면 어떤 인덱스에도 즉시 접근이 가능하다.

이를 Direct access 또는 Random access 라고 부른다.

 

 

📍  Static Array 선언

int[] intArray = new int[10];          
String[] stringArray = new String[5];   
char[] charArray = new char[]{ 'h', 'e', 'l', 'l', 'o' };
char[] charArray = { 'h', 'e', 'l', 'l', 'o' };

※  배열을 초기화하고 값을 넣어주지 않으면 기본값으로 설정된다.

     int = 0  ,  char = \u0000  ,  string = null

 

 

📍  Static Array 접근 및 수정

intArray[i];                           // i번째 원소에 접근
intArray[intArray.length - 1];         // 마지막 원소에 접근
intArray[i] = 3;                       // i번째 원소를 3으로 수정

 

 

📍  Static Array 복사

// 1차원 배열 복사

int[] arr = { 1, 2, 3, 4, 5 };

int[] copy = Arrays.copyOf(arr, arr.length);    // 전체 복사 copy = { 1, 2, 3, 4, 5 }
int[] copy = Arrays.copyOf(arr, 2, 5);          // 특정 부분 복사 copy = { 3, 4, 5 }

// 2차원 배열 복사

int[][] arr = { ... };
int[][] copy = new int[arr.length][arr[0].length];

for(int i = 0; i < arr.length; i++) {
	copy[i] = Array.copyOf(arr[i], arr[0].length);
}

 

Arrays.copyOf( ) 메소드를 사용하여 2차원 배열을 복사할 경우 shallow copy가 발생할 수 있다.

deep copy를 하려면 for 문을 사용하여 각 열에 대한 복사가 필요하다.

 

※  Shallow Copy

    내부 배열들은 복사되는 않는 것으로 복사된 배열을 변경하면 원본 배열이 함께 수정되는 현상이다.

int[][] arr = { { 1, 2, 3 } , { 4, 5, 6 } }
int[][] copy = Array.copyOf(arr, arr.length);

copy[0][0] = 9999;    // 복사본 수정

System.out.println("arr[0][0] = " + arr[0][0]);     
System.out.println("copy[0][0] = " + copy[0][0]);​

// 결과
arr[0][0] = 9999
copy[0][0] = 9999

 

 

📍 Static Array 정렬

// 오름차순으로 정렬

int[] arr = { 1, 3, 2 };
Arrays.sort(arr);

for(int num : arr) {
	System.out.println("num = " + num);
}

// 결과
num = 1
num = 2
num = 3

 

 

📍 Static Array 초기화

int[] arr = new int[10];
Arrays.fill(arr, 5);        // 모든 인덱스가 5로 초기화

 

 

---

 

💡  Dynamic Array

 

Dynamic Array는 다음과 같은 두 가지 특징을 가진다.

• 유동적인 크기의 저장 공간을 가진다.
• 필요에 따라 크기를 확장하고 데이터를 저장한다.

크기 변경이 불가능한 정적 배열과 달리 동적 배열에서는 크기 변경이 가능하므로 코딩 테스트에서 자주 사용된다.

 

 

📍  resize

 

동적 배열에 데이터를 추가하다 할당된 크기를 초과하면, 크기를 늘린 배열을 새로 선언하고 데이터를 옮긴다.

그리고 기존에 선언된 배열은 메로리에서 삭제하는데 이 과정을 resize 라고 한다.

resize를 한 칸씩 늘린다면 비효율적이므로 보통 2배 큰 크기로 resize하는데 이를 doubling 이라고 한다.

 

 

📍  Dynamic Array 사용

 

List 인터페이스와 ArrayList 클래스를 사용하면 직접 구현할 필요 없이 Dynamic Array를 사용할 수 있다.

우리가 알아야 할 것은 ArrayList 연산들과 시간 복잡도이다.

	Static Array	Dynamic Array
배열에 접근 및 수정	$O(1)$	$O(1)$
배열의 끝에 새로운 요소 삽입	$O(1)$	$O(1)$
배열의 마지막 요소 삭제	$O(1)$	$O(1)$
배열의 특정 위치에 새로운 요소 삽입	$O(n)$	$O(n)$
배열의 특정 위치의 요소 삭제	$O(n)$	$O(n)$

 

 

📍  Array List 선언

// Integer 타입을 저장하는 list라는 이름을 가진ArrayList 선언

List<Integer> list = new ArrayList<>();
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));

// Integer 타입을 저장하는 list라는 이름의 ArrayList 선언과 동시에 초기화

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));

 

 

📍  Array List 접근 및 수정

list.get(i);           // i번째 원소에
list.set(i, 3);        // i번째 원소를 3으로 수정

 

 

📍  Array List 추가

 

Array List에 원소를 추가하는 경우, 마지막에 원소를 삽입하는 경우와 중간에 원소를 삽입하는 경우로 나눌 수 있다.

 

마지막에 원소를 삽입하는 경우, 맨 뒤에 원소를 추가하기만 하면 되므로 $O(1)$의 시간 복잡도를 갖는다.

하지만 중간에 원소를 삽입하는 경우, 원소를 삽입한 후 뒤의 원소들을 한 칸씩 미루어야 하므로 $O(n)$이다.

list.add(1);               // 마지막에 원소 1 추가
list.add(2, 10);           // 2번째 위치에 원소 10 추가

 

 

📍  Array List 삭제

 

Array List의 원소를 삭제하는 경우도 마지막 원소를 삭제하는 경우와 중간 원소를 삭제하는 것으로 나눌 수 있다.

 

마지막 원소를 삭제하는 경우, 맨 뒤의 원소를 삭제하기만 하면 되므로 $O(1)$의 시간 복잡도를 갖는다.

하지만 중간의 원소를 삭제하는 경우, 원소를 삭제한 후 뒤의 원소들을 한 칸씩 당겨야 하므로 $O(n)$이다.

list.remove(list.size()-1));            // 마지막 원소 삭제
list.remove(2);                         // 2번째 위치의 원소 삭제
list.remove(Integer.valueIf(2));        // 2값을 갖는 원소 중 제일 앞에 있는 값 삭제

 

※  ArrayList<Integer> 의 remove( ) 사용할 때 주의점

remove( ) 인자로 인덱스와 지울 오브젝트를 받는 두 가지 오버라이드가 존재한다.
때문에 원소값이 2인 요소를 지우려고 list.remove(2) 를 사용하면 2번째 인덱스 값이 삭제된다.

따라서 값이 2인 요소를 삭제하려면 list.remove(Integer.valueOf(2)) 를 사용해야 한다.

단, 이는 정수 리스트에만 해당하는 것으로 스트링 리스트라면 list.remove("a") 로 사용해도 무방하다.

 

 

📍  Array List 정렬

List<Integer> arrayList = new ArrayList<>(List.of(1, 3, 2, 5, 4));

arrayList.sort(Integer::compareTo);                 // 오름차순 정렬
arrayList.sort(Comparator.reverseOrder());          // 내림차순 정렬

 

 

📍  2차원 Array List

 

배열과 다르게 리스트는 크기가 초기화 되어 있지 않으므로 새로운 행을 추가하며 사용해야 한다.

List<List<Integer>> doubleList = new ArrayList<>();

for(int i=0; i<10; i++) {
	List<Integer> newRow = new ArrayList<>();        // 새로운 열 추가
    for(int j=1; j<10; j++) {
    	newRow.add(i*10 + j);
    }
    doubleList.add(newRow);
}

// 결과
[[1, 2, 3, 4, 5, 6, 7, 8 ,9 ,10],
 [11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
 ...]

 

※  2차원 Array List의 deep copy & shallow copy

2차원 Array List도 일반적인 방식으로 복제하면 shallow copy가 되어 원본에 영향을 준다.

List<List<Integer>> doubleList = new ArrayList<>();
List<List<Integer>> copyList = new ArrayList<>(doubleList);

copyList.get(0).set(0, 9999);.​

// doubleList 결과
[[9999, 2, 3, 4, 5, 6, 7, 8, 9, 10], ...]​

때문에 2차원 Static Array와 마찬가지로 2차원 Array List도 for 문을 이용하여 각 행을 따로 복제해야 한다.

List<List<Integer>> doubleList = new ArrayList<>();
List<List<Integer>> copyList = new ArrayList<>();

for(List<Integer> row : doubleList) {
	copyList.add(new ArrayList<>(row)}
}

copyList.get(0).set(0, 9999);​

// doubleList 결과
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], ...]​