컬렉션 자료구조[JAVA]

컬렉션은 자료를 저장하기 위한 구조입니다.

 

많이 사용되는 자료구조

• 리스트(list)
• 스택(stack)
• 큐(queue)
• 집합(set)
• 해쉬 테이블(hash table)

 

 

컬렉션 인터페이스

• Collection : 모든 자료구조의 부모 인터페이스로서 객체의 모임을 나타냅니다.
• Set : 집합(중복되지 않은 원소)을 나타내는 자료구조
• List: 순서가 있는 자료구조로 중복된 원소를 가질 수 있다.
• Map: 키와 값들이 연관되어 있는 사전과 같은 자료구조
• Queue: 극장에서의 대기줄과 같이 들어온 순서대로 나가는 자료구조

 

컬렉션의 특징

• 컬렉션은 제네릭을 사용합니다.
• 컬렉션에는 int나 double같은 자료형은 사용할 수 없습니다. 클래스만 가능합니다.
  • 기초 자료형을 클래스로 감싼 랩터 클래스인 Integer이나 Double을 사용할 수 있습니다.
  • 기본 자료형을 저장하면 자동으로 랩퍼 클래스의 객체로 변환됩니다. (오토박싱)

 

컬렉션의 요소 접근법 3가지

 

1. for문

for(int i=0; i<list.size(); i++){
	System.out.println(list.get(i));
}

 

2. for-each

for(String s : list){
	System.out.println(s);
}

 

3. 반복자(Iterator)

 

반복자 메서드

• hasNext() : 아직 방문하지 않은 원소가 있으면 true
• next() : 다음 원소를 반환
• remove() : 최근에 반환된 원소를 삭제

while(e.hasNext()){
	s = (String) e.next();
	System.out.println(s);
};

 

4. Stream 라이브러리

 

forEach 메소드와 람다식을 사용합니다.

list.forEach((n)-> System.out.println(n))

 

---

 

벡터

벡터 클래스는 컬렉션의 일종으로 가변 크기의 배열을 구현하고 있습니다.

기존의 배열은 크기가 고정되어 있어서 사용하기 불편했다면 벡터는 요소의 개수가 늘어나면서 자동으로 배열의 크기가 증가합니다,

 

또한 벡터는 제네릭 기법을 사용하고 있으므로 어떤 타입의 객체라도 저장이 가능합니다.

Vector<String> vec = new Vector<>();

vec.add("apple");
vec.add("Orange");
vec.add(20);
vec.add(new Integer(10));

Collections.sort(vec);

 

---

ArrayList

ArrayList는 가변 크기의 배열을 구현하는 클래스입니다. 앞의 Vector와 아주 유사합니다.

차이점은 Vector는 스레드 간의 동기화를 지원하지만 ArrayList는 동기화를 하지 않기 때문에

Vectror보다 성능이 우수합니다. 하지만 멀티 스레드 상황이라면 Vector를 사용하는 것이 좋습니다.

ArrayList는 타입 매개 변수를 가지는 제네릭 클래스로 제공됩니다.

따라서 ArrayList를 생성하려면 타입 매개 변수를 지정해야합니다.

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

 

ArrayList 객체에 데이터를 저장하기 위해서는 add() 메소드를 사용합니다,

list.add("MILK");
list.add("BREAD");

• MILK: 0 , BREAD:1

 

만약 기존의 데이터가 들어 있는 위치를 지정하여 add() 호출하면 새로운 데이터는 중간에 삽입됩니다.

list.add(1, "APPLE");

• MILK:0 APPLE:1 BREAD:2

 

특정한 위치에 있는 원소를 바꾸기 위해서는 set 메서드를 이용합니다.

list.set(2,"GRAPE");

데이터를 삭제하려면 remove 메소드를 사용합니다.

list.remove(3); // 인덱스 3의 원소를 제거한다.

 

ArrayList 객체에 저장된 객체를 들고오는 메서드는 get()입니다.

String s = list.get(1);

 

배열을 리스트로 변경하기 위한 메서드는 Arrays.asList() 메소드 입니다.

List<String> list = Arrays.asList(new String[size]);

 

---

LinkedList

ArrayList의 경우 삽입이나 삭제할 때 뒤에 있는 원소들을 이동하여야 하기 때문에 문제가 됩니다.

이런 경우에는 연결 리스트로 구현된 LinkedList를 사용하는 것이 좋습니다.

연결 리스트는 각 원소를 링크로 연결합니다. 각 원소들은 다음 원소를 가르키는 링크를 저장하고 있습니다.

삽입이나 삭제가 일어날 시 뒤에 있는 원소들을 이동시키는 것이 아닌 삭제가 일어나는 위치에서 바로 앞에 있는 원소의 링크값만을 변경하면 됩니다.

