[지료구조] ArrayList에 대해서

 

 

제목과는 약간 관련 없는 내용이지만, 오늘은 두 번의 코딩 테스트를 쳤다. 

배달 잘하는 친구들과 메시지 잘 보내는 친구들에서 보는 코테였는데 앞선 테스트는 자바스크립트, 다음 테스트는 자바로 쳤다.

 

---

 

코테 일정을 받고 익숙하지 않은 JS로 시험을 준비하면서 내가 상상했던 것 : 

---

 

"뭐? 신입 프론트엔드 개발자가 백엔드와 DB 지식도 갖고 있는 자기 주도형 풀 스택 개발자라고?"

"뭐? 토이 프로젝트를 만들었는데 react와 스프링 부트 부분을 전부 담당했다고?"

 

---

아침에 털리고 오후에 털린 다음의 나 :

 

 

어림도 없지...

 

---

 

알고리즘 공부를 독학으로 하는 것은 쉽지 않다. 프로그래머스 lv2 정도 문제만 되어도 풀기 위해 많은 시간을 투자하면서 공부해야 하는데 문제는 코테 공부에만 올인하면 어쩌다 한 번씩 마주치는 미니 프로젝트 같은 실무과제에서 털리는 경우도 있다. 

그럼 어떻게 해야 될까? 

 

몸을 하나 더 만들어서 코테 공부하면서 실무 공부도 하면 된다! 다들 신입이지만 경력 3년 차 혹은 그 이상에 준하는 실력을 가지고 있으며 Hackerton 같은 경험은 물론 인턴경력도 한두 개 정도는 당연하지 않던가. 그 정도에 비하면 몸 두 개 만드는 건 쉬운듯하니 그냥 하자...

 

---

 

그래서 위와 같은 이유로 시작한 자료구조 공부 1편 ArrayList이다. 사실 알고리즘 문제를 풀면서 자주 사용하기는 했는데 내가 주로 사용한 경우는 

 

 

1. 배열을 쓰고는 싶은데 크기를 미리 정할 수 없을 때

2. list.add()로 편리하게 넣고 싶을 때

 

정도였던 거 같다. 그래서 그냥 아는 내용은 한 번 더 짚고 놓친 내용은 배울 수 있는 계기라고 생각하며 공부했다.

 

 

---

ArrayList 선언

 

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

아마 대부분의 ArrayList는 이렇게 구현하는 거 같다. 하지만 왜? 에 대해서는 생각해본 적은 없던 거 같다. 

 

먼저 List는 인터페이스, ArrayList는 클래스다. 

클래스는 일반 클래스와 추상 클래스로 구성되고

인터페이스는 모든 메서드가 추상 메서드인 경우이며 인터페이스를 상속받는 클래스는 인터페이스의 모든 추상 메서드를 구현해야 한다.

 

정리하면 List라는 큰 범주 속에 있는 것들 중 하나인 ArrayList로 정의해놓은 것이라고 할 수 있다.

 

ArrayList<Integer> list = new ArrayList<Integer>();

 

이런 식으로 쓸 수도 있지만 이렇게 할 경우 List -> ArrayList 순서로 내려오는 것이 아니라 ArrayList로 고정되어버린 것이기 때문에 유연성이 떨어진다. 잘 모르고 써 왔던 형식이지만 그대로 써도 좋을 것 같다. 그런데 생각해보면 알고리즘 문제 풀 때는 유연성이 필요한 경우가 딱히 없었기 때문에 ArrayList로 고정하는 것도 뭐 상관없을 것 같다.

 

그리고 new 부분에 파라미터 타입을 생략한 것은 그냥 JDK 1.7 이상 버전에 추가된 기능이다.

 

 

 

---

 

 

ArrayList 주요 메서드

 

내가 ArrayList를 썼던 기억을 되돌려보면 일반 배열처럼 직접 인덱스 값을 넣어서 해당 배열 값을 가져오는 일은 없었던 거 같다. ArrayList에 대한 공부를 확실히 하지 않아서 그냥 안된다고 생각했는데 아니었다. 그냥 내가 모르는 거였다. 

 

list.add(value)

배열에 내가 원하는 값을 추가할 때 이렇게 추가해주면 된다. 보통 반복문을 통해서 값을 넣는다.

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

        for (int i=0; i < 10; i ++){
        	
            // 0 ~ 9의 값을 차례로 list에 넣는다.
            list.add(i);
            
        }

 

list.get(index) 

왜 이때까지 ArrayList에서는 인덱스로 값을 검색할 수 없다고 생각했을까...? 지금이라도 알아서 다행이다.

몰랐던 사실이지만 null 값도 할당할 수 있다!

 

list.size()

List의 사이즈를 알고 싶을 때 사용한다. 아마 반복문의 범위를 지정할 때 쓰면 되겠지?

 

list.remove(index)

List는 생각보다 많은 기능이 있었다. null값을 할당할 수 있어서 그런지 List가 뭔가 더 깔끔하게 삭제하는 느낌.

다만, 중요한 것은 List에서 특정 인덱스를 삭제해서 빈 공간이 생기면 그대로 두는 것이 아니라 뒤에 있는 값을 앞당긴다는 것이다. 위에서 언급은 안 했지만 추가할 때도 마찬가지.

 

