[자료구조] 01. 배열 리스트

배열은 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어, 각 항목이 하나의 원소에 저장되는 기본적인 자료구조입니다.

또한 특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1) 시간에 접근할 수 있습니다.

그러나 새 항목이 배열 중간에 삽입되거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 한칸씩 앞뒤로 이동시켜야 하므로, 삽입이나 삭제 연산은 O(N) 으로 볼 수 있습니다.

그러나 삽입이나 삭제 연산 같은 경우 상각분석에 따르면, 평균 수행시간은 O(1) 이라고 하긴 합니다.

 

배열은 미리 정해진 크기의 메모리 공간을 할당 받은 뒤 사용해야 하므로, 자리가 부족한 상황이 생기기도 합니다.

이런 경우 주로 에러 처리를 하여 프로그램을 정지시키는데, 프로그램의 안정성을 향상시키기 위해 공간을 조절하기도 합니다.

프로그램이 실행되는 동안에, 할당된 메모리 공간을 확장하거나 축소하는 배열을 동적 배열이라고 합니다.

 

아래 코드는 배열로 리스트를 구현한 ArrayList 입니다.

import java.util.NoSuchElementException;

public class ArrayList<E> {
	private E arr[];
	private int size;
	
	// 생성자
	public ArrayList()
	{
		// 공간 하나 만들고 사이즈 0으로 초기화
		arr = (E[]) new Object[1];
		size = 0;
	}
	
	// 배열 확장 및 축소
	private void resize(int newSize)
	{
		// 확장된 크기의 공간을 확보 후
		Object t[] = new Object[newSize];
		for(int i = 0 ; i < size ; i++)
		{
			// 기존 원소들 옮겨준 뒤
			t[i] = arr[i];
		}
		System.out.println("resized : " + arr.length + " to " + newSize);
		// 사용하던 위치에 다시 연결
		arr = (E[])t;
	}
	
	// 검색 연산
	public E at(int i)
	{
		// 인덱스 검사 후
		if(i < 0 || i >= size || size == 0)
			throw new NoSuchElementException();
		// 해당 위치 원소를 반환
		return arr[i];
	}
	
	public int length()
	{
		return size;
	}
	
	// 삽입 연산
	public void insert(E item, int k)
	{
		if(size == arr.length)
		{
			resize(size * 2);
		}
		// 해당 위치부터 끝까지
		for(int i = size - 1 ; i >= k ; i--)
		{
			// 뒤로 한칸씩 밀어줌
			arr[i + 1] = arr[i];
		}
		// 해당 위치에 원소 삽입 후 사이즈 갱신
		arr[k] = item;
		size++;
	}
	
	// 삽입 연산
	public void insertBack(E item)
	{
		// 배열의 최대사이즈라면 크기 재조정
		if(size == arr.length)
		{
			resize(arr.length * 2);
		}
		// 마지막 공간에 삽입 및 사이즈 갱신
		arr[size++] = item;
	}
	
	// 삭제 연산
	public E delete(int k)
	{
		if(size == 0) throw new NoSuchElementException();
		
		// 반환해줄 해당 인덱스의 원소 잡음
		E item = arr[k];
		// 위치가 바뀔 원소들을 하나씩 앞으로 당기고 사이즈 갱신
		for(int i = k ; i < size - 1 ; i++)
		{
			arr[i] = arr[i+1];	
		}
		size--;
		// 남는 공간이 너무 많다면 (1 / 4 이하로 사용 중이라면) 배열을 반으로 줄임
		if(size > 0 && size < arr.length / 4)
		{
			resize(arr.length / 2);
		}
		
		// 사용자가 삭제한 원소를 반환
		return item;
	}
	
	@Override
	public String toString() {
		String ret = "";
		for(int i = 0 ; i < size - 1 ; i++)
		{
			ret += arr[i].toString() + " ";
		}
		ret += arr[size-1].toString();
		return ret;
	}
}