[필기정리]Day22 - 컬렉션 프레임워크

# 용어정리

1. 프레임워크(Framework) : 잘 정의된 약속된 구조나 골격

 

2. 자바에서 말하는 프레임워크란? 잘 정의된 약속된 구조의 클래스 틀

 

3. 자료구조(Data Structures) :

데이터의 저장과 관련이 있는 학문으로서,  

검색 등 다양한 측면을 고려하여 효율적인 데이터의 저장 방법을 연구하는 학문.

 

4. 알고리즘(Algorithms)
알고리즘은 저장된 데이터의 일부 또는 전체를 대상으로 진행하는 각종 연산을 연구하는 학문.

 

5. 자료구조에서 정형화하고 있는 데이터의 저장방식 예시.
배열(Array), 리스트(List), 스택(Stack), 큐(Queue), 트리(Tree), 해시(Hash) 등

 

6. 알고리즘 예시 
정렬(Sort), 탐색(Search), 최대(Max), 최소(Min) 검색 

 

7. 컬렉션
   데이터의 저장, 그리고 이와 관련있는 알고리즘을 구조화 해 놓은 프레임워크이다.
   쉽게는 자료구조와 알고리즘을 클래스로 구현해놓은 것 정도로 생각해도 좋다.

   때문에 컬렉션 클래스들을 가리켜 ‘컨테이너 클래스’라고도 한다.

 

// Tip

- 컬렉션 프레임워크(Collections Framework) : 데이터 군을 저장하는 클래스들을 표준화한 설계

- 컬렉션 : 다수의 데이터(데이터 그룹)

- 프레임워크 : 표준화된 프로그래밍 방식

 

8. 컬렉션 프레임 워크의 인터페이스 구조

 

인터페이스	설명	클래스
List<E>	순서가 있는 데이터의 집합으로, 데이터의 중복을 허용	ArrayList, LinkedList
Set<E>	순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않음	HashSet, TreeSet
Map<K, V>	키와 값의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 이때 키는 중복을 허용하지 않지만, 값은 중복될 수 있음.	HashMap, TreeMap

//Tip : hash - 보안성을 높이고 속도를 빠르게 할 수 있다.

                  문자열을 변환하기 때문에 원본 데이터를 알 수 없어 보안성이 높아지고,

                  데이터를 짧게 만들어주기 때문에 속도가 빨라지는 것이다!

 

- 그림으로 정리한 Collections Framework

9. 컬렉션이 프레임워크인 이유?
 인터페이스 구조를 기반으로 클래스들이 정의되어 있기 때문에 프레임워크라 하는 것이다.

★ List<E> 인터페이스와 이를 구현하는 제네릭 클래스
 ㄴ ArrayList<E> : 배열기반

    LinkedList<E> : Linked 기반

★11. List<E> 인터페이스를 구현하는 제네릭 클래스들은 다음 두 가지 특성을 공통으로 지닌다.
① 동일한 인스턴스의 중복저장을 허용한다.
② 인스턴스의 저장순서가 유지된다.

 

- ArrayList<E>의 특징
 저장소의 용량을 늘리는 과정에서 많은 시간이 소요된다. - ArrayList<E>의 단점
 데이터의 삭제에 필요한 연산과정이 길다. - ArrayList<E>의 단점
 데이터의 참조가 용이해서 빠른 참조가 가능하다. - ArrayList<E>의 장점

- LinkedList<E> 특징
  저장소의 용량을 늘리는 과정이 간단하다. LinkedList<E>의 장점
  데이터의 삭제가 매우 간단하다. LinkedList<E>의 장점
  데이터의 참조가 다소 불편하다. LinkedList<E>의 단점

 

- ArrayList

ex) 

import java.util.ArrayList;

