챕터 11-4 연습문제

[pej4303]

• [11-4] LinkedList 클래스는 이름과 달리 실제로는 이중 원형 연결리스트(doubly circular linked list) 로 구현되어 있다. LinkedList 인스턴스를 생성하고 11개의 요소를 추가했을 때, 이 11개의 요소 중 접근시간(access time)이 가장 오래 걸리는 요소는 몇 번째 요소인가?

출처

• Java의 정석

[pej4303]

• 답 : 11번째 요소
• 이유 : LinkedList 클래스는 불연속적으로 데이터가 위치해있기 때문에 처음부터 순차적으로 접근해야지 특정 값을 찾을 수 있다. 따라서 뒤쪽에 있는 데이터를 접근해야되면 더 느려질 수 밖에 없다.

public static void main(String[] args) {
        /**
         * ArrayList와 LinkedList 클래스의 속도 비교
         * 
         * 결론 : 동일하게 11개의 데이터를 넣고 접근 속도를 비교해 보았는데 LinkedList 클래스가 거의 2배 정도로 느리다.
         */
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        list.add(11);
        
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(1);
        list2.add(2);
        list2.add(3);
        list2.add(4);
        list2.add(5);
        list2.add(6);
        list2.add(7);
        list2.add(8);
        list2.add(9);
        list2.add(10);
        list2.add(11);
        
        long startTime = System.nanoTime();
        for (int i=0; i<list.size(); i++) {
            list.get(i);
        }
        long endTime  = System.nanoTime();
        System.out.println("ArrayList 소요시간 : " + (endTime - startTime));
        
        startTime = System.nanoTime();
        for (int i=0; i<list2.size(); i++) {
            list2.get(i);
        }
        endTime  = System.nanoTime();
        System.out.println("LinkedList 소요시간 : " + (endTime - startTime));
    }
[실행결과]
ArrayList 소요시간 : 10200
LinkedList 소요시간 : 20100

[kha212]

11번째 마지막 요소에 접근하고자 할 때 가장 오래 걸림 (해당 요소의 위치를 알기 위해 처음부터 직전 요소까지 조회)
※특정 요소 접근시의 소요 시간 측정 방법?

public static void main(String[] args) {
	ArrayList al = new ArrayList(10000);
	LinkedList ll = new LinkedList();
		
	dataAdd(al);
	dataAdd(ll);
		
	System.out.println("array list get time: " + access(al));
	System.out.println("linked list get time: " + access(ll));
		
	/* 실행시 '대체로' 링크드 리스트가 느리게 나오지만, 실행시마다 처리 시간이 달라져서
	  마지막 데이터 가져올 때 가장 느린지는 확인 어려움 */

}
	
public static void dataAdd(List list) {
	for (int i = 0; i<10000; i++) list.add(String.valueOf(i));
}
	
public static long access(List list) {
	long strt = System.nanoTime();
	//for (int i = 0; i<1000; i++) list.get(i);
	list.get(10000 - 10);
	long end = System.nanoTime();
	return (end - strt);
}

[pej4303]

[연습문제 답안]

• 답 : 6번째 요소(가운데 요소)
• 이유 : LinkedList 클래스가 이중 원형 연결구조여서 마지막 요소와 첫번째 요소의 접근은 쉬우나 중간 요소인 경우 순차적으로 접근해야되기 때문에 속도가 느림