2. 리스트 -배열(Array List)

1. ArrayList 구현 (JAVA)

Java가 익숙치 않아서 조금 어려움이 있지만 주석을 달면서 개념을 이해해 가보자! 

package list;

import java.util.Arrays;

public class MyArrayList<T> implements IList<T> {
    private static final int DEFAULT_SIZE = 50; 

    private int size;      // 배열안에 들어가 있는 데이터 사이즈, 인덱스 역할 변수
    private T[] elements;  // 삽입할 데이터 변수 T[]은 임의의 데이터 유형을 받을 수 있도록함

    public MyArrayList() {                          // 배열리스트 생성자 만들기
        this.size = 0;
        this.elements = (T[]) new Object[DEFAULT_SIZE];  // 배열 생성시에는 size를 지정해줘야 하기 때문에 Default 값을 넣어준다
    }

    @Override
    public void add(T t) {                     // 배열에 데이터(t)를 배열 맨 끝에 추가한가
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.size * 2);  // 데이터가 배열의 사이즈를 넘어가면 배열의 크기를 2배로 늘려준다
        }                                                                 // 사이즈를 키우고 기존에 elements에 있던 데이터를 옮긴다
        this.elements[size++] = t;  // this.elements[this.size] = t; this.size += 1; 와 동일한 동작
    }                               // 맨처음 0 번째 데이터 넣고 다음에는 사이즈가 1로 바뀌었기 때문에 그 다음 인덱스에 데이터를 넣을 수 있게 한다

    @Override
    public void insert(int index, T t) {    // 우리가 정한 인덱스에 데이터(t)를 집어 넣는다
                                            // 넣으려는 인덱스에 이미 데이터가 있으면 거기부터 전체적으로 한 칸씩 뒤로 밀어준 뒤 삽입한다
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.size * 2);
        }
        for (int i = index; i < this.size; i++) {  // 한칸 씩 데이터를 뒤로 밀어주는 동작
            this.elements[i+1] = this.elements[i];
        }
        this.elements[index] = t;                  // 데이터 삽입
        this.size++;                               // 데이터 크기 +1
    }

    @Override
    public void clear() {               // 배열안에 데이터를 모두 비워주는 작업
        this.size = 0;                  // 생성자 처럼 초기화
        this.elements = (T[]) new Object[DEFAULT_SIZE];
    }

    @Override
    public boolean delete(T t) {    // 삭제하려는 데이터(t)를 찾아서 삭제해주고 그 위치에서 뒤에 데이터들을 앞으로 당겨주는 동작 
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) {       // 데이터가 파라미터로 들어온 (t)와 동일하다면
                for (int j = i; j < this.size -1; j++) {    // 뒤의 인덱스 데이터로 덮어쓰기
                    this.elements[j] = this.elements[j+1];
                }
                this.size--;
                return true;
            }
        }
        return false;                   // 일치하는 데이터가 없다면 false 반환
    }

    @Override
    public boolean deleteByIndex(int index) {  // 삭제하려는 index위치의 데이터를 삭제하고 그 뒤의 데이터를 앞으로 당겨주는 동작
        if (index < 0 || index > this.size - 1) {  // 잘못된 인덱스 입력 시의 오류 처리 (Boolean 이니까 false로)
            return false;
        }
        for (int i = index; i < this.size-1; i++) { // 삭제하려는 인덱스를 뒤에 데이터로 덮어써버리고 
            this.elements[i] = this.elements[i+1];
        }
        this.size--;                                // 데이터 사이즈 -1 
        return true;
    }

    @Override
    public T get(int index) {                   // 인덱스 위치의 데이터를 가져오는 동작
        if (this.size <= index) {
            throw new IndexOutOfBoundsException();  // 잘못된 인덱스 입력 시의 오류 처리
        }
        return this.elements[index];
    }

    @Override
    public int indexOf(T t) {                   // 파라미터로 받은 데이터 t()가 배열안에 있으면 해당 인덱스 반환 없으면 -1 반환
        for(int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {              // 배열에 데이터가 들어가 있는지 아닌지 반환
        return this.size == 0;
    }

    @Override
    public boolean contains(T t) {              // 파라미터로 받은 데이터 t()가 배열안에 있으면 true 없으면 false를 주는 동작
        for(T elem : this.elements) {
            if (elem.equals(t)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int size() {                     // 배열의 데이터 사이즈 반환
        return this.size;
    }
}

---

2. ArrayList 구현 (Python)

class ArrayList:
    def __init__(self, size=10):
        self.max_size = size # maximum memory capacity
        self.list = [None] * self.max_size # allocate array
        self.size = 0 # current actual size (number of elements)

    def add(self, value):
        if self.size >= self.max_size: # check if enough memory capacity
            self._increase_size()
        self.list[self.size] = value
        self.size += 1

    def _increase_size(self):
        new_max_size = self.max_size * 2 # double memory size
        new_list = [None] * new_max_size
        for i in range(0, self.max_size): # copy old list to new list
            new_list[i] = self.list[i]
        self.max_size = new_max_size
        self.list = new_list

    def get(self, index):
        if index >= self.size or index < 0:
            raise Exception('Invalid index')

        return self.list[index]

    def delete(self, index):
        if index >= self.size or index < 0:
            raise Exception('Invalid index')

        # shift list from deleted index onwards
        # element before index are not affected by deletion
        for i in range(index, self.size): 
            self.list[index] = self.list[index+1]

        self.size -= 1