class IntroArrayList
{
	public static void main(String[] args)
	{
		ArrayList<Integer> list=new ArrayList<Integer>();
		
		/* 데이터의 저장 */
		list.add(11); // new Integer(11)와 동일의미, 오토박싱으로 Integer 객체의 주소값이 지정된다.
		list.add(new Integer(22));
		list.add(new Integer(33));
		
		/* 데이터의 참조 */
		System.out.println("1차 참조");
		for(int i=0; i<list.size(); i++) // size = 3
			System.out.println(list.get(i)); // 결과 : 11 22 33
		
		/* 데이터의 삭제 */
		list.remove(0);
		System.out.println("2차 참조");
		for(int i=0; i<list.size(); i++)  // size = 2
			System.out.println(list.get(i)); // 결과 : 11 22 33	
	}
}

 

- ArrayList<E> 클래스의 용량(버퍼) 설정 
ArrayList<E> 클래스는 저장되는 데이터의 수가 증가함에 따라서, 

용량(데이터 저장 가능한 용량)이 자동으로 증가하는 클래스이다. 

 

그런데 용량을 증가시키는 과정에서 수반되는 연산으로 인해 때로는 성능에 부담이 되기도 한다. 

때문에 대략 500여 개의 데이터가 저장 될 것이 예상되는 상황에서는 

점진적으로 용량을 500으로 늘리기 보다, 

처음부터 용량을 500으로 잡음으로 인해서 불필요한 연산을 줄일 필요도 있다. 

 

물론 ArrayList<E>의 메소드 중에는 저장용량의 설정을 위한 메소드가 존재한다. 

 

Q. 따라서 여러분은 API 문서를 참조하여 이 메소드를 찾기 바란다. 

   그리고 다음 조건을 만족시키는 코드를 각각 구성해 보기 바란다. 

 

<조건>
- Integer 인스턴스를 저장할 수 있는 ArrayList<E>를 생성하고 저장용량을 500으로 늘린다.
- ArrayList<E>에 저장되어 있는 인스턴스 수의 두 배로 저장용량을 늘린다.

 

A.  ensureCapacity()

public void ensureCapacity(int minCapacity);		// 메소드 원형
ArrayList<Integer> list = new ArrayList<Integer>();
list.ensureCapacity(500);
list.ensureCapacity(list.size()*2);

 

- Linked List

ex)

import java.util.LinkedList;

class IntroLinkedList
{
	public static void main(String[] args)
	{
		LinkedList<Integer> list=new LinkedList<Integer>(); // ArrayList 예시와 다른 부분
		
		/* 데이터의 저장 */
		list.add(11); // 정수값이 아니라 Integer 객체의 주소값이 저장되는 것(오토박싱)
		list.add(22);
		list.add(new Integer(33));
		
		/* 데이터의 참조 */
		System.out.println("1차 참조");
		for(int i=0; i<list.size(); i++) // size = 3
			System.out.println(list.get(i));
		
		/* 데이터의 삭제 */
		list.remove(0);
		System.out.println("2차 참조");
		for(int i=0; i<list.size(); i++) // size = 2
			System.out.println(list.get(i)); // 결과 : 22 33	
	}
}

- 인터페이스를 구현함으로 인해서 일반적인 규칙성을 적용할 수 있다.

 

Q. SoSimpleLinkedListImpl.java 소스를 분석하여 메모리 맵을 그려 보시오.

class Box<T>
{
	public Box<T> nextBox; // T가 String으로 바뀜
	T item;

	public void store(T item) { this.item=item; }
	public T pullOut() { return item; }
}

class SoSimpleLinkedListImpl
{
	public static void main(String[] args)
	{
		Box<String> boxHead=new Box<String>();
		boxHead.store("First String");
		
		boxHead.nextBox=new Box<String>();
		boxHead.nextBox.store("Second String");
		
		boxHead.nextBox.nextBox=new Box<String>();
		boxHead.nextBox.nextBox.store("Third String");
		
		Box<String> tempRef;
		
		/* 두 번째 박스에 담긴 문자열 출력 과정 */
		tempRef=boxHead.nextBox;
		System.out.println(tempRef.pullOut());

		/* 세 번째 박스에 담긴 문자열 출력 과정 */
		tempRef=boxHead.nextBox;
		tempRef=tempRef.nextBox;
		System.out.println(tempRef.pullOut());
	}
}

