컬렉션

ArrayList

컬렉션이란 자료의 집합을 관리하는 자료 구조이다. 가장 간단하게는 배열이 있지만 배열은 재할당할 수 없어 최초 생성한 크기 이상을 저장할 수 없다는 약점이 있다. 컬렉션은 실행중에 메모리를 자동으로 재할당하므로 가변 크기의 자료들을 저장하는데 적합하다.

가장 대표적이고도 실용적인 컬렉션이 ArrayList이다. 배열과 메모리 관리 방법이 유사하되 실행중에 요소의 개수에 따라 동적으로 크기를 늘릴 수 있고 배열 중간에도 삽입, 삭제가 자유롭다는 차이점이 있다. 템플릿 클래스이므로 <> 괄호안에 저장하고자 하는 데이터의 타입 파라미터를 밝혀야 한다. 생성자는 다음과 같다.

 

ArrayList<E>()

ArrayList<E>(int initialCapacity)

 

디폴트 생성자는 크기 10의 배열을 초기 할당한다. 어차피 실행중에 필요한만큼 메모리가 늘어나므로 초기 크기는 중요하지 않다. 하지만 매번 재할당하면 속도가 느려지므로 대용량의 자료를 관리해야 한다면 초기 크기를 전달하여 처음부터 메모리를 크게 할당해 놓는 것이 유리하다. 요소를 추가할 때는 다음 메서드를 호출한다.

 

boolean add(E e)

void add(int index, E element)

 

요소만 전달하면 배열의 끝에 추가되고 위치까지 같이 전달하면 지정한 위치에 삽입된다. 중간에 끼어들면 뒤쪽의 요소들은 자동으로 한칸씩 뒤로 이동한다. 배열의 현재 크기를 조사할 때는 size 메서드를 호출하며 배열이 비어 있는지만 알고 싶을 때는 isEmpty 메서드를 호출한다.

 

int size()

boolean isEmpty()

 

비어 있다는 것은 요소 개수가 0이라는 것과 같으므로 size() == 0 조건문으로도 조사할 수 있다. 그러나 큰 배열의 경우는 개수를 전부 세는 것 자체가 시간을 많이 소모할 수도 있으므로 비어 있는지만 알고 싶을 때는 isEmpty 메서드가 더 빠를 것이다. 배열의 요소를 읽거나 변경할 때는 다음 두 메서드를 사용한다.

 

E get(int index)

E set(int index, E element)

 

get 메서드로 읽고자 하는 배열의 첨자를 전달하면 이 첨자에 저장된 요소가 읽혀진다. 이때 첨자는 반드시 배열의 크기보다 작아야 하여 범위를 벗어나면 IndexOutOfBounds 예외가 발생한다. 요소를 삭제할 때는 다음 메서드를 사용한다.

 

E remove(int index)

void removeRange(int fromIndex, int toIndex)

void clear()

 

첨자를 지정하여 한 요소만 삭제할 수도 있고 일정 범위의 요소를 삭제할 수도 있다. clear 메서드는 모든 요소를 전부 다 삭제한다. 다음 두 메서드는 배열에서 요소를 찾는다.

 

int indexOf(Object o)

int lastIndexOf(Object o)

 

검색하고자 하는 요소를 인수로 전달하면 이 요소가 발견되는 위치를 리턴한다. 발견되지 않으면 -1이 리턴된다. indexOf는 배열의 앞쪽부터 검색을 하며 lastIndexOf는 뒤쪽에서부터 검색을 시작한다. 배열에 똑같은 요소가 여러 개 존재하는 경우 어떤 메서드로 검색을 하는가에 따라 결과가 달라질 수도 있다. 다음 예제는 ArrayList의 여러 가지 메서드를 순서대로 호출해 본다.

 

import java.util.*;

class JavaExam {

     public static void main(String args[]) {

          ArrayList<String> arName = new ArrayList<String>();

          arName.add("전두환");

          arName.add("김영삼");

          arName.add("김대중");

          arName.add(1,"노태우");

          for (int i = 0;i < arName.size();i++) {

              System.out.println(arName.get(i));

          }

 

          System.out.println("==========");

          arName.remove(2);

          arName.set(2,"원더걸스");

          for (int i = 0;i < arName.size();i++) {

              System.out.println(arName.get(i));

          }

          if (arName.indexOf("노태우") != -1) {

              System.out.println("있다");

          } else {

              System.out.println("없다");

          }

     }

}

 

