ArrayList (+ Iterator , Comparator) [Java Collection 구현하기]

kungfugay 2025. 1. 21. 00:40

2025. 1. 21. 00:40

*참고: Java SE 17 기준 API Docs

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayList.html#method-summary

Field

elementData : 내부적으로 요소를 저장하기 위한 배열
size : 현재 ArrayList에 저장된 요소의 수
~~modCount~~

Constructor

ArrayList(): 기본 생성자 - 초기 용량 10
ArrayList(int initialCapacity) : 입력값으로 초기 용량 설정

Method

CRUD	추가(add)	boolean add(E e): 리스트의 끝에 요소를 추가합니다. ~~void add(int index, E element): 지정한 위치에 요소를 추가합니다.~~	O(1) 단, 용량 초과시 O(n)
	접근(get)	E get(int index): 지정한 인덱스의 요소 반환	O(1)
	수정(set)	E set(int index, E e): 지정한 인덱스의 요소를 새로 수정
	제거(remove)	~~boolean remove(Object o): 지정한 요소를 제거합니다.~~ E remove(int index): 지정한 인덱스의 요소를 제거하고 반환합니다.	O(n) 제거 후 요소 이동 필요
기타	크기 반환	int size(): 리스트에 저장된 요소의 수를 반환합니다.
		boolean isEmpty()
		~~boolean contains(Object o): 리스트에 지정한 요소가 포함되어 있는지 확인합니다.~~
오버라이드 메소드		String toString()
오버라이드 메소드		Iterator<E> iterator()

Field

// Field
private Object[] elementData;   // 내부적으로 요소를 저장하기 위한 배열
private int size;               // 현재 ArrayList에 저장된 요소의 수
private int arraySize = 10;     // default값 10

Constructor

// 기본 생성자 - 초기 용량 10
public __ArrayList() {
    elementData = new Object[arraySize]; //
}

// 커스텀 생성자 - 입력값으로 초기 용량 설정
public __ArrayList(int initialCapacity) {
    this.arraySize = initialCapacity;   // arraySize 초기화
    elementData = new Object[initialCapacity];
}

boolean add(E e)

// C - add
public boolean add(E e) {
    // Case 1 : elementData 배열에 빈 공간이 있다면
    if (size < arraySize) {
        elementData[size] = e;
        size++;
        return true;
    }

    // Case 2 : 배열에 남은 공간이 없다면
    // (1) 배열 크기 2배로 확장
    arraySize *= 2;

    // (2) 기존 요소 옮겨 담기
    Object[] tempArr = new Object[arraySize]; // 옮겨 담을 어레이
    for (int i=0; i<size; i++) {    // 반복 조건: 현재 존재하는 요소 개수만큼
        tempArr[i] = elementData[i];
    }

    // (3) 그 다음 위치에 새 요소 삽입
    tempArr[size] = e;  // 첫번째 실행이라면 10번째에 넣고
    size++;             // 그 다음부터 11번째, 12번째 ...

    // (4) 새로운 배열을 elementData로 설정
    elementData = tempArr;
    return true;
}

E get(int index)

// R - get
public E get(int index) {
    // 인덱스 범위 검사
    if(index < 0 || index >= size) {
        throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
    }
    // 반환 (Object -> 제네릭 타입으로)
    return (E)elementData[index];
}

E set(int index, E e)

// U - set
public E set(int index, E e) {
    // 인덱스 범위 검사
    if(index < 0 || index >= size) {
        throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
    }

    // 반환할 E: 수정되기 전의 요소
    E prev = (E) elementData[index]; // 임시저장

    // 새로운 E로 해당 인덱스의 값 수정
    elementData[index] = e;

    // 반환
    return prev;
}

E remove(int index)

// D - remove
public E remove(int index) {
    // 인덱스 범위 검사
    if(index < 0 || index >= size) {
        throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
    }

    // 삭제될 타겟 요소 임시 저장
    E prev = (E) elementData[index];

    // 인덱스 땡겨주기
    for (int i = index; i< size -1; i++) {
        elementData[i] = elementData[i+1];  // 덮어쓰기
    }

    elementData[size-1] = null; // 맨 마지막 요소는 수동으로 삭제
    size--;     // 전체 요소 크기 줄여주기

    return prev;    // 삭제된 요소 반환
}

Iterator<E> iterator()