A. 

- TempRef의 경우 먼저 3000번지 주소의 참조변수가 생성되고 이후 5000번지 주소의 참조변수가 생성되는 것

- 위의 메모리맵은 싱글 링크드 리스트이며, 더블 링크드 리스트도 있다. 

 

Q. ArrayList<E> vs LinkedList<E>

   아래에서 제시하는 상황에 적절한 자료구조를 선택해보자.

 

- 상황 1

  저장하게 되는 데이터의 수가 대략적으로 예측 가능하며, 

  빈번한 데이터의 참조가 일어나는 상황에서 유용하게 사용할 수 있는 컬렉션 클래스는 무엇인가?

  A. ArrayList<E>

-  상황2
   저장하게 되는 데이터의 수가 예측 불가능하며,

   빈번한 데이터의 저장 및 삭제가 일어나는 상황에서 유용하게 사용할 수 있는 컬렉션 클래스는 무엇인가? 

  A. LinkedList<E>

 

ex)

import java.util.Iterator;
import java.util.LinkedList;

class IteratorUsage
{
	public static void main(String[] args)
	{
		LinkedList<String> list=new LinkedList<String>();
		list.add("First"); 
		list.add("Second");
		list.add("Third");
		list.add("Fourth");
		
		Iterator<String> itr=list.iterator();
		
		System.out.println("반복자를 이용한 1차 출력과 \"Third\" 삭제");
		while(itr.hasNext()) // true(다음 요소 있는 경우)나 false 반환
		{
			String curStr=itr.next(); // 가리키는 곳의 객체주소값 반환
			System.out.println(curStr); // 주소값이 들어감
			if(curStr.compareTo("Third")==0)
				itr.remove(); // 같은 경우 Third 객체 삭제
		}
		
		System.out.println("\n\"Third\" 삭제 후 반복자를 이용한 2차 출력 ");		
		itr=list.iterator(); // 반복자(itertator)를 반환한다.
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

 

ex) 강사님 예시

import java.util.Iterator;
import java.util.LinkedList;

class PhoneInfo
{
	private String name;
    private int age;
    
    public PhoneInfo(String name, int age)
    {
    	this.name = name;
        this.age = age;
    }
    
    public void showInfo()
    {
    	System.out.println("이름 :" +name);
        System.out.println("나이 :" +age);
    }
}

class IteratorUsage
{
	public static void main(String[] args)
	{
		LinkedList<PhoneInfo> list=new LinkedList<PhoneInfo>();
		list.add(new PhoneInfo("홍길동", 20)); 
		list.add(new PhoneInfo("배트맨", 30)); 
		list.add(new PhoneInfo("원더우먼", 22));  

		Iterator<PhoneInfo> itr=list.iterator();
		while(itr.hasNext()) 
		{
			PhoneInfo info=itr.next(); 
			info.showInfo();	
		}
	}	
}

 

★ set(집합)

① 중복저장을 허용하지 않음

② 저장의 순서가 유지되지 않는다.

    ↔ 예외 LinkedSet : 중복저장을 허용하진 않지만 Linked의 속성 때문에 저장의 순서는 유지된다.

ex) 

import java.util.Iterator;
import java.util.HashSet;

class UsefulIterator
{
	public static void main(String[] args)
	{
		HashSet<String> set=new HashSet<String>();
		set.add("First");
		set.add("Second");
		set.add("Third");
		set.add("Fourth");
		
		Iterator<String> itr=set.iterator(); // 반복자 반환
		
		System.out.println("반복자를 이용한 1차 출력과 \"Third\" 삭제");
		while(itr.hasNext()) // 다음 요소 있으면 true 반환
		{
			String curStr=itr.next();
			System.out.println(curStr);
			if(curStr.compareTo("Third")==0)
				itr.remove();
		}
		
		System.out.println("\n\"Third\" 삭제 후 반복자를 이용한 2차 출력 ");		
		itr=set.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

- 저장 순서가 유지되지 않기 때문에 내부적 알고리즘 순으로 출력되어 정확한 순서는 찍어보기 전엔 알 순 없다.

해당 예시 이클립스 결과 화면

 

ex)

import java.util.Iterator;
import java.util.LinkedList;

class PrimitiveCollection
{
	public static void main(String[] args)
	{
		LinkedList<Integer> list=new LinkedList<Integer>();
		list.add(10);		// Auto Boxing
		list.add(20);		// Auto Boxing
		list.add(30);		// Auto Boxing
		
		Iterator<Integer> itr=list.iterator();
		
		while(itr.hasNext())
		{
			int num=itr.next();		// Auto Unboxing
			System.out.println(num); // 결과 : 10 20 30
		}
	}
}

// UnBoxing : 인스턴스 형태를 기본 자료형으로 꺼내는 것!

 

ex)

