[자료구조] 컬렉션 프레임워크 - List

 

 

 

컬렉션 프레임 워크란

표준 API로 제공하는 자료구조

라이브러리를 의미한다.

 

 

데이터를 저장할 때, 어떤 방식으로 저장하느냐에 따라 프로그램의 성능이 바뀐다. 그래서 상황에 맞는 적절한 자료구조를 선택해야한다. 그래서 JAVA는 자료구조를 만드는데 필요한 다양한 인터페이스를 제공하는데 이를 JAVA 컬렉션 프레임워크라고 부른다.

 

 

컬렉션 프레임워크와 관련된 클래스들은 java.util 패키지 안에 들어가 있다.

 

 

 

List, Map, Set, Queue 같이 기본적인 자료구조 인터페이스가 java.util 패키지 안에 담겨져 있다. 그러므로 우리는 자료구조를 직접 만들지 않고 API를 갖다가 쓰면 된다. 그럼 이제부터 하나씩 자료구조들을 사용해보자.

 

 

List<E>

배열이 공간이 한정되어 있는 상자라면

리스트는 구슬을 꿰는 실과 같다.

 

배열은 저장가능한 객체의 수가 고정되어 있다. 리스트는 크기가 유동적이다. 배열은 삽입, 삭제가 일어나도 인덱스가 가리키는 데이터는 고정되어 있다.

 

리스트도 배열처럼 인덱스(index)가 있어, 인덱스를 통해 검색, 삽입, 삭제를 할 수 있다. 리스트는 삽입, 삭제에 따라 인덱스가 가리키는 데이터가 유동적으로 바뀐다. 앞에 있던 구슬이 사라지면 뒤에 있던 구슬이 앞자리를 차지하듯 말이다.

 

List<E>는 인터페이스다. 그렇다면 인터페이스를 구현할 구현 클래스가 필요하다. List를 구현할 구현 클래스는 구조에 따라 ArrayList, Vector, LinkedList로 나뉘어진다.

 

 

ArrayList

 

 

 

ArrayList는 배열기반의 리스트이다. 하지만 배열과 달리, 리스트는 크기가 고정되어 있지 않다. 그래서 삽입, 삭제가 일어나면 인덱스가 가리키는 객체를 바꾸어주어야 한다.

 

 

 

이와 같이, 인덱스 2의 객체가 사라지면, 뒤에 있는 객체들이 그 자리를 메운다. 하지만 이런 방식은 많은 오버헤드를 만든다. 2번째가 사라지면 3,4,5,6의 인덱스의 자리가 하나씩 앞으로 땡겨야한다.

 

그래서 삽입, 삭제가 빈번한 경우, 데이터를 ArrayList로 만들면 비효율적이다. 삽입, 삭젝가 빈번하고 자료구조의 크기를 유동적으로 할 필요가 있다면 LinkedList가 적당하다.

 

LinkedList

 

 

LinkedList는 배열기반이 아니다. 그래서 인덱스를 통한 삽입, 삭제가 일어나지 않는다. 대신 인접 객체 참조변수의 주소를 링크하는 방식으로 구성되어 있다. 그래서 중간에 하나가 삭제되어도, 인접 링크만 수정하면 된다. ArrayList처럼 앞으로 전부 땡길 필요가 없다.

 

그러므로 삽입, 삭제의 오버헤드가 적다. LinkedList의 인덱스는 Root부터 링크를 타고 이동할 때마다 하나씩 더해져서 정해진다. 그러므로 단순 검색시, ROOT부터 index를 count해주어야 하기 때문에 이미 index가 정해져 있는 ArrayList보다 검색속도가 느리다.

 

그러므로 상황에 따라 적합한 자료구조를 선택해야한다. 검색이 많거나 리스트 끝에 단순이 데이터를 추가하는 경우가 많다면 ArrayList가 적합하다. 만약 리스트의 삽입, 삭제가 많다면 LinkedList가 적합하다.

 

 

package list;

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> arrayList = new ArrayList(); //ArrayList
		List<String> linkedList = new LinkedList();//LinkedList
		
		long startTime=0;
		long endTime=0;
		
		//ArrayList 시간 측정
		startTime = System.nanoTime(); // ArrayList 시작!
		
		for(int i = 0; i<10000; i++) {
			//0번 자리 중간에 삽입하기
			arrayList.add(0,String.valueOf((int)(Math.random()*100)));
		}
		endTime = System.nanoTime(); // ArrayList 끝!
		
		System.out.println("ArrayList add() 걸린 시간 : " + ( endTime-startTime ) + "ns");
		
		//LinkedList 시간 측정
		startTime = System.nanoTime(); // LinkedList 시작!
		
		for(int i = 0; i<10000; i++) {
            //LinkedList 0번 자리 중간 삽입 
			linkedList.add(0,String.valueOf((int)(Math.random()*100))); 
		
         }
		endTime = System.nanoTime(); //LinkedList 끝!
		
		System.out.println("LinkedList add() 걸린 시간 : " + ( endTime-startTime ) + "ns");

	}

}

 

<출력 결과>

 

 

ArrayList는 중간에 삽입하면 인덱스를 하나씩 밀어주기 때문에 느리다. LinkedList는 중간에 삽입되면 인접 참조만 바꾸어 주기에 빠르다. 이처럼 자료구조에 따라 데이터 처리속도가 차이가 나기 때문에 상황에 맞는 적절한 자료구조를 선택하는 것이 중요하다.

 

Vector

Vector는 내부구조가 ArrayList와 똑같지만 메소드들이 synchronized 키워드로 동기화되어 있다. 멀티스레드 환경에서 리스트가 공유 자원의 역할을 할 때 안전한 객체의 추가, 삭제를 할 수 있다.

 

 

---

정리

1. 다양한 자료구조를 컬렉션 프레임 워크로 이용가능하다.

2. List는 크기가 유동적인 자료구조이다.

3. 검색, 추가는 ArrayList. 삽입, 삭제는 LinkedList가 유리하다.

4. 멀티스레드 환경의 안전한 객체의 추가, 삭제 시 Vector를 이용해준다.

 

---

 

참고자료

[Java 강의53] 자바 자료구조 클래스 -3 (LinkedList 사용법)

 

이것이 자바다

저자 : 신용권

출판 : 한빛미디어발매2015.01.05.