JAVA로 배우는 자료구조 - Data Structure란? Array, ArrayList

Data Structure란?

Data를 담는 것, 담는 구조.

큰 데이터를 효율적으로 관리하는 것.

어떤 Data를 담아서 정리정돈하고 효율적으로 관리하는 것이다.

 

Array

Array도 Java의 API이다. 배열은 거의 모든 프로그래밍 언어에 구현되어있다. 

배열은 연관된 데이터를 하나의 변수에 그룹핑해 관리하는 방법이다.

변수 하나에 여러 정보를 담을 수 있다.

 

int[] number = new int[4];

 

배열의 사용

배열에 들어간 데이터들은 순서대로 0부터 번호를 부여받음

배열.length는 배열의 길이이다.

 

배열의 한계

배열의 중간에 한 공간의 데이터를 없애고 나서 반복문으로 출력하면

없앤 공간은 그대로 있는데 값이 null이 리턴된다.

배열은 인덱스에 따라서 값을 유지하기 때문에 엘리먼트를 삭제해도 빈 자리가 남아있다.

이렇게 삭제한 자리를 그 뒤에 위치한 엘리먼트를 당겨서 메꾸기, 데이터가 순서에 따라 연속적으로 빈틈없이 위치하는 자료구조는 list이다. 

 

List

배열의 가장 큰 특징은 인덱스가 있다는 점이다.  인덱스는 데이터를 매우 빠르게 가져온다.

하지만 인덱스로 데이터를 가져오려면 각 데이터의 인덱스 값이 고정되어 있어야 한다.

또 어떤 엘리먼트를 삭제하면 삭제된 데이터가 있던 자리는 비워둬야 해 메모리가 낭비된다. 또 배열에 데이터가 있는지 없는지 항상 확인해야 한다.

리스트는 배열의 장점인 빠른 데이터 조회 대신, 빈틈없는 데이터 적재라는 장점을 취한 자료구조이다.

 

리스트의 기능

리스트의 핵심은 리스트가 순서가 있는 엘리먼트의 모임이다.

리스트는 빈 엘리먼트를 허용하지 않습니다. 또 리스트는 (배열과 마찬가지로) 중복된 데이터를 허용한다는 걸 기억해두세요. 중복을 허용하지 않는 자료 구조도 있다.

리스트의 정의

처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
리스트에 데이터가 있는지를 확인하는 기능
리스트의 모든 데이터에 접근할 수 있는 기능

이 있으면 리스트이다.

 

자바에서의 리스트

자바의 경우 배열과 리스트를 모두, 따로 지원합니다.

int[] number = {10,20,30,40,50};

int[]는 변수 numbers가 정수를 엘리먼트로 담는 배열을 말한다. 자바에서 배열의 원소를 제거하기는 쉽지 않다.

대신 자바에서는 리스트라는 자료구조를 지원한다.

 

LinkedList와 ArrayList는 같은 리스트지만 구현방법이 다르다.

LinkedList numbers = new LinkedList();

ArrayList numbers = new ArrayList();

 

LinkedList는 추가/삭제가 빠르지만, 인덱스 조회가 느리다.

ArrayList는 인덱스 조회가 빠르지만, 추가/삭제가 느리다.

데이터를 빈번히 조회한다면 ArrayList가,

데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.

 

ArrayList

ArrayList는 배열로 구현한 리스트이다. 내부에서 배열을 이용하기 때문에 인덱스를 이용해 데이터에 접근한다.

그래서 데이터를 인덱스로 조회할 땐 빠르지만, 데이터를 추가/삭제할 때는 느리다.

 

데이터 추가하기

ArrayList는 내부에서 배열에 데이터를 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면

이후의 데이터는 한 칸씩 뒤로 물러나야 한다.

 

데이터 삭제하기

삭제도 추가와 비슷하다. 데이터를 삭제한 빈자리를 채우기 위해 뒤쪽 데이터를 한 칸씩 앞으로 당겨야한다.

 

데이터 가져오기

Array로 구현한 리스트는 데이터를 매우 빠르게 가져옵니다. 메모리 주소를 정확하게 참조해서 데이터를 가져온다.

각 엘리먼트는 자신만의 주소(인덱스)를 가지고 있다. 인덱스를 알면 데이터를 빨리 찾아갈 수 있다.

 

내장된 ArrayList의 사용법

ArrayList를 사용하려면 먼저 ArrayList 객체를 만들어야 한다.

ArrayList는 java.util.ArrayList에 포함되어 있으므로 먼저 java.util.ArrayList import를 한다.

추가 - add메소드를 사용해서 추가한다. add는 단순 배열뒤에 데이터를 더하기 때문에 빠르다.

 

자바 배열의 크기는 고정되어 있다. 내부의 배열이 꽉 찼는데 새로운 데이터를 추가할 때는?

이 경우는 기존 배열보다 2배 긴 새 배열을 들어, 기존 데이터를 새로운 배열에 복제한다.

덕분에 프로그래머는 ArrayList의 크기를 신경 쓰지 않아도 되지만 배열의 크기를 키우는 데는 많은 부하가 걸린다.

 

삭제 - 특정 인덱스에 위치한 엘리먼트를 삭제할 때는 remove를 사용한다.

가져오기 - 특정 인덱스에 위치한 엘리먼트를 가져올 때는 get을 사용한다.

반복 - ArrayList를 탐색할때는 Iterator를 사용한다. Iterator는 객체지향 프로그래밍에서 주로 사용하는 반복 기법.

Iterator를 쓰려면 우선 Iterator 객체를 만들어야 한다.

Iterator<Integer> it = numbers.iterator();

Iterator 객체를 쓰면 numbers객체에 저장된 값을 하나씩 순회할 수 있다.

while(it.hasNext()){
    System.out.println(it.next());          
}

it.next()메소드는 호출될 때마다 엘리먼트를 순서대로 리턴한다. 만약 더 이상 엘리먼트가 없다면 while문 안의 조건

it.hasNext()는 false를 리턴해 while문을 종료시킨다.

Iterator는 엘리먼트를 삭제/추가할 때도 쓸 수 있다.

while(it.hasNext()){
    int value = it.next();
    if(value == 30){
        it.remove();
    }                       
}

it.remove()는 it.next()를 통해서 리턴된 numbers의 엘리먼트를 삭제한다.

 

Iterator보다 조금 더 편하게 엘리먼트를 순회하는 방법도 있다.

for(int value : numbers){
    System.out.println(value);
}