[Java] ArrayList, LinkedList를 직접 구현해보며 이해한 것

0. 들어가기 전

우테코에서 미니 미션으로 '리스트 구현하기'를 시켰다.

ArrayList, LinkedList 두 개를 직접 구현해보는 것이었는데, 처음 해보는 것이라서 신선했다.

 

가끔씩 모르는 메소드, 클래스들이 나오면 그 클래스를 들어가서 직접 코드를 뜯어보기 때문에

코드를 들어가보는 것에는 익숙했지만,

그래도 단순히 사용하기만 했었던 ArrayList, LinkedList를 직접 구현해야한다니 막막했다.

 

게다가 LinkedList는 어떤 원리인지도 자세히 알지 못했고 많이 사용해본 적도 없어서 더 막막했던 것 같다.

 

직접 구현한 코드들은 거의 ArrayList, LinkedList를 복붙한 내용이라서 자세하게는 기록하지 않고

미션을 진행하면서 내가 이해한 점들을 기록해보고자 한다.

(내가 코드를 보고 한 이해이기 때문에 잘못된 이해일 수도 있다 😭)

---

1. ArrayList

 

1-1. add 메소드

원래는 add 메소드를 실행했을 때 ArrayList의 '크기'에 관한 부분은 생각지도 않고 썼었다.

 

이번에 직접 구현해야 했기 때문에 add 시에 ArrayList의 '크기'를 처음으로 생각해봤을 때

당연히 1개의 요소가 추가로 들어가기 때문에 1개의 크기만 늘어나는 느낌으로 생각했었다.

 

직접 구현한 아래의 코드를 보면서 크기가 어떻게 늘어나는지 살펴보자!

(직접 구현했다고 했지만 사실 ArrayList 코드 복붙임 😄)

private void add(String value, String[] elementData, int s) {
    if (size == elementData.length) {
        elementData = grow();
    }
    elementData[s] = value;
    size = s + 1;
}

private String[] grow() {
    return grow(size + 1);
}

private String[] grow(int expandCapacity) {
    elementData = Arrays.copyOf(elementData, newCapacity(expandCapacity));
    return elementData;
}

// 비트 연산자 >> : 비트를 이동시킨다. 12(1100) -> 6(110)로 비트 이동
// 원래 사이즈에 하나씩 오른쪽으로 비트 이동 시킨 값(2분의 1값)을 더한다.
// 12 -> 12 + 6 / 8 -> 8 + 4가 새로운 Capacity
private int newCapacity(int expandCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
	...
    
   	return newCapacity;
}

1. elementData(ArrayList의 배열 요소)를 grow()로 성장? 시킨다.

2. grow()가 호출되면, 현재 사이즈보다 1 큰 값을 grow의 인수로 넘겨준다. - grow(size + 1)

 

3. int 값을 인수로 받는 grow는 Arrays.copyOf로 배열 요소와

새로운 배열 크기를 newCapacity를 호출하여 복사한다.

 

4. 이때, newCapacity()를 보면, 새로운 배열 크기를 계산할 때

oldCapacity + (oldCapacity >> 1)로 지정하고 있다.

 

오른쪽 비트 연산자를 이용하여 1비트 이동하는데, 이렇게 되면 원래 수의 2분의 1이 된다.

따라서 원래 Capacity의 1.5배를 새로운 배열 크기로 지정하게 된다!

(배열의 처음 add 시 크기는 10으로 지정되고, 10보다 큰 사이즈가 들어올 때 1.5배를 지정한다.)

 

※ 코드 예시

ex) 
ArrayList arrayList = new ArrayList();
// ElementData = ArrayList안의 배열, length로 0 출력
// 초기화 후 처음 length는 0이다.
System.out.println(arrayList.getElementData.length); 

// add
arrayList.add("seongHa");
// length로 초기값 10 출력
System.out.println(arrayList.getElementData.length);

arrayList.add("seongHa");
arrayList.add("seongHa");
// 배열 10번째까지 배열 length 10
...
// add 11번 째
arrayList.add("seongHa");
// 배열 초기값 10의 1.5배인 15 출력
System.out.println(arrayList.getElementData.length);

이런 식으로 계속 지정 크기 경계값 이상이 될때 1.5배씩 할당을 한다!

 

 

1-2. remove 메소드

remove도 add와 마찬가지로 사용 시에는 별 생각없이 썼었다.

 

단순히 그냥 '인덱스를 받아서 해당 인덱스의 값을 지워주겠구나~'하고 사용했었는데

이번에 구현 시에 생각해보니 값을 지운 인덱스가 비어 있을텐데

해당 인덱스 뒤의 요소들은 앞으로 땡겨야하지 않을까? 라는 생각이 들었다.

 

어떻게 할지 몰라서 ArrayList 코드를 살펴봤는데 다음과 같았다.

