Simple Data Structure (2) - List/Set/Map

앞에서는 Collection을 포함한 공통 메서드들에 대해 다루었습니다.

이번 시간에는 가장 많이 사용되는 List/Set을 구현한 자료구조에 대해 알아보겠습니다.

 

일반적인 데이터 저장은 ArrayList

리스트 인터페이스를 구현한 대표적인 자료구조로 내부적으론 배열로 구성되어 있습니다.

또한 리스트를 구현했기 때문에 자료를 순서대로 저장하고 중복을 허용하는 특징을 가지고 있습니다.

List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>(Arrays.asList(1,2,3,2));	//Parameter Collection

//원소 추가
list1.add(0);
System.out.println(list1);        //[0]

//원소들 추가
list1.addAll(Arrays.asList(1,2,3));    
System.out.println(list1);        //[0, 1, 2, 3]

//원소 반환
System.out.println(list1.get(0)); //1

//원소 수정
list1.set(2, 0);   				  //Parameter index, element
System.out.println(list1);		  //[0, 1, 0, 3]

//원소 삭제
list1.remove(0);   				  //Parameter index 
System.out.println(list1);        //[1, 0, 3]

//원소들 삭제
list1.removeAll(Arrays.asList(1,2,3));  
System.out.println(list1);        //[0]

//원소가 포함되었는지 확인
System.out.println(list1.contains(0));		//true

//인덱스 반환
System.out.println(list1.indexOf(2));		//1
System.out.println(list1.lastIndexOf(2));	//3

 

ArrayList 데이터 삭제의 불안정성

ArrayList에서 데이터를 삭제할 때 remove를 사용합니다

remove 메서드는 우선 삭제할 인덱스를 채우기 위해 데이터를 복사 붙여넣기하여 순차적으로 밀어넣습니다.

그 뒤로 마지막 인덱스를 제거합니다.

따라서 순차적으로 remove를 실행시키면 데이터가 제대로 삭제되지 않는 현상이 발생할 수 있습니다.

List<Integer> me = new ArrayList(Arrays.asList(1,2,3,2));
		
for(int i=0; i<me.size(); i++) {
    me.remove(i);
}

System.out.println(me);   //[2, 2]

위와 같이 모든 인덱스를 순차적으로 remove 메서드를 실행해도 데이터가 남아있다. 그렇다면 데이터를 안전하게 지우는 방법은 없을까요? 방법은 iterator을 사용하는 것입니다.

List<Integer> me = new ArrayList(Arrays.asList(1,2,3,2));
Iterator<Integer> it = me.iterator();

while(it.hasNext()) {
    it.next();		//해당 메서드가 호출되어야지 예외가 발생하지 않음
    it.remove();	//원소 삭제
}

System.out.println(me);	   //[]

데이터가 모두 안정적으로 지워졌습니다.

 

ArrayList와 LinkedList

LinkedList는 배열이 아닌 노드가 연결되어 있는 형태로 구성되어 있습니다.

이에 따라 중간에 데이터를 삽입하거나 삭제할 때 굉장히 빠른 속도를 자랑합니다. ArrayList와는 달리 노드가 가리키는 참조값만 변경해주면 되기 때문이지요.

반대로 ArrayList으 경우 단순 데이터 조회에 굉장히 유리합니다. 인덱스값만 알게된다면 원하는 데이터를 찾을 수 있기 때문이죠.

자료구조는 각각의 장단점이 있기 마련입니다. 그래서 상황에 알맞게 사용해야합니다.

하지만 중간에 데이터를 삽입이나 삭제하는 상황은 생각보다 자주 나오지 않아 보통의 경우 ArrayList를 가장 많이 사용합니다.

 

집합연산에는 HashSet

HashSet은 집합 인터페이스를 구현하였으며 내부적으로는 HashMap으로 이루어져 있습니다.

