자바 자료구조 구현 - 배열, ArrayList(리스트)

배열(배열 크기 정적 구현)

public class Test {	
	public static void main(String[] args) {
		
		int[] arr = {0, 0, 0};
		int[] arr = new int[3];
		
		// 두줄의 결과값이 동일하다. 	
        
        //관련 메소드 3가지 
        System.out.println(arr.length); // 1, ArrayList의 원소 개수를 반환하는 메소드 
		Arrays.sort(arr); // Array의 모든 데이터를 정렬
		// 정렬 대상외의 다른 인수를 추가하지 않으면 오름차순으로 정렬함, 
		// 특정 범위의 데이터만 정렬할 시, from, to 인덱스를 지정할 수 있음 
        
        // 배열의 모든 데이터를 String으로 반환하는 메서드
		System.out.println(Arrays.toString(arr)); 
        
	}
}

 

배열 사용시 시간 복잡도

*배열 데이터에 접근하기 위한 시간 복잡도는 O(1)

*배열에 데이터를 추가할 경우 

    1. 맨 뒤에 삽입할 경우 시간복잡도 : 맨 뒤에 임의 접근이 가능하고, 다른 데이터에 영향을 주지 않음, O(1)

    2. 맨 앞에 삽입할 경우 시간복잡도 : 기존 데이터들을 한칸씩 뒤로 미는 연산 필요함, 밀어야하는 데이터의 개수가 N이면,  O(N)

    3. 중간에 삽입할 경우 시간복잡도 : 삽입한 데이터 이후의 값들을 모두 한칸씩 뒤로 미는 연산 필요, 밀어야하는 데이터의 개수가 N이면,  O(N)

 

배열 사용시 고려할점 

임의 접근이 가능하여 빠르게 접근할 수 있지만, 이를 위해 충분한 메모리 공간이 필요함. 

배열의 중간이나 맨앞에 데이터 삽입이 많은지 확인해야함. 

 

ArrayList(배열 크기 동적 구현)

package Mar0308;

import java.util.ArrayList;
import java.util.Collections;

public class Test {	

	public static void main(String[] args) {
		
		ArrayList<Integer> list = new ArrayList<>();
		
		list.add(0); 
		list.add(1); // 리스트의 끝에 값 추가 
		
		
		// 다른 컬렉션을 통한 초기화 
		
		ArrayList<Integer> list2 = new ArrayList<Integer>(list);
		System.out.println(list2); //[0, 1]
		
		// 인덱스를 통한 접근
		System.out.println(list2.get(0)); // 0
		
		// 데이터 삭제
		list.remove(list.size() -1); // 마지막 데이터 삭제 
		System.out.println(list); // [0]
		
		// 관련 메소드 3가지 
		
		System.out.println(list.size()); // 1, ArrayList의 원소 개수를 반환하는 메소드 
		System.out.println(list.isEmpty()); // false, ArrayList에 저장된 데이터가 하나도 없는지 여부를 반환하는 메소드 
		Collections.sort(list); // ArrayList의 모든 데이터를 정렬
		// 정렬 대상외의 다른 인수를 추가하지 않으면 오름차순으로 정렬함, 
		// 특정 범위의 데이터만 정렬할 시, from, to 인덱스를 지정할 수 있음 
		System.out.println(list); 
		
	}

}