[JAVA] 컬렉션프레임워크(CollectionFramework) 2

List 구현체

Vector 와 ArrayList

---

List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 공통적인 특징을 갖는다.

공통점	차이점
List 인터페이스를 구현한다. 저장순서가 유지되고 중복을 허용한다. 데이터의 저장 공간으로 배열을 사용한다.	Vector는 멀티쓰레드에 대한 동기화가 되어 있으나 ArrayList는 그렇지 않다.

 => Vector는 동기화처리 때문에, 성능이 좋지않으므로 사용할때 주의해야 한다.

LinkedList

---

배열은 가장 기본적인 형태의 자료구조로 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(access time)이 가장 빠르다는 장점을 가지고 있다.

하지만 !! 아래와 같은 단점이 존재한다.

1. 크기를 변경할 수 없다.

크기가 넘으면 새로운 배열을 생성하여 데이터를 복사하는 작업이 필요

실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하므로 메모리가 낭비된다.

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,

중간의 데이터를 추가하려면, 빈자리를 만들기 위해 그 뒤의 데이터들을 복사하여 이동해야한다. 

LinkedList는 이러한 단점을 보완하기 위하여 나온 자료구조로

불연속적으로 존재하는 데이터를 연결(link)한 형태로 구성되어 있다.

각 요소들은 자신과 연결된 다음 요소에 대한 참조를 갖고있다.

ArrayList와 LinkedList 비교

ArrayList는 사이즈가 고정되어 있기 때문에 삽입 시 사이즈를 늘려주는 연산이 추가되어야 하고 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기 때문에 채워주는 연산이 추가적으로 발생한다.

이런 부가적인 연산은 시스템의 성능 저하로 이어지기 때문에 삽입/삭제가 빈번하게 발생하는 프로세스의 경우 치명적이다. 그리고 자료들이 지속적으로 사제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 된다.

하지만 LinkedList는 이러한 문제를 연결형태로 해결하여 ArrayList에서 뒤로 밀거나 채우는 작업 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이 합니다. 따라서 이렇게 삽입/삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는 것이 바람직하다.

하지만, LinkdList의 단점도 존재한다. ArrayList에서는 무작위 접근(random access)가 가능하지만, LinkedList는 순차접근(sequential access)만이 가능하다.

n 개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다. 그렇기 때문에 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다 긴 시간이 소모된다.

또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 한다는 점이다.

(출처 : 넥스트리)

=> 순차적으로 추가/삭제 하는 경우에는 ArrayList가 LinkedList보다 빠르다.

=> 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

ArrayList와 LinkedList 접근테스트

get을 사용한 방식과 Iterator를 사용하여 ArrayList와 LinkedList에 접근해보았다.

get 메소드를 사용하였을 때 LinkedList에서 데이터 접근하는 속도는 굉장히 느렸다.

=> ArrayList와 다르게 LinkedList에서 get은 효율적이지 않다. get을 호출할 때마다 내부적으로 반복문이 실행되는데.. Iterator는 내부적으로 반복 처리된 노드가 무엇인지에 대한 정보를 유지하기 때문에 Iterator를 사용하는 것이 더 유리하다고함

public class ListTest {
    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList<>(1000000);
        LinkedList<Integer> ll = new LinkedList<>();
        insertData(al);
        insertData(ll);
        
        System.out.println("== Get 접근 테스트 ==");
        System.out.println("ArrayList : " + getAccess(al));
        System.out.println("LinkedList : " + getAccess(ll));
        
        System.out.println("== Iterator 접근 테스트 ==");
        System.out.println("ArrayList : " + iteratorAccess(al));
        System.out.println("LinkedList : " + iteratorAccess(ll));
        
    }
    
    public static void insertData(List<Integer> list) {
        for(int i=0; i<100000; i++) list.add(i);
    }
    
    public static long getAccess(List<Integer> list) {
        long start = System.currentTimeMillis();
        for(int i=0; i<100000; i++) list.get(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
    
    public static long iteratorAccess(List<Integer> list) {
        Iterator<Integer> iter = list.iterator();
        long start = System.currentTimeMillis();
        while(iter.hasNext()) {
            iter.next();
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
}
 

결과

== Get 접근 테스트 ==

ArrayList : 3

LinkedList : 4747

== Iterator 접근 테스트 ==

ArrayList : 5

LinkedList : 3

배열의 경우 만일 n 번째 원소의 값을 얻어 오고자 한다면 단순히 수식을 계산함으로써 해결된다.

n번째 데이터 주소 = 배열의주소 + n * 데이터타입의 크기

배열은 요소들이 연속적으로 메모리상에 존재하기 때문에 이처럼 간단한 계산만으로 n번째 데이터의 주소를 얻어서 읽을 수 있어서 get연산시 굉장히 좋은 성능을 갖는다.(Random Access)

Stack과 Queue

---

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out)

큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)

스택의 활용 예 

=> 수식계산, 수식괄호검사, undo/redo, 브라우저 (뒤로, 앞으로)

큐의 활용 예

=> 최근사용문서, 인쇄작업 대기목록, 버퍼