자바 자료구조1 -동적배열(ArrayList)

1. 정적 배열

 

자바에서 배열을 선언하기 위해 다음과 같이 선언한다.

 

//길이 100인 정수형 배열
int[] array = new int[100];

 

이렇게 선언한 배열을 정적 배열이라고 부른다.

 

정적 배열은 배열의 선언과 동시에 크기를 정해주어야하고, 이후 크기를 변경할 수는 없다.

 

변경하는 방법이야 있겠지만.. 그 방법이 쉽지는 않다

 

 

2. 동적 배열

 

자주 길이가 바뀌는 경우, 정적 배열을 사용하고 싶다면, 길이를 아주 충분히 큰 배열로 선언한다면 가능할지도 모른다.

 

하지만 너무 많은 메모리를 낭비하는 것일 수도 있다.

 

이를 해결하기 위해 나온 것이 동적 배열

 

동적 배열은 자유롭게 길이가 줄어들고 늘어날 수 있다.

 

정확히 사용하고 싶은 만큼만 공간메모리를 차지하여 사용하는 방식이다.

 

 

 

삽입, 삭제, 탐색 과정이 모두 정적 배열과 동일하여 시간복잡도가 동일하지만

 

동적배열은 메모리를 필요한 만큼만 사용한다는 차이가 있다.

 

 

3. ArrayList

 

자바에서 동적 배열은 ArrayList라는 클래스를 이용해 표현할 수 있다.

 

사용하는 방법은 import java.util.ArrayList;와 ArrayList<(type)> (name) = new ArrayList<>(); 의 선언이 필요하다.

 

여기서 (type)은 배열 안에 들어갈 원소의 타입을 명시하는 것으로 reference type이어야 한다고 함

 

예를 들어 정수형 동적 배열은 다음과 같이 만들 수 있다.

 

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList<>();
    }
}

 

 

4. 핵심 메소드

 

자주 사용되는 메소드는 다음과 같다.

 

4-1) add(E)

 

ArrayList의 맨 뒤에 데이터 E를 추가한다.

 

python의 append겠네

 

 

4-2) size()

 

현재 ArrayList에 들어있는 데이터의 수를 반환

 

python의 len()이겠네요

 

 

4-3) remove(index)

 

index 위치에 있는 원소를 삭제한다.

 

첫번째 원소의 경우 remove(0), 맨 뒤에 있는 원소를 삭제할려면 remove((name).size()-1)

 

 

4-4) get(index)

 

index 위치에 있는 원소를 조회

 

package array;

import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		
		//정수를 관리할 ArrayList를 선언
		ArrayList<Integer> v = new ArrayList<>();
		
		//v = [5]
		v.add(5);
		
		System.out.println("v에 들어있는 원소의 수: " + v.size());
		System.out.println("v[0]: " + v.get(0));
		
		//v = [5,2]
		v.add(2);
		
		//v = [5,2,9]
		v.add(9);
		
		System.out.println("v[1]: "+v.get(1));
		System.out.println("v[2]: " + v.get(2));
		
		//존재하지 않는다.
		//System.out.println("v[3]: " + v.get(3));
		
		//ArrayList내 원소를 순회하기 위해 v.size()와 for문을 이용
		for(int i = 0; i<v.size(); i++) {
			System.out.println(v.get(i));
		}
		
		System.out.println("###################");
		
		//맨 뒤에 있는 원소 삭제
		v.remove(v.size() - 1);
		
		// 들어 있는 원소의 수
		System.out.println(v.size());
		
		System.out.println("###################");
		
		//출력
		for(int i = 0; i < v.size(); i++) {
			System.out.println(v.get(i));
		}
	}

}

v에 들어있는 원소의 수: 1
v[0]: 5
v[1]: 2
v[2]: 9
5
2
9
###################
2
###################
5
2

 

 

5. Collection

 

자바에서는 ArrayList, Stack, Queue, Deque 등의 자료구조들을 사용할 수 있다.

 

이는 java에서 미리 이런 자료구조를 사용할 수 있도록 Collection으로 만들어 놓아서 그렇다.

 

이렇게 Collection으로 정의된 자료구조를 컨테이너라고 부른다.

 

컨테이너 내의 원소들을 순회하기 위해 iterator라는 이름의 반복자를 사용하기도 한다.

 

 

6. iterator

 

import java.Iterator;와 Iterator<(type)> (name) = (컨테이너 이름).iterator();로 선언

 

정수값을 원소로 하는 ArrayList v를 조회하기 위한 iterator는...

 

ArrayList<Integer> v = new ArrayList<>();
Iterator<Integer> iterator = v.iterator();

 

iterator에 이용되는 핵심 메소드는 iterator.next()와 iterator.hasNext()이다.

 

한칸씩 전진하며 다음 원소를 살피는 메소드는 iterator.next()

 

다음 값이 남아있는지 미리 확인하는 iterator.hasNext()

 

여기서 next()는 위치 이동하기 전에 현재 원소 값을 반환하는 역할을 한다.

 

iterator를 이용해 모든 원소를 순회하는 코드는..

 

package array;

import java.util.ArrayList;
import java.util.Iterator;

public class Main2 {
	public static void main(String[] args) {
		ArrayList<Integer> v = new ArrayList<>();
		
		v.add(5);
		v.add(2);
		v.add(9);
		
		//Iterator로 원소 순회하기
		Iterator<Integer> iterator = v.iterator();
		
		//다음 위치의 원소가 남아있는가?
		while(iterator.hasNext()) {
			//현재 위치의 원소 반환
			Integer num = iterator.next();
			System.out.println(num);
		}
	}
}

5
2
9

 

 

7. 연습문제

 

동적 배열을 이용해 다음 쿼리를 수행하는 프로그램 작성

 

push_back A: 정수 A를 동적 배열의 맨 뒤에 넣는 연산

 

pop_back: 맨 뒤에 있는 정수를 하나 삭제

 

size: 동적 배열에 들어있는 정수의 개수 출력

 

get k: k번째 숫자를 출력

 

여기서 핵심은...

 

1) 문자열 입력받기: sc.next();

 

2) 문자열끼리 비교할 때는 a.equals(b);로 해줘야한다.

 

지금 q == "push_back"하면 q가 push_back이 들어있음에도 false라고 나오더라

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

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

        for(int i = 1; i <= n; i++){
            
            String q = sc.next();

            if(q.equals("push_back")){

                int a = sc.nextInt();
                array.add(a);
            } else if (q.equals("pop_back")){

                array.remove(array.size()-1);
            } else if (q.equals("size")){
                System.out.println(array.size());
            } else {
                int k = sc.nextInt();

                System.out.println(array.get(k-1));
            }
        }
    }
}