Set Interface를 구현하였기에 순서가 존재하지 않고 중복을 허용하지 않습니다. HashMap으로 구성되어 있기 때문에 데이터 조회나 연산에 효율적이며 HashSet을 활용해 집합연산 메서드를 소개해드리겠습니다.

//생성
Set<Integer> me = new HashSet<>(Arrays.asList(1,2,3));   //파라미터로 Collection을 받음
Set<Integer> ma = new HashSet<>(Arrays.asList(3,4,5));
Set<Integer> mo = new HashSet<>();


//합집합
me.addAll(ma);
System.out.println(me);   //[1, 2, 3, 4, 5]

//차집합
me.removeAll(ma);
System.out.println(me);   //[1, 2]

//교집합
me.retainAll(ma);
System.out.println(me);   //[]

//부분집합인지 확인
System.out.println(ma.containsAll(me));   //true

 

범위검색에는 TreeSet

집합 인터페이스를 구현한 자료구조인 TreeSet은 이진 탐색 트리로 구성되어 있습니다.

따라서 데이터를 넣음과 동시에 자동으로 정렬된다는 특징을 가지고 있습니다. 당연하지만 Set Interface를 구현하였기 때문에 순서가 존재하지 않고 중복을 허용하지 않습니다. HashSet과는 달리 범위검색에 관련된 메서드들을 가지고 있습니다.

//생성
SortedSet<Integer> me = new TreeSet<>(Arrays.asList(1, 5, 3, 3)); //파라미터로 Collection을 받음
SortedSet<Integer> me = new TreeSet<>();

//이진 탐색 트리
System.out.println(me);	  //[1, 3, 5]

//?이상 ?미만인 데이터
System.out.println(me.subSet(1, 3));	//[1]

//?보다 작은 데이터
System.out.println(me.headSet(3));		//[1]

//?보다 큰 데이터
System.out.println(me.tailSet(3));		//[3, 5]

해당 메서드들은 SortedSet Interface를 구현한 것이기 때문에 생성 시에 SortedSet Interface로 구현해야 합니다.

 

 

데이터 쌍값 저장은 HashMap

키와 값을 가진 쌍값 데이터를 저장하기 위한 자료구조인 Map Interface입니다.

내부적으론 키와 값을 가진 내부 클래스인 Map.Entry의 배열로 구성되어 있습니다. 이때 키는 중복이 허용되지 않으며 값은 중복이 허용된다는 특징을 가지고 있습니다.

HashMap은 해싱기법을 사용하여 Map Interface를 구현하고 있으며 쌍값 데이터 조회와 연산에 매우 뛰어난 성능을 보입니다.

 

자주 사용하는 메서드들을 HashMap을 구현한 예시로 살펴보겠습니다.

//생성
Map<String, Integer> me = new HashMap<>();
Map<String, Integer> ma = new HashMap<>();

//데이터의 저장(중복 데이터는 오버라이딩)
me.put("one", 1);
ma.put("two", 2);
ma.put("two", 7);

//데이터 조회
System.out.println(me.get("one"));	 //1
System.out.println(ma.get("two"));   //7
System.out.println(me.getOrDefault("three", 3));   //3

//맵끼리 합치기(중복 데이터는 오버라이딩)
me.putAll(ma);
System.out.println(me);   //{one=1, two=7}

//데이터 제거
ma.remove("two");
System.out.println(ma);   //{}

//키나 값이 있는지 확인
System.out.println(me.containsKey("one"));	//true
System.out.println(me.containsValue(1));	//true

//집합 형태로 Map.Entry, keys, values 반환
System.out.println(me.entrySet());	//[one=1, two=7]
System.out.println(me.keySet());	//[one, two]
System.out.println(me.values());	//[1, 7]

HashMap은 순서가 보장되지 않는 특징이 있습니다. 하지만 HashMap 대신 LinkedHashMap을 구현한다면 데이터를 추가한 순서가 보장된다는 특징을 가질 수 있습니다.