이것은 코딩 테스트에서 가장 중요하게 생각해야 할 효율성과 관련이 있는데 List에서 값을 추가하고 삭제할 때마다 많은 요소를 앞당기고 미는 작업이 생긴다. 그런데 이런 작업을 반복문에서 한다면? 

 

You shall not pass

 

실행시간 초과로 코테를 통과할 수 없을 것이다. 따라서 삭제와 추가는 조심해서 쓰도록 하자.

 

++ 추가

remove() 메소드는 리턴값으로 삭제한 값을 리턴한다. 유용하게 쓸수있을지도?

 

 

정렬

각종 알고리즘에서 정렬을 빼먹을 수 없는 존재다. 개인적으로 정렬은 정말 어렵다고 생각한다.

아무튼 일반 배열과 ArrayList의 정렬 방식은 약간 다르다.

 

 

package Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArrayTest2 {

    public static void main(String[] args) {

        int[] arr = {3,2,4,5,12,5,4,6,7,23};

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

        list.add(3);
        list.add(2);
        list.add(4);
        list.add(5);
        list.add(12);
        list.add(5);
        list.add(4);
        list.add(6);
        list.add(7);
        list.add(23);

        System.out.println("Array");
        Arrays.sort(arr);
        for (int i : arr){
            System.out.print(i + " ");
        }

        System.out.println();

        Collections.sort(list);
        

        System.out.println("List");
        for (int i : list){
            System.out.print(i + " ");
        }


    }
}

 

콘솔에 출력된 결과 

 

 

같은 두가지 다른 형태의 배열을 만들어서 동일한 원소를 넣고 정렬했다. 동일한 결과가 나왔지만  코드에서 알 수 있듯이, 형태가 약간 다르다. 

Arrays.sort(arr);

Collections.sort(list);

 

---

 

뭐가 다른지 궁금해서 조금만 파봤다.

 

먼저 일반 배열의 sort에 대해서 찾아봤는데 뭔지는 모르겠지만 대충 DualPivotQuickSort 란 알고리즘으로 정렬을 하는 것 같다. 정렬에 대해서 파고파고 들어가면 끝도 없기에 간단히 정리를 하자면

 

DualPivotQuickSort 는 Insertion sort와 Quick sort를 섞은 것이다. 

 

Quick sort는 원시 데이터 타입 같은 정렬방식이 정해져 있는 방식의 데이터에 효과적이기 때문에 일반 배열에서 사용한다.

 

 

 

List 같은 경우 정렬하는 Comparable 인터페이스를 상속받는다. Comparable은 사용자가 정렬 기준을 직접 정의할 수 있다. 일반 배열은 원시 타입의 데이터를 주로 쓰는 반면 Collection을 사용하는 자료들은 Wrapper class에 넣은 자료들을 넣어서 사용하기 때문에 그런 것 같다. 찾아보니 Collecton에서는 Tim sort를 사용하는데 

 

Tim sort는 Insertion sort와 Merge sort를 섞은 것이다.

 

그리고 이 정렬 방식은 현실 세계에 있는 데이터들을 정렬하는데 적합하다고 한다. (designed to perform well on many kinds of real-world data. - wiki)

 

 

stackoverflow.com/questions/32334319/why-does-collections-sort-use-mergesort-but-arrays-sort-does-not

Why does Collections.sort use Mergesort but Arrays.sort does not?

 

---

 

공부하면서 간단하게 해 본 실습 코드 ↓↓↓↓↓

package Array;

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

public class ArrayTest {


    public static void main(String[] args) {


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

        for (int i=0; i < 10; i ++){
            list.add(i);
        }

        System.out.println(list.get(1));
        //1번 인덱스의 값 : 1

        for (int i : list){
            System.out.print(i + " ");
        }
        System.out.println();

        // List 에서 값을 추가하면 많은 작업이 발생한다.
        System.out.println("값을 추가하기전 5번 인덱스 : " + list.get(5));

        list.add(4, null);

        System.out.println("값을 추가한 다음 5번 인덱스 : " + list.get(5));


        // 값을 삭제할때도 마찬가지

        System.out.println("값을 삭제하기 전 3번 인덱스 : " + list.get(3));
        list.remove(3);
        System.out.println("값을 삭제한 후 3번 인덱스 : " + list.get(3));




    }


}

 

콘솔에 출력된 결과

 

 

 

 

마치며

 

사실 정리 잘해놓은 다른 블로그와 비교하면 List가 속해있는 Collection 프레임워크를 파고들어가거나 심도 있게 기능적인 원리를 알아본 것은 아니지만 지금 내 단계에서는 어떻게 사용하고, 뭐가 중요하고, 언제 사용하는지 아는 것이 가장 중요한 것 같다. 만약 다음에 다시 ArrayList를 공부한다면 그때는 아마 대용량의 데이터를 처리할 때 좀 더 효율적으로 처리하기 위해서 고민하는 경우가 아닐까 싶다. 

코테는 망했지만 뭐라도 더 알게 되었으니 오늘은 이득임.