1. 리스트(1) Array Lists

학교 수업 '자료구조' 복습

리스트란?

• 유한하고 순서가 있는 데이터의 나열
• 리스트 속의 데이터들은 위치 position가 있음
• 표기법 : <a₀, a₁, ... , a𝚗-₁>
• 어떤 연산operation이 필요할까?

필요한 연산

• 특정 위치에 아이템을 넣을(insert, append) 수 있다.
• 특정 위치의 아이템을 읽고(getValue), 변경(update)할 수 있다.
• 특정 위치의 아이템을 삭제(remove)할 수 있다.
• 리스트 내의 아이템 개수(length)를 알 수 있다.
• 리스트를 비울(clear)수 있다.

필요한 연산

배열(Array) 기반 리스트

• 넣기

• 삭제

• 구현

public class arrayList<E> implements List<E> {

    int listSize;
    E[] data;

    public arrayList(int capacity) {
        listSize = 0;
        data = (E[]) new Object[capacity];
    }

    @Override
    public void insert(int pos, E item) {
        for (int i = listSize; i > pos; i--) {
            data[i] = data[i - 1];
        }
        data[pos] = item;
        listSize++;
    }

    @Override
    public void append(E item) {
        insert(listSize, item);

    }

    @Override
    public void update(int pos, E item) {
        data[pos] = item;

    }

    @Override
    public E getValue(int pos) {
        return data[pos];
    }

    @Override
    public E remove(int pos) {
        E ret = data[pos];

        listSize--;

        for (int i = pos; i < listSize; i++) {
            data[i] = data[i + 1];
        }
        return ret;
    }

    @Override
    public int length() {
        return listSize;
    }

    @Override
    public void clear() {
        listSize = 0;
    }
}

• 장점
  특정 위치의 데이터 조회가 빠르다.
• 단점
  데이터의 추가, 삭제 비용이 크다.
  크기가 고정되있다. (넣으려는 데이터가 더 많으면 error, 넣으려는 데이터가 너무 적으면 메모리 낭비...)