// Iterable 인터페이스 - 메소드 구현
@Override
public Iterator<E> iterator() {
    // 익명클래스 방식
    return new Iterator<E>() {
        private int pointer;

        @Override
        public boolean hasNext() {
            return pointer < size();
        }

        @Override
        public E next() {
            E e = get(pointer);
            pointer++;
            return e;
        }
    };
}

전체 코드

import java.util.Arrays;
import java.util.Iterator;

public class __ArrayList<E> implements Iterable<E> {
    // Field
    private Object[] elementData;   // 내부적으로 요소를 저장하기 위한 배열
    private int size;               // 현재 ArrayList에 저장된 요소의 수
    private int arraySize = 10;     // default값 10

    // 기본 생성자 - 초기 용량 10
    public __ArrayList() {
        elementData = new Object[arraySize]; //
    }

    // 커스텀 생성자 - 입력값으로 초기 용량 설정
    public __ArrayList(int initialCapacity) {
        this.arraySize = initialCapacity;   // arraySize 초기화
        elementData = new Object[initialCapacity];
    }

    // size()
    public int size() {
        return this.size;
    }

    // isEmpty()
    public boolean isEmpty() {
        return this.size == 0;
    }

    // C - add
    public boolean add(E e) {
        // Case 1 : elementData 배열에 빈 공간이 있다면
        if (size < arraySize) {
            elementData[size] = e;
            size++;
            return true;
        }

        // Case 2 : 배열에 남은 공간이 없다면
        // (1) 배열 크기 2배로 확장
        arraySize *= 2;

        // (2) 기존 요소 옮겨 담기
        Object[] tempArr = new Object[arraySize]; // 옮겨 담을 어레이
        for (int i=0; i<size; i++) {    // 반복 조건: 현재 존재하는 요소 개수만큼
            tempArr[i] = elementData[i];
        }

        // (3) 그 다음 위치에 새 요소 삽입
        tempArr[size] = e;  // 첫번째 실행이라면 10번째에 넣고
        size++;             // 그 다음부터 11번째, 12번째 ...

        // (4) 새로운 배열을 elementData로 설정
        elementData = tempArr;
        return true;
    }

    // R - get
    public E get(int index) {
        // 인덱스 범위 검사
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
        }
        // 반환 (Object -> 제네릭 타입으로)
        return (E)elementData[index];
    }

    // U - set
    public E set(int index, E e) {
        // 인덱스 범위 검사
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
        }

        // 반환할 E: 수정되기 전의 요소
        E prev = (E) elementData[index]; // 임시저장

        // 새로운 E로 해당 인덱스의 값 수정
        elementData[index] = e;

        // 반환
        return prev;
    }

    // D - remove
    public E remove(int index) {
        // 인덱스 범위 검사
        if(index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("인덱스의 범위를 벗어났습니다.");
        }

        // 삭제될 타겟 요소 임시 저장
        E prev = (E) elementData[index];

        // 인덱스 땡겨주기
        for (int i = index; i< size -1; i++) {
            elementData[i] = elementData[i+1];  // 덮어쓰기
        }

        elementData[size-1] = null; // 맨 마지막 요소는 수동으로 삭제
        size--;     // 전체 요소 크기 줄여주기

        return prev;    // 삭제된 요소 반환
    }

    // toString
    @Override
    public String toString() {
        return "__ArrayList{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                ", arraySize=" + arraySize +
                '}';
    }

    // Iterable 인터페이스 - 메소드 구현
    @Override
    public Iterator<E> iterator() {
        // 익명클래스 방식
        return new Iterator<E>() {
            private int pointer;

            @Override
            public boolean hasNext() {
                return pointer < size();
            }

            @Override
            public E next() {
                E e = get(pointer);
                pointer++;
                return e;
            }
        };
    }
}

저작자표시 비영리 변경금지 (새창열림)

'Java > Data Structures' 카테고리의 다른 글

Linked List (+ Node, Iterator ) [Java Collection 구현하기] (1)	2025.01.16
[자료구조] Queue (큐) - 배열로 구현 (2)	2025.01.14
[자료구조] Stack (스택) - 배열로 구현 (0)	2025.01.14
[Java] 해쉬맵 HashMap<>() + TreeMap<>() - 컬렉션 자료형 (Collection) (0)	2025.01.13
[Java] ArrayList<>() - 컬렉션 자료형, List, CRUD (0)	2025.01.10

kungfugay's Blog

ArrayList (+ Iterator , Comparator) [Java Collection 구현하기]

Field

Constructor

Method

'Java > Data Structures' 카테고리의 다른 글

+ Recent posts

티스토리툴바