import java.util.Iterator;
import java.util.HashSet;

class SetInterfaceFeature
{
	public static void main(String[] args)
	{
		HashSet<String> hSet=new HashSet<String>();

		hSet.add("First");
		hSet.add("Second");
		hSet.add("Third");
		hSet.add("First"); // 중복저장 허용되지 않으므로 저장되지 않는다
		
		System.out.println("저장된 데이터 수: "+hSet.size());
		
		Iterator<String> itr=hSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

 

ex)

import java.util.Iterator;
import java.util.HashSet;

class SimpleNumber
{
	int num;
	public SimpleNumber(int n)
	{
		num=n;
	}
	public String toString()
	{
		return String.valueOf(num); // valueOf() : 문자열로 바꿔주는 메소드
	}
}

class HashSetEqualityOne
{
	public static void main(String[] args)
	{
		HashSet<SimpleNumber> hSet=new HashSet<SimpleNumber>();
		hSet.add(new SimpleNumber(10));
		hSet.add(new SimpleNumber(20));
		hSet.add(new SimpleNumber(20));
		
		System.out.println("저장된 데이터 수: "+hSet.size());
		
		Iterator<SimpleNumber> itr=hSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

- hashcode() : 두 객체가 같은 객체인지 확인하는 메소드

- equals() : 두 객체의 내용이 같은지 확인하는 메소드

 

- 위의 중복을 허용하지 않게 하려면 hashCode()와 equals() 2가지를 메소드 오버라이딩 해줘야 한다.

  내부적으로 hashcode가 먼저 호출된다.

ex)

import java.util.Iterator;
import java.util.HashSet;

class SimpleNumber
{
	int num;
	public SimpleNumber(int n)
	{
		num=n;
	}
	public String toString()
	{
		return String.valueOf(num);
	}
	public int hashCode() // 가장 먼저 호출됨
	{
		return num%3; // 나머지가 동일한 것을 체크하기 위함
	}
	public boolean equals(Object obj) //  equals 메소드로 같은지 검사
	{
		SimpleNumber comp=(SimpleNumber)obj;
		if(comp.num==num) // 같은 것은 중복저장으로 생각해 저장하지 않음
			return true;
		else
			return false;		
	}
}

class HashSetEqualityTwo
{
	public static void main(String[] args)
	{
		HashSet<SimpleNumber> hSet=new HashSet<SimpleNumber>();
		hSet.add(new SimpleNumber(10));
		hSet.add(new SimpleNumber(20));
		hSet.add(new SimpleNumber(20));
		
		System.out.println("저장된 데이터 수: "+hSet.size());
		
		Iterator<SimpleNumber> itr=hSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next()); // 결과 : 10 20
	}
}

 

// Tip : hash가 들어간 것은 모두 검색속도가 빠르다.

 

Q. 다음 클래스의 두 인스턴스를 HashSet<E>에 저장할 때, 

   두 인스턴스의 데이터(name & age)가 완전히 동일하다면,

   하나만 저장되도록 hashCode 메소드와 equals 메소드를 오버라이딩 하자.

import java.util.HashSet;
import java.util.Iterator;

class Person
{
	String name;
	int age;