단점은 위치를 가지고 원소를 접근하는 연산은 LinkedList가 ArrayList보다 더 시간이 많이 걸린다는 것입니다.

---

 

Set

 

ArrayList에는 데이터 간의 순서가 존재합니다. 하지만 순서에는 상관없이 데이터만 저장하고 싶은 경우에는 Set이 좋습니다.

수학적으로 집합(set)은 동일한 데이터를 중복해서 가질 수 없습니다.

A={1,2,3,4,5}는 집합이지만 A={1,1,2,2,3}은 집합이 아닙니다.

Set 인터페이스는 Collection 인터페이스에 정의된 메소드를 제공하며 데이터의 중복만을 막도록 설계되어 있습니다.

자바에서는 3가지 구현이 제공합니다.

• Hashset
• TreeSet
• LinkedHashSet

 

HashSet

해쉬 테이블에 원소를 저장하기 때문에 성능면에서 가장 우수합니다. 하지만 원소들의 순서가 일정하지 않은 단점이 있습니다.

 

 

TreeSet

레드-블랙 트리(red-black tree)에 원소를 저장합니다. 따라서 값에 따라 순서가 결정되지만 HashSet보다 느립니다.

 

 

LinkedHashSet

해쉬 테이블과 연결 리스트를 결합한 것으로 원소들의 순서는 삽입되었던 순서와 같습니다.

LinkedHashSet은 약간의 비용을 들여서 HashSet의 문제점인 순서의 불명확성을 제거한 방법입니다.

 

 

합집합과 교집합

수학에서 집합 연산에는 합집합과 교집합이 있습니다.

자바에는 addAll()과 retainAll()이라는 메소드가 있습니다.

Set<Integer> s1 = new HashSet<>(Arrays.asList(1,2,3,4,5,7,9));
Set<Integer> s2 = new HashSet<>(Arrays.asList(2,4,6,8));

s1.retainAll(s2); // 교집합을 계산한다.
System.out.println(s1);

• Arrays.asList()는 배열 데이터를 List로 변경하는 메소드입니다.

 

 

중복된 단어 검출하기

Set<String> s = new HashSet<String>();
String[] sample = {"사과","사과","바나나", "토마토"};

for(String a : sample){
	if(!s.add(a)){
		System.out.println("중복된 단어:" + a);
	}
}

System.out.println(s.size() + "중복되지 않은 단어: " + s);

---

 

Map

Map은 키-값을 하나의 쌍으로 묶어서 저장하는 자료구조입니다.

 

Map은 사전과 같은 자료구조입니다. 사전처럼 단어가 있고, 단어에 대한 설명이 있습니다.

중복된 키를 가질 수 없습니다. 각 키는 오직 하나의 값에만 매핑될 수 있습니다.

키(key)	값(value)
kim	1234
park	pass

 

Map은 List와 같은 자료구조와는 상당히 다르기 때문에 Collection 인터페이스를 사용하지 않고

별도의 Map이라는 이름의 인터페이스가 제공되고 이 인터페이스를 구현한 HashMap, TreeMap, LinkedHashMap 등의 3가지의 클래스가 제공됩니다.

 

HashMap은 해싱 테이블에 데이터를 저장하고 TreeMap은 탐색 트리에 데이터를 저장합니다.

키를 정렬된 순서로 방문할 필요가 없다면 HashMap이 약간 빠릅니다. 데이터를 저장하려면

put() 메소드를 사용합니다. 키들은 중복되지 않아야하며 동일한 키로 두 개의 값을 저장할 수 없습니다.

Map<Integer, String> map = new HashMap<>();
map.put("kim", "1234");

value = map.get("kim");

Java 9 부터는 한 줄의 문장을 사용하여 HashMaps를 초기화할 수 있습니다.

Map<Integer, String> map = Map.of("kim", "1234", "park", "pass", "lee", "word")

 

Map에 학생들의 데이터 저장하기

Map<String, String> map = new HashMap<String, String>();

map.put("kim", "1234");
map.put("park", "pass");
map.put("lee", "word");

System.out.println(map.get("lee"));

for(String key : map.keySet()){
	String value = map.get(key);
	System.out.println("key=" + key + ", value=" + value );
}

map.remove(3);
map.put("choi", "password");
System.out.println(map);

 

 

Map의 반복문

 

1. for-each 구문과 keySet()

for(String key : map.keySet()){
	String value = map.get(key);
	System.out.println("key=" + key + ", value=" + value );
}

 

2. 반복자

Iterator<String> it = map.keySet().iterator();
while(it.hasNext()){
	String key = it.next();
	System.out.println("key=" + key + ", value=" + map.get(key));
}

 

3. stream 라이브러리

map.forEach((key,value) -> {
	System.out.println("key=" + key + ", value=" + value)
});