문자열을 저장하는 arName 배열을 선언하고 초기화했다. 생성자의 인수로 초기값을 전달하지 않았으므로 최초 10개의 요소를 저장할 수 있는 크기로 생성될 것이다. add 메서드로 전두환, 김영삼, 김대중을 차례대로 추가했다. 추가된 순서대로 배열의 선두부터 차례대로 기억된다. 노태우는 1번 위치에 삽입했다. 전두환과 김영삼 사이에 노태우가 끼어들 것이다.

배열을 순회할 때는 0부터 시작해서 size 메서드로 조사한 배열 크기 직전까지 순회하면서 get 메서드로 첨자 위치의 요소를 읽으면 된다. 정적 배열과 마찬가지로 시작 첨자는 항상 0이며 마지막 첨자는 크기보다 1 작다. 배열의 모든 요소들을 출력해 보았는데 역대 대통령 순으로 출력될 것이다.

다음은 remove 메서드로 2번 요소를 삭제했는데 김영삼이 삭제된다. 중간에 요소가 삭제되면 뒤쪽의 요소들이 한칸씩 앞쯕으로 이동하므로 김대중이 2번 요소가 될 것이다. set 메서드로 2번 요소를 원더걸스로 바꾸어 보았다. 김영삼은 사라지고 김대중은 원더걸스로 바뀔 것이다. 마지막으로 indexOf로 노태우 요소가 아직 있는지를 점검해 보았다.

 

전두환

노태우

김영삼

김대중

==========

전두환

노태우

원더걸스

있다

 

ArrayList에 저장되는 요소들은 참조형만 가능하며 기본형은 저장할 수 없다. 실행중에 힙에 동적으로 할당되어야 하기 때문이다. 만약 기본형을 저장하고 싶다면 이때는 앞에서 배운 래퍼 클래스로 박싱하여 저장해야 한다. 다음 예제는 정수를 컬렉션에 저장한다.

 

import java.util.*;

class JavaExam {

     public static void main(String args[]) {

          ArrayList<Integer> arNum = new ArrayList<Integer>();

          arNum.add(86);

          arNum.add(92);

          arNum.add(77);

          for (Integer i : arNum) {

              System.out.println(i);

          }

     }

}

 

ArrayList<int> 타입은 허용되지 않으므로 int를 래핑하는 Integer 타입을 사용해야 한다. 이외에도 ArrayList에는 컬렉션을 배열로 변환하는 toArray 메서드와 뒤쪽의 여유 메모리를 회수하는 trimToSize 메서드가 제공된다.

LinkedList

ArrayList는 요소들을 인접한 메모리에 저장하기 때문에 읽기 속도가 굉장히 빠르다. 원하는 첨자에 요소 타입의 크기를 곱하기만 하면 원하는 값을 바로 구할 수 있다. 그러나 요소들이 계속 인전한 상태를 유지하기 위해 중간에 삽입, 삭제할 때 뒤쪽의 요소들을 이동시켜야 하므로 삽입, 삭제 속도는 느리다.

LinkedList는 ArrayList와는 완전히 반대되는 성질을 가진다. 요소들을 인접한 메모리에 저장하는 것이 아니라 힙의 아무 곳에나 저장하되 링크로 서로 연결하여 앞뒤 순서를 구별한다. 중간에 요소를 삽입 삭제하더라도 메모리를 이동할 필요없이 링크만 조작하면 되므로 삽입, 삭제 속도가 빠르다. 그러나 임의 위치의 요소를 읽으려면 처음부터 순서대로 링크를 따라 가야 하므로 읽기 속도는 느리다.

이 둘은 사용 용도가 완전히 같아서 서로 대체 가능하다. 내부적인 구조가 다름으로 인해 메모리 사용량에서 차이가 나고 읽기, 쓰기 동작의 속도차가 날 뿐이다. 읽기 동작이 빈번하면 ArrayList를 쓰는 것이 유리하고 삽입, 삭제가 빈번하면 LinkedList를 쓰는 것이 유리하다. 그러나 일반적으로는 읽기가 쓰기보다 훨씬 더 중요하기 때문에 ArrayList가 대부분의 경우에 더 좋은 성능을 보여 준다.

둘 다 똑같은 용도로 사용하는 클래스이므로 인터페이스도 거의 비슷하다. 다만 LinkedList에는 다음 메서드들이 추가로 제공된다. 리스트의 첫 위치에 삽입하거나 첫 위치의 요소를 읽는데 이 메서드들도 사실 add(0, e), get(0)와 동일하므로 특별한 것도 아니다.

 

void addFirst(E e)

E getFirst()

 

다음 예제는 연결 리스트로 역대 대통령을 저장해 보고 다시 출력한다.

 

import java.util.*;

class JavaExam {

