[Java] 배열(Array)

 

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다.

 

 

 

 

 

 

 

 

배열(Array)

 

• 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조
• 특정 원소에 접근할 때에는 배열의 인덱스로 O(1) 시간에 접근
• 새 항목을 배열 중간에 삽입하거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 1칸씩 뒤로 또는 앞으로 이동 : O(n) 시간

 

 

 

 

 

 

 

• a는 배열 이름인 동시에 배열의 첫번째 원소의 레퍼런스를 저장
• a[i]는 인덱스 i를 가지는 원소를 가리키는 레퍼런스
• a[i]는 a가 가지고 있는 레퍼런스에 원소의 크기(Byte). * i 를 더하여 a[i]의 레퍼런스를 계산
  • a[i] = a + (원소의 크기 * i)
  • char 배열 : 2 bytres
  • int 배열 : 4 bytes

 

 

Overflow

 

• 배열은 미리 정해진 크기의 메로리 공간을 할당 받아 사용해야 한다. 빈자리가 없으면 새 항목을 삽입할 수 없는 상황(Overflow) 발생
• Overflow가 발생하면 에러 처리를 하여 프로그램 정지. 하지만 프로그램의 안정성을 향상시키기 위해 아래와 같은 아이디어를 적용한다.
•  

배열에 overflow가 발생하면 배열 크기를 2배로 확장. 만일 배열의 3/4이 비어있으면 배열 크기를 1/2로 축소

 

 

<Java 구현>

 

ArrList class에서 리스트를 배열로 구현해보자.

import java.util.NoSuchElementException;
public class ArrList <E> {					//리스트의 항목들을 저장할 배열
	private E a[];						// 리스트의 항목 수
    private int size;						// 생성자
    public ArrList() {						// 최초로 1개의 원소를 가진 배열 생성
    	a = (E[]) new Object[1];				// 항목 수를 0으로 초기화
        size = 0;
    }
    // 탐색, 삽입, 삭제 연산을 위한 메소드 선언
}

 

** Java 문법

Stack을 이용할 때에는 util 라이브러리 중 EmptyStackException을 불러올 수 있지만, 그 외에는 일반적으로 NoSuchElementException을 불러온다.

 

 

 

 

 

필요한 method를 하나씩 구현해보자.

 

peek(k) 메서드

public E peek(int k) {
	if (size == 0)
		throw new NoSuchElementException();		// underflow 경우 프로그램 정지
	return a[k];
    }

 

• 이 메서드는 k번째 항목을 반환한다. 단순히 읽기만을 수행한다.
• k 번째를 peek, 반환하고 싶은데 항목 수가 0 즉, 비어잇다면 오류를 발생시킨다.
• 아니면 k 번 인덱스의 값을 반환한다.

 

 

 

insertLast()

public void insertLast(E newItem) {				// 가장 뒤에 새 항목 삽입
	if (size == a.length)					// 배열에 빈 공간이 없으면
		resize(2*a.length);				// 배열 크기 2배 확장
	a[size++] = newIemt;					// 새 항목 삽입
}

 

 

• 새 항목(newItem)을 맨 뒤에 삽입한다.
• 맨 뒤에 삽입하려는 데 항목 수가 길이랑 일치하면 2배로 늘리고 새 데이터를 뒤에 집어넣는다.

 

 

 

 

 

 

 

insert()

public void insert(E newItem, iont k) {					// 새 항목을 k-1번째 항목 다음에 삽입
	if (size == a.length)						// 배열에 빈 공간 없으면
		resize(2*a.length);					// 배열 크기 2배로 확장
	for ( int i = size-1; i >= k; i--) a[i+1] = a[i]; 		// 한 칸씩 뒤로 이동
	a[k] = newItem;
	size++;
}

 

 

• 새 항목을 k -1번째 항목 다음에 삽입.
• 메모리 관점에서 삽입되는 원리를 설명하면 아래 그림을 참고하자.

 

 

 

 

 

resize()

private void resize(int newSize) {					// 배열 크기 조절
	Objectr[] t = new Object[newSize];				// newSize 크기의 새로운 배열 t 생성
	for (int i = 0; i < size; i++)
		t[i] = a[i];						// 배열 a를 배열 t로 복사
	a = (E[]) t;							// 배열 t를 배열 a로
}

 

• 배열의 크기를 확대 / 축소

 

 

 

 

 

 

delete(k)

• k번째 삭제

public E delete(int k) {
	if (isEmpty()) throw new NoSuchElementException();	// underflow 경우에 프로그램 정지
	E item = a[k];
	for (int i = k; i < size; i++) a[i] = a[i+1];		// 한 칸씩 앞으로 이동
	size--;
	if (size > 0 && size == a.length/4)			// 배열에 항목들이 1/4만 차지한다면
		size(a.length/2);				// 배열을 1/2 크기로 축소
	return item;

 

 

메모리 관점

 

 

 

 

 

1. 삭제된 원소의 공간 메우기
2. 배열의 크기 축소

 

main class

public class main {
	public static void main(Stirng[] args) {
        ArrList<String> s = new ArrList<String>();
        s.insert("apple"); s.print(); s.insert("orange"); s.print();
        s.insert("cherry"); s.print(); s.insert("pear"); s.print();
        s.insert("grape", 1); s.print(); s.insert("lemon", 4); s.print();
        s.insert("kiwi"); s.print();
        s.delete(4); s.print(); s.delete(0); s.print();
        s.delete(0); s.print(); s.delete(3); s.print();
        s.delete(0); s.print();

        System.out.println("1번째 항목은 "+s.peek(1)+"이다."); System.out.println();
	}
}

 

 

 

출력 결과 예시

 

 

 

 

 

 

배열의 수행 시간

• peek()는 인덱스를 이용하여 배열 원소를 직접 접근 : O(1)
  • 바로 접근하기 때문에 O(n)이 아닌 O(1)
• 삽입 / 삭제는 새 항목을 중간에 삽입하거나 삭제한 후에 뒤따르는 항목들을 1칸씩 앞이나 뒤로 이동 : O(n)
  • Upper bound이기 때문에 O(n)
• 맨 뒤에 새 항목 삽입 : O(1)
• 배열의 크기 확대 / 축소 : O(n)
  • overflow 이런아서 2배로 늘리다면 O(n)
• 상각 분석에 따르면 연속적인 삽입 / 삭제의 평균 수행 시간 :O(1)