선형 자료구조

Array

• 배열은 선언 시 배열의 길이를 지정해야 한다.
  • 배열 생성 후 길이를 변경하는 것은 불가능하다. (새 배열 만들어서 복사해야함)
• 배열은 연속된 메모리에 저장된다.

위의 그림처럼 배열은 생성 시 길이를 지정하기 때문에 연속된 메모리를 할당할 수 있다. 연속적이기 때문에 각 요소의 위치를 특정할 수 있다. 그래서 인덱스를 이용한 랜덤한 값에 대한 접근의 시간 복잡도가 O(1)이다.

 

하지만 그렇기 때문에 데이터의 삽입/삭제에는 불리하다. 배열 중간에 요소를 삽입하려면 뒤의 요소들이 한 칸씩 이동해야하기 때문이다. 삭제의 경우도 마찬가지다.

 

그래서 배열은 읽기에는 특화되어있지만 길이를 조정할 수 없고 삽입/삭제의 성능이 떨어지므로 읽기 성능이 중요한 구현에서 사용하면 좋을듯하다.

ArrayList

ArrayList는 배열처럼 빠른 읽기도 가능하고 list의 길이도 변경이 가능하다. 어떻게 가능한 것일까?

우선 ArrayList는 기본적으로 Object[]로 이루어져있다. 즉, 배열이다.

그런데 어떻게 길이를 변경할 수 있다는거지?

 

답을 먼저 말하자면 Object[]에 요소가 가득차면 자동적으로 새로운 배열(당연히 기존의 Object[]보다 길어야한다.)을 생성하여 기존의 값을 복사하여서 사용한다. ArrayList는 배열을 사용하지만 필요시 새로운 배열을 생성하고 복사하는 과정을 대신해주기 때문에 길이가 자유자재로 늘어나는 것처럼 보인다.

ArrayList.java

public class ArrayList<E> extends ... {

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    ...

    public ArrayList() {  
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }

    ...
}

ArrayList를 생성하면 빈 Object[]을 할당하는 모습을 볼 수 있다.
여기서 하나의 값을 add(e) 했다고 가정해보자.

public class ArrayList<E> extends ... {

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    private int size;

    ...


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

    public boolean add(E e) {  
        modCount++;  
        add(e, elementData, size);  
        return true;}
    }
    ...
}

add 메서드에서 s와 elementData.length를 비교하는 조건이 등장한다.
size는 선언한 적이 없으니 기본값인 0일 것이고 elementData역시 전의 코드에서 빈 Object[]을 할당받았으므로 length는 이다. 고로, ArrayList를 생성하고 처음 값을 add하는 경우에는 if문에 입장해서 grow메서드를 실행하게 된다.

public class ArrayList<E> extends ... {

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    private int size;

    ...

    private Object[] grow(int minCapacity) {  
        int oldCapacity = elementData.length;  
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
            int newCapacity = ArraysSupport.newLength(oldCapacity,  
                    minCapacity - oldCapacity, /* minimum growth */  
                    oldCapacity >> 1           /* preferred growth */);  
            return elementData = Arrays.copyOf(elementData, newCapacity);  
        } else {  
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];  
        }  
    }  

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

    ...
}

grow(size + 1)로 메서드를 호출한다. 현재 minCapacity = 1
여기서는 두 가지 경우로 분기된다.

• 배열의 길이 == 0인 경우 (else)
  • DEFAULT_CAPACITY와 size 중 큰 값의 크기로 배열이 생성된다. DEFAULT_CAPACITY은 10이므로 기본적으로 크기가 10인 배열이 생성된다.
• 그 외의 경우 (if)
  • ArraysSupport.newLength메서드에서 새로운 길이를 산정한다.
  • Arrays.copyOf에서 계산된 길이의 크기의 배열에 기존의 배열을 복사한다.

 

정리하자면 ArrayList는 길이를 자동적으로 늘려주는 배열이다.
그렇기에 읽기 성능은 빠르고 삽입/삭제의 성능은 느린 배열의 특징을 그대로 공유하고 있다.

Stack

stack도 ArrayList와 비슷한 로직을 가지고 작동된다. Stack에 필요한 push와 pop같은 메서드를 구현한 것 외에는 동작 방식은 같다.

LinkedList

• 비연속적으로 메모리에 저장된다.
• 각각의 요소는 노드라는 형태로 저장되는데 노드에는 이전노드, 데이터, 다음노드의 정보가 담겨져있다.
• 읽기가 느리다. (인덱스 사용 불가)
  • 데이터를 찾기 위해서 첫 노드부터 원하는 위치까지 순차적으로 이동해야한다.
• 삽입과 수정은 빠르다.
  • 기존의 노드를 제거하고 새로운 노드에 이전, 이후 노드의 정보를 매핑하면 끝나기 때문이다.

LinkedList.java

public class LinkedList<E> extends ... {

    transient int size = 0;  

    transient Node<E> first;  

    transient Node<E> last;

    public LinkedList() {  
    }

    ...

}

처음 LinkedList를 생성하면 아무런 로직이 없다.

public class LinkedList<E> extends ... {

    transient int size = 0;  

    transient Node<E> first;  

    transient Node<E> last;

    ...

    public boolean add(E e) {  
        linkLast(e);  
        return true;
    }

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

    ...

    private static class Node<E> {  
        E item;  
        Node<E> next;  
        Node<E> prev;  

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

    ...

}

마찬가지로 add를 해보겠다. 그러면 linkLast 메서드로 이동한다.

• Node 클래스는 LinkedList의 inner class로 존재한다.
• l에 last를 입력한다.
  • 생성 후 처음으로 add를 하는 경우는 l은 null이다.
• 이전 노드, 데이터, 다음 노드를 입력하여 새로운 노드를 생성한다.
• l == null인 경우 (처음 데이터 입력)
  • 새로운 노드를 first로 지정
• 그 외의 경우
  • 이전 노드의 next 필드에 생성된 노드 입력
    • 생성된 노드에서 next값은 기본적으로 null이 들어간다. 왜냐하면 다음 노드를 만들어야지 next노드를 입력할 수 있기 때문이다. 그렇기에 이전 노드의 next 필드에 생성된 노드를 넣어주는 것이다.

 

배열과 반대로 읽기 성능은 느리지만 삽입/삭제의 성능은 빠르다.

Queue

자바에서 Queue를 구현하기 위해서는 Queue 인터페이스를 구현받으면 된다. LinkedList는 Queue를 구현하고 있기 때문에 LinkedList로 Queue를 사용할 수 있다.

• 입력은 똑같이 add 사용
• 가장 앞의 데이터를 뽑는 메서드는 poll 사용