	public Person(String name, int age)
	{
		this.name = name;
		this.age = age;
	}
	public String toString()
	{
		return name + "(" + age + "세)";
	}
}

class PersonMain
{
	public static void main(String[] args)
	{
		HashSet<Person> hSet = new HashSet<Person>();
		hSet.add(new Person("이진호", 10));
		hSet.add(new Person("이진호", 20));
		hSet.add(new Person("김명호", 20));
		hSet.add(new Person("김명호", 15));
		hSet.add(new Person("이진호", 20));
		hSet.add(new Person("김명호", 20));

		System.out.println("저장된 데이터 수 : " +  hSet.size());

		Iterator<Person> itr = hSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

인스턴스의 내용비교가 되도록 적절히 오버라이딩 되었다면, 다음의 실행결과를 보여야 한다. 
단, 이름과 나이 정보가 출력되는 순서는 hashCode 메소드의 구현에 따라 다를 수 있다. 
아니 대부분 다를 것이다.

저장된 데이터 수 : 4
김명호(20세)
김명호(15세)
이진호(10세)
이진호(20세)

 

A.

import java.util.HashSet;
import java.util.Iterator;

class Person
{
	String name;
	int age;

	public Person(String name, int age)
	{
		this.name = name;
		this.age = age;
	}
    
	public String toString()
	{
		return name + "(" + age + "세)";
	}
    
	@Override
	public int hashCode() {
		return name.hashCode();
	}
    
	@Override
	public boolean equals(Object obj) {
		Person other = (Person)obj;
		if(age == other.age && name.equals(other.name))
			return true;
		else
			return false;
	}
}

class PersonMain
{
	public static void main(String[] args)
	{
		HashSet<Person> hSet = new HashSet<Person>();
		hSet.add(new Person("이진호", 10));
		hSet.add(new Person("이진호", 20));
		hSet.add(new Person("김명호", 20));
		hSet.add(new Person("김명호", 15));
		hSet.add(new Person("이진호", 20));
		hSet.add(new Person("김명호", 20));

		System.out.println("저장된 데이터 수 : " +  hSet.size());

		Iterator<Person> itr = hSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

 

- Tree가 들어간 키워드는 정렬해주는 것!

ex)

import java.util.Iterator;
import java.util.TreeSet; // 중복저장 허용하지 않음

class SortTreeSet
{
	public static void main(String[] args)
	{
		TreeSet<Integer> sTree=new TreeSet<Integer>();
		sTree.add(1); // = sTree.add(new Integer(1)); 1은 객체! 오토박싱된 것 
		sTree.add(2);
		sTree.add(4);
		sTree.add(3);
		sTree.add(2);
		
		System.out.println("저장된 데이터 수: "+sTree.size());
		
		Iterator<Integer> itr=sTree.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

 

- 정렬을 위해선 인터페이스 Comparable를 구현하고, compareTo를 메소드 오버라이딩 해야 한다.

 

ex) 나이 오름차순으로 정렬되고 있다.

import java.util.Iterator;
import java.util.TreeSet;

class Person implements Comparable<Person> // 정렬을 위해 만든 인터페이스
{
    String name;
    int age;

    public Person(String name, int age)
    {
        this.name=name;
        this.age=age;
    }
    public void showData()
    {
    	System.out.printf("%s %d \n", name, age);
    }
    public int compareTo(Person p) // compareTo 메소드 오버라이딩 해줘야 한다!
    {
        if(age>p.age)           // = return age - p.age; (동일표현)
            return 1;
        else if(age<p.age)     // 알파벳순 정렬을 원하는 age 대신 name을 넣으면 된다  
            return -1;
        else	
            return 0;
    }
}

class ComparablePerson 
{
	public static void main(String[] args)
	{
		TreeSet<Person> sTree=new TreeSet<Person>();
		sTree.add(new Person("Lee", 24));
		sTree.add(new Person("Hong", 29));
		sTree.add(new Person("Choi", 21));
		
		Iterator<Person> itr=sTree.iterator();
		while(itr.hasNext())
			itr.next().showData();
	}
}

 

- String은 이미 정렬기준이 있다. (메소드 오버라이딩 때문)

ex) 기존의 String의 정렬기준이 아닌 글자의 길이로 정렬을 원하는 경우

    인터페이스 Comparable 구현, compareTo 메소드 오버라이딩함

import java.util.TreeSet;
import java.util.Iterator;

class MyString implements Comparable<MyString>
{
	String str;
	
	public MyString(String str)
	{
		this.str=str;
	}
	
	public int getLength()
	{
		return str.length();
	}
	
	public int compareTo(MyString mStr)
	{
		if(getLength()>mStr.getLength())
			return 1;
		else if(getLength()<mStr.getLength())
			return -1;
		else
			return 0;
		
		/*
		 * return getLength()-mStr.getLength();
		 */
	}
	
	public String toString()
	{
		return str;
	}
}

class ComparableMyString
{
	public static void main(String[] args)
	{
		TreeSet<MyString> tSet=new TreeSet<MyString>();		
		tSet.add(new MyString("Orange"));
		tSet.add(new MyString("Apple"));
		tSet.add(new MyString("Dog"));
		tSet.add(new MyString("Individual"));
		
		Iterator<MyString> itr=tSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

 

- 정렬의 기준이 되는 클래스를 만들어주어 활용하는 방법도 있음

ex)

import java.util.TreeSet;
import java.util.Iterator;
import java.util.Comparator;

class StrLenComparator implements Comparator<String>
{
	public int compare(String str1, String str2)
	{
		if(str1.length()> str2.length())
			return 1;
		else if(str1.length()< str2.length())
			return -1;
		else
			return 0;
		
		/*
		 * return str1.length()-str2.length();
		 */
	}
}

class IntroComparator
{
	public static void main(String[] args)
	{
		TreeSet<String> tSet=new TreeSet<String>(new StrLenComparator());		
		tSet.add("Orange");
		tSet.add("Apple");
		tSet.add("Dog");
		tSet.add("Individual");
		
		Iterator<String> itr=tSet.iterator();
		while(itr.hasNext())
			System.out.println(itr.next());
	}
}

//Tip

- Comparable : 기본 정렬기준 구현할 때 사용

- Comparator : 기본 정렬기준이 아닌 다른 정렬기준으로 정렬할 때 사용

 

# Map

  key : 중복될 수 없다.

  value : 중복할 수 있다.

 

- key를 넘기면 value를 반환해준다.

ex)

import java.util.HashMap;

class IntroHashMap
{
	public static void main(String[] args)
	{
		HashMap<Integer, String> hMap=new HashMap<Integer, String>();

		hMap.put(new Integer(3), "나삼번");		
		hMap.put(5, "윤오번");	
		hMap.put(8, "박팔번");	
		
		System.out.println("6학년 3반 8번 학생: "+hMap.get(new Integer(8)));
		System.out.println("6학년 3반 5번 학생: "+hMap.get(5));
		System.out.println("6학년 3반 3번 학생: "+hMap.get(3));
		
		hMap.remove(5);		/* 5번 학생 전학 감 */ 
		System.out.println("6학년 3반 5번 학생: "+hMap.get(5));		
	}
}

 

- Map 인터페이스를 구현한 것은 iterator 메소드가 없다.

ex) 

import java.util.TreeMap;
import java.util.Iterator;
import java.util.NavigableSet;

class IntroTreeMap
{
	public static void main(String[] args)
	{
		TreeMap<Integer, String> tMap=new TreeMap<Integer, String>();

		tMap.put(1, "data1");		
		tMap.put(3, "data3");	
		tMap.put(5, "data5");	
		tMap.put(2, "data2");	
		tMap.put(4, "data4");	
		
		NavigableSet<Integer> navi=tMap.navigableKeySet();
		
		System.out.println("오름차순 출력...");
		Iterator<Integer> itr=navi.iterator();
		while(itr.hasNext())
			System.out.println(tMap.get(itr.next()));
		
		System.out.println("내림차순 출력...");
		itr=navi.descendingIterator(); // 내림차순
		while(itr.hasNext())
			System.out.println(tMap.get(itr.next()));	
	}
}