public boolean remove(String value) {
    Objects.checkIndex(index, size);
    final String[] es = elementData;

    String oldValue = es[index];
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(String[] elementData, int index) {
    final int newSize;
    newSize = size -1;
    if (newSize > index) {
        // System.arraycopy 인수 
        // 1. 복사하고자 하는 원본
        // 2. 원본에서 읽어올 처음 인덱스 위치
        // 3. 복사본 대상 
        // 4. 어느 부분 데이터 채울지 인덱스
        // 5. 데이터 길이 (원본에서 복사본으로 얼만큼 읽어올지)
        // 지우려는 인덱스 뒤 요소들을 하나씩 앞으로 땡긴다.
        System.arraycopy(elementData, index + 1, elementData, index, newSize - index);
    }
    // 땡긴 후 마지막 인덱스를 null 처리로 지운다.
    size = newSize;
    elementData[size] = null;
}

remove 메소드 안에 있는 fastRemove() 메소드가 핵심이다.

 

Syetem.arraycopy()를 사용하여

해당 ArrayList의 배열의 지우려는 인덱스 뒤의 요소들을 하나씩 앞으로 땡겨서 배열 요소를 바꾼다.

그 후, 배열의 마지막 인덱스는 비어있을 것이므로 null 처리로 지운다.

 

이렇게 제거하려는 인덱스 뒤의 요소들을 앞으로 땡기고 마지막 인덱스를 null 처리하는

remove의 원리를 알게 되었다.

 

또, remove의 반환 값이 oldValue, 즉 지운 값이라는 것도 처음 알게 되었다!

---

2. LinkedList

 

LinkedList는 거의 사용해본 적도 없었어서 많이 생소했다.

자세한 원리를 이해하지는 못했지만 어느정도 이해한 부분을 기록하려고 한다!

 

2-1. LinkedList는 값이 아닌 노드를 가진다.

아래의 코드는 LinkedList가 가지는 필드이다.

public class LinkedList {

    private int size = 0;

    private Node<String> first;

    private Node<String> last;

    private static class Node<String> {

        String item;
        Node<String> next;
        Node<String> prev;

        Node(Node<String> prev, String element, Node<String> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

위의 코드처럼, 필드로 '값'을 가지는 것이 아니라 static class로 정의된 Node를 가진다.

이 부분이 처음에 상당히 이해하기가 어려웠는데,

List안의 Node들이 서로 이전 노드, 다음 노드를 가리키는 구조이다.

 

2-2. 값을 추가할 때(add),  값 추가가 아닌 추가할 값을 가진 노드를 연결한다.

public boolean add(String value) {
    linkLast(value);
    return true;
}

private void linkLast(String value) {
    final Node<String> l = last;
    final Node<String> newNode = new Node<>(l, value, null);
    last = newNode;
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
}

add() 메소드가 호출되면, linkLast() 메소드를 호출하는데

메소드 이름에서도 알 수 있듯이 마지막 노드와 연결하는 기능을 가진다!

 

코드가 처음 봤을 때 상당히 이해하기 어려웠는데,

요약하면 기존 리스트의 last 노드(필드로 가진)의 next와

새로 생성한 추가할 값을 가지고 있는 newNode의 prev를 연결해준다.

 

 

2-3. 값을 가져올 때, 값을 바로 가져오는 것이 아니라 노드를 가리키며 노드 안의 값을 가져온다.

public String get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 해당 인덱스의 노드 탐색하여 반환
private Node<String> node(int index) {
    if (index < (size >> 1)) {
        Node<String> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<String> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

우선, 값을 가져오는 get() 메소드를 보면,

return에서 node(index)로 먼저 node를 가져온 후 해당 node의 item을 반환하는 것을 알 수 있다.

따라서, 먼저 값이 있는 node를 찾고 그 후에 node 안의 값을 반환한다.

 

그렇다면 값이 있는 node는 어떻게 찾는가?

노드를 찾는 node() 메소드를 보면 알 수 있다.

 

for 반복문이 있는 것으로 보아, LinkedList의 노드를 돌면서 해당 인덱스의 노드를 찾는 것을 알 수 있다.

if문으로 다음과 같은 조건으로 탐색하는 것을 알 수 있다.

- index가 size의 절반보다 작거나 같으면
    - first 노드에서 시작해서 next를 계속 탐색해서 해당 index의 노드를 탐색한다.
    
- index가 size의 절반보다 크면
    - last 노드에서 시작해서 prev를 계속 탐색해서 해당 index의 노드를 탐색한다.

 

2-4. 값을 제거할 때, 값을 제거하는 것이 아니라 연결된 노드의 연결을 끊어서 제거한다.

public String remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

// 연결된 링크를 끊는 기능
private String unlink(Node<String> x) {
    final String element = x.item;
    final Node<String> next = x.next;
    final Node<String> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    return element;
}

코드를 보면, unlink()의 파라미터로 연결을 끊을 Node를 받아서

해당 노드의 prev, next를 null로 만들어서 연결을 끊고

마지막에는 값인 item도 null로 만들어서 제거하는 것을 알 수 있다.

---

이렇게 ArrayList, LinkedList를 직접 구현해보면서 이해한 것을 기록해보았다.

모든 메소드를 다 기록하지는 않고 핵심적인 메소드들만 정리해보았다.

 

아직도 깊게는 이해하지 못했고, 그냥 어렴풋이 알 정도로만 이해가 된 것 같지만

그래도 몰랐던 사실들을 알 수 있어서 좋았다.