배열을 이용한 리스트 구현

배열을 이용한 리스트 구현

code

import java.util.NoSuchElementException;

public class ArrayList{

    static class List<E> {
        private E a[]; // 리스트의 항목들을 저장할 배열
        private int size; // 리스트의 항목 수

        // 생성자
        public List() {
            a = (E[]) new Object[1]; // 최초로 1개의 원소를 가진 배열 생성
            size = 0; // 항목 수를 0으로 초기화
        }

        // 리스트가 empty이면 true 리턴
        public boolean isEmpty() {
            return size == 0;
        }

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

        // 새 항목을 k-1번쨰 항목 다음에 삽입
        public void insert(E newItem, int k) {
            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번째 항목 삭제
        public E delete(int k) {
            // underflow 경우에 프로그램 정지
            if (isEmpty())
                throw new NoSuchElementException();

            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만 차지한다면
                resize(a.length / 2); // 배열을 1/2 크기로 축소
            return item;
        }

        // k번째 항목을 리턴, 단순히 읽기만 한다.
        public E peek(int k) {
            // underflow 경우에 프로그램 정지
            if (isEmpty())
                throw new NoSuchElementException();
            return a[k];
        }

        // 배열 크기 조절
        private void resize(int newSize) {
            Object[] t = new Object[newSize]; // newSize 크기의 새로운 배열 t 생성

            for (int i = 0; i < size; i++)
                t[i] = a[i]; // 배열 s를 배열 t로 복사

            a = (E[]) t; // 배열 t를 배열 s로
        }

        // 배열의 항목들을 출력
        public void print() {
            if (isEmpty())
                System.out.print("배열이 비어있음.");
            else
                for (int i = 0; i < a.length; i++)
                    System.out.print(a[i] + "\t ");
            System.out.println();
        }

    }

    public static void main(String[] args) {
        // TO-DO
    }

}

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)