     public static void main(String args[]) {

          LinkedList<String> arName = new LinkedList<String>();

          arName.add("전두환");

          arName.add("김영삼");

          arName.add("김대중");

          arName.add(1,"노태우");

         

          for (int i = 0;i < arName.size();i++) {

              System.out.println(arName.get(i));

          }

     }

}

 

컬렉션 클래스의 이름이 바뀌었을 뿐 사용하는 방법은 완전히 동일하다. 중간에 노태우를 삽입할 때의 속도가 조금 더 빠르겠지만 실측할 수 없을 정도로 근소한 차이가 난다. 실행 결과도 물론 앞 예제와 동일하다.

 

전두환

노태우

김영삼

김대중

 

그러나 연결 리스트는 배열에 비해 요소를 읽는 속도가 느려 출력에는 상당히 불리하다. 요소가 기껏 4개밖에 없어서 차이를 느낄 수 없지만 100개 정도만 되도 차이가 벌어진다. 왜냐하면 연결 리스트는 get 메서드가 상당히 비효율적으로 동작하기 때문이다. 임의 위치의 한 요소를 읽을 때마다 리스트의 처음부터 순회를 해 와야 한다. 위 예제의 for 루프는 형태상으로는 단순 루프이지만 내부에 헤더부터 i번째 요소까지 링크를 따라가는 코드가 포함되어 있어 실제로는 이중 루프이다.

이런 약점을 극복하기 위해 연결 리스트는 반복자라는 것을 제공한다. 반복자는 링크의 현재 위치를 저장해 두는 객체이며 저장된 위치에서 바로 다음칸으로 이동할 수 있어 링크를 따라 순회할 때 훨씬 더 효율이 좋다. 코드를 다음과 같이 수정해 보자.

 

Iterator<String> it = arName.iterator();

while (it.hasNext()) {

     System.out.println(it.next());

}

 

리스트의 iterator 메서드를 호출하면 리스트의 요소들을 순회할 수 있는 반복자가 리턴되는데 이 반복자는 리스트의 요소 타입을 가리키므로 선언문에 순회할 데이터의 타입을 파라미터로 밝혀야 한다. 반복자는 최초 리스트의 헤더를 가리키며 next 메서드로 다음 요소로 링크를 따라 이동한다.

next는 요소를 읽어 리턴하기 때문에 리스트의 끝에서 에러를 리턴할만한 장치가 없다. 그래서 리스트의 끝에 닿으면 예외를 발생시킨다. 이 예외를 방지하려면 next로 이동하기 전에 hasNext 메서드를 호출하여 뒤쪽에 아직 요소가 있는지를 먼저 점검해 보아야 한다. 실행결과는 for 루프를 돌리는 것과 다를 게 없다. 그러나 리스트에 요소가 많을 때는 반복자를 쓰는 것이 확실히 더 빠르다.

HashMap

해시는 빠른 검색을 위해 데이터를 미리 정해진 규칙에 따라 일정한 장소에 저장하는 기법이다. 대용량의 버킷을 마련해 놓고 해쉬 코드에 따라 버킷 번호를 선택해 저장해 두면 검색시에 해쉬 코드를 구하는 간단한 연산으로 원하는 값을 바로 구할 수 있다. 자세한 것은 자료 구조 관련 서적을 참조하기 바란다.

자바는 HashMap 클래스로 해시를 제공한다. 키와 값에 대해 두 개의 타입을 파라미터로 전달한다. put 메서드로 키와 값의 쌍을 해시에 저장하며 get 메서드로 키를 전달하면 원하는 값을 빠른 속도로 검색할 수 있다.

 

import java.util.*;

class JavaExam {

     public static void main(String args[]) {

          HashMap<String,Integer> Snack = new HashMap<String,Integer>();

          Snack.put("오징어 땅콩", 2500);

          Snack.put("죠리퐁", 1900);

          Snack.put("핫브레이크", 450);

          Snack.put("빼빼로", 900);

         

          String MySnack = "죠리퐁";

          System.out.println(MySnack + "의 가격은 " + Snack.get(MySnack));

     }

}

 

과자의 이름과 가격을 해시에 저장해 놓고 검색해 보았다. 항목이 몇 개 안되므로 이 정도로는 해시의 빠른 검색 속도를 실감하기 어려울 것이다. 항목의 개수가 아무리 많아도 거의 실시간으로 검색된다. 거짓말 안보태고 수억개가 넘어도 검색 시간은 순간이다. 대신 메모리는 좀 많이 먹는다.

사용자가 작성한 클래스를 해시의 키로 사용하려면 hashCode 메서드를 재정의하여 해시 코드가 고르게 분포되도록 해야 한다. 이때 equals 메서드도 같이 재정의해야 한다.

출처 : http://www.winapi.co.kr/