Power Coding 파워 코딩

List

15 Jan 2019 Tags:
Data Structure, List, Java


List

List는 자료를 순서대로 저장하는 자료구조이다.

대표적으로는 배열을 이용하여 구현하는 ArrayList와 Pointer를 이용하여 구현하는 LinkedList가 있다.

ArrayList

ArrayList는 배열을 이용하여 구현한다. 배열을 이용하여 구현하기 때문에 하기의 장단점이 있다.

  • 장점 : 각 원소들을 접근하는데 매우 빠르다.
  • 단점 : 삭제, 추가 시 많은 부하가 걸린다.

ex)

  • 삭제 : 크기가 1000개의 ArrayList에서 0번째 메모리 삭제 시 999번의 데이터 이동이 필요.
  • 삽입 : 크키가 1000개의 ArrayList에서 0번째에 추가 시 기존 1000개의 데이터 이동이 필요.
  • 추가 : 원래 할당 된 사이즈 보다 더 큰 사이즈가 필요한 경우, 새로 메모리 할당 및 복사하는 과장이 필요.

    LinkedList

    LinkedList는 Pointer를 이용하여 구현한다. Pointer를 이용하여 구현하기 때문에 하기의 장단점이 있다.

  • 장점 : 삭제, 추가 시 부하가 매우 적다. (새로 메모리 할당 후 Link). 메모리
  • 단점 : 각 원소들을 접근하는데 매우 느리다.

ex) 1000번 중 999 번째의 데이터를 찾기 위해서는 0번째부터 순차적으로 1번째 데이터 Node로 가고 다음 링크를 타서 2번쨰 데이터 Node가고 …

ArrayList vs LinkedList

ArrayList와 LinkedList 성능표

  ArrayList LinkedList
indexing O(1) O(n)
Insert/delete at beginning O(n) O(1)
Insert/delete at end O(1) O(1)
Insert/delete in middle O(n) search time + Θ(1)

Iterator

자바에서는 List의 순회에 사용할 수 있는 Iterator 클래스를 제공함.
아래 코드처럼 사용

Iterator it;

it = myList.iterator();

while(it.hasNext())
{
    System.out.println(it.next());
}


몇가지 퍼포먼스 테스트

ArrayList에서 메모리 Overflow시 얼마나 많은 부하가 있는지, 그리고 Iterator 사용의 이점에 대해 몇 가지 테스트 해보았다.

테스트 대상 자료형
1. ArrayList
2. ArrayList (미리 사이즈 할당)
3. LinkedList

테스트 내역
1. List의 추가/삽입 (마지막, 처음)
2. 서치 테스트 (메소드를 이용, Iterator를 이용)


테스트 결과

이론적으로 보았던, 삽입/추가 시 ArrayList는 매우 성능이 떨어졌다.
하지만, 데이터 순회에서는 강점을 보였다.

(단위 ms)  
1. 메모리 추가 테스트  
▶ 마지막 추가 : 데이터 10000000개
- not allocated list add time: 1983  
- allocated list add time: 526  
- linked list add time: 4581  

▶ 처음에 추가 : 데이터 100000개  
- not allocated list add time: 1002  
- allocated list add time: 1050  
- linked list add time: 6  

2. 서치 테스트
- ArrayList iterator time: 8  
- ArrayList direct search time: 5  
- linkedList iterator search time: 76   
- linkedList 직접 서치하는 경우.. 20분째 결과가 안나옴

결론

  1. 메모리 할당
    ArrayList에서 미리 메모리 할당이 가능하다면 할당한다.
  2. 데이터 순회
    Iterator의 경우 한번 거쳐가기 때문에, ArrayList의 경우 직접하는게 빠르다.
    하지만, LinkedList의 경우 Iterator를 사용하는 것이 매우 빠른 속도를 보인다.

테스트 코드

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int size = 10000000;
		//int size = 100000;
		//int size = 100;
		
		List<Integer> notAllocatedList = new ArrayList<>();
		List<Integer> allocatedList = new ArrayList<>(size);	// 메모리 사이즈를 미리 할당한다.
		List<Integer> linkedList = new LinkedList<>();
				
		long start;
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			notAllocatedList.add(i);
		}
		System.out.println("not allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.add(i);
		}
		System.out.println("allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis(); 
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.add(i);
		}
		System.out.println("linked list add time: "+(System.currentTimeMillis() - start));
		
		notAllocatedList.clear();
		allocatedList.clear();
		linkedList.clear();
		
		allocatedList = new ArrayList<>(size);	// 메모리 사이즈를 미리 할당한다.
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			notAllocatedList.add(0, i);
		}
		System.out.println("not allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.add(0, i);
		}
		System.out.println("allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis(); 
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.add(0, i);
		}
		System.out.println("linked list add time: "+(System.currentTimeMillis() - start));
		

		Iterator it;	
		
		it = allocatedList.iterator();
		
		start = System.currentTimeMillis();
		while(it.hasNext())
		{
			it.next();
		}
		System.out.println("ArrayList iterator time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.get(i);
		}
		System.out.println("ArrayList direct search time: "+(System.currentTimeMillis() - start));
		
		it = linkedList.iterator();		
		start = System.currentTimeMillis();
		while(it.hasNext())
		{			
			it.next();
		}
		System.out.println("linkedList iterator search time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.get(i);
		}
		System.out.println("linkedList direct search time: "+(System.currentTimeMillis() - start));
	}

}

Related Posts