Data Distructure(자료구조)
Collection Framework(컬렉션 프레임워크)
1. List : 인터페이스
- 동일한 데이터의 중복을 허용한다.
- 데이터 저장 순서가 유지된다.
- 힙(heap) 영역 내에서 List는 객체를 일렬로 늘어놓은 구조를 하고 있다.
- 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있다. 이 때 List 컬렉션은 객체 자체를 저장하여 인덱스를 부여하는 게 아니라, 해당하는 인덱스에 객체의 주소값을 참조하여 저장한다.
- List 컬렉션에서 공통적으로 사용가능한 추가, 검색, 삭제 메소드를 갖고있다.
<Arraylist>
| List<T> list = new Arraylist<T>(n); |
import java.util.*;
public class Examples {
public static void main(String[] args){
int size;
List<String> list = new ArrayList<String>(); //자동으로 10개 공간 생성
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
list.add("F");
list.add("G");
list.add("H");
list.add("I");
list.add(1, "J");
size = list.size();
System.out.println("저장된 객체 수 : "+ size);
for(int i=0; i<size; i++){
//데이터를 인덱스로 관리
System.out.print(i + "번째 : " + list.get(i));
System.out.println();
}
System.out.println();
System.out.println("----------------변경 후----------------");
System.out.println();
list.remove(1);
list.remove(1);
size = list.size();
for(int i=0; i<size; i++){
System.out.print(i + "번째 : " + list.get(i));
System.out.println();
}
}
}
List<String> list = new ArrayList<String>();
: 기본 생성자로 ArrayList 객체를 생성 -> 내부에 10개의 객체를 저장할 수 있는 초기 용량이 생성됨
list.add("more");
: 11번째의 객체를 추가 -> list가 참조하는 ArrayList 컬렉션에 10*2+2 = 22개의 객체를 저장할 수 있는 공간이 자동으로 생성
List<String> list = new ArrayList<String>(40);
: 배열과 마찬가지로, 용량을 초기화하여 원하는 만큼의 객체를 저장할 수 있다.
list.remove(1);
: 중간에 위치한 객체를 삭제 -> 인덱스를 자동으로 업데이트 해준다. 인덱스 1 이 처음 삭제된 후, 뒤의 객체들이 앞으로 한 칸씩 이동하며 그 자리를 자동으로 메꾸는 형태가 된다.
list.get(i)
: list.add(); 로 저장되는 모든 데이터는 Object 타입의 객체이므로, String 형 변수에 get해온 값을 담고 싶다면 String alphabet = (String)list.get(i) 와 같은 형변환을 반드시 해야한다. 동일한 데이터 타입으로 형변환해주는 것은 필수!
저장 공간 부족으로 ArrayList의 용량을 늘리게 되는 경우, 기존의 ArraList에 추가하는 것이 아닌 확장된 크기의 ArrayList를 새로 생성하고 새로 생성된 ArrayList에 기존의 ArrayList 값들을 복사해주는 과정을 거친다.
그리고 기존의 ArrayList는 가비지 컬렉션에 의해 메모리에서 제거된다.
따라서 ArrayList에서 용량을 늘린다는 것은 새로운 배열 인스턴스의 생성과 기존 데이터의 복사가 필요한 번거로운 작업이 되는 것이다.
<LinkedList>
따라서, LinkedList는 특정 인덱스의 객체를 제거하거나 삽입하면, 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
그러므로 중간 삽입/삭제가 빈번할 수록 LinkedList를 쓰는 것이 효율적이다.
반대로, 순차적인 삽입/삭제가 빈번하다면 ArrayList를 사용하는 것이 효율적이다.
LinkedList를 생성할 때, 처음에는 어떠한 링크도 만들어지지 않기 때문에 내부적으로 비어있다. 아래와 같은 코드로 생성할 수 있다.
| List<E> list = new LinkedList<E>(); |
자바에서 LinkedList 클래스는 스택과 큐를 구현하는 데 자주 쓰인다.
큐는 자바에서 일반적으로 두가지 방법으로 구현
- 배열을 사용하여 구현
- LinkedList나 ArrayList 클래스를 사용
* LinkedList -> Queue 자료구조 구현
List<E> list = new LinkedList<E>(); 로 선언을 권장했던 기존 자료구조 코드들와는 달리,
큐를 구현할 때 사용하는 메소드를 집어넣기 위해서는 반드시 LinkedList<E> list = new LinkedList<E>(); 라는 생성자를 사용해야한다.
즉, offer(), poll(), peek() 와 같은 메소드가 List인터페이스에서 제공되지 않는 LinkedList클래스만의 것이다.
import java.util.*;
class QueueExample{
public void method(){
LinkedList<Integer> queue = new LinkedList<Integer>();
//Queue에 삽입
queue.offer(11);
queue.offer(22);
queue.offer(33);
queue.offer(44);
queue.offer(55);
System.out.println(queue);
System.out.println(queue.poll()); //Queue에서 맨 앞 요소 제거하며 읽기
System.out.println(queue);
System.out.println(queue.peek()); //Queue에서 제거하지 않고 맨 뒤 요소 읽기
System.out.println();
ListIterator<Integer> it = queue.listIterator();
if(it.hasNext()){
System.out.println(it.next());
System.out.println(it.next());
System.out.println(it.previous());
System.out.println(it.previous());
}
}
}
public class Sample {
public static void main(String[] args){
QueueExample ex = new QueueExample();
ex.method();
}
}
/*
----------------------------------print----------------------------------
[11, 22, 33, 44, 55]
11
[22, 33, 44, 55]
22
22
33
33
22
-------------------------------------------------------------------------
*/
Queue(큐)
: FIFO, 선입선출 방식
- offer(); 메소드를 사용하여 Queue에 요소를 삽입
- poll() : Queue에서 맨 처음 요소를 제거하며 출력
- peek() : Queue에서 제거하지 않고 맨 뒤 요소를 출력
2. Set : 인터페이스
- 데이터의 저장 순서를 유지하지 않는다.
- 같은 데이터의 중복 저장을 허용하지 않는다. 따라서 null도 하나의 null만 저장할 수 있다.
- Set 컬렉션은 List 컬렉션처럼 인덱스로 객체를 검색해서 가져오는 메소드가 없다. 대신 전체 객체를 대상으로 한 번 씩 다 가져오는 반복자, Iterator을 제공한다.
|
Set<String> setExample = new...;
Iterator<String> iterator = setExample.iterator();
|
이 코드를 구현하여 iterator객체를 통해 사용할 수 있다.
|
1
2
3
4
5
6
|
Set<String> setExample = new...;
Iterator<String> iterator = setExample.iterator();
while(iterator.hasNext()){
String getin = iterator.next();
}
|
보통 위 같은 방식으로, iterator 인터페이스에 선언된 hasNext()와 next() 메소드를 사용하여 구현한다.
Set 인터페이스를 구현한 주요 클래스는 3개가 있다.
| Class | 특징 |
| HashSet | 순서가 필요없는 데이터를 hash table에 저장. Set 중에 가장 성능이 좋음. |
| TreeSet | 저장된 데이터의 값에 따라 정렬됨. red-black tree 타입으로 값이 저장됨. HashSet보다 성능이 느림. |
| LinkedHashSet | 연결된 목록 타입으로 구현된 hash table에 데이터 저장. 저장된 순서에 따라 값이 정렬되나 셋 중 가장 느림 |
3개의 클래스의 성능 차이는 클래스 때문인데, 셋 중 HashSet이 특히 큰 dataset에서, 별도의 정렬작업이 없기 때문에 가장 빠르다.
또한 JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘을 사용하였기 때문에 매우 빠른 검색 속도를 가진다.
<HashSet>
* 해시 알고리즘 (hash algorithm)
: HashSet에서 사용하는 알고리즘으로, 해시 함수(hash function)를 사용하여 데이터를 해시 테이블에 저장하고 다시 그것을 검색하는 방식
자바에서 해시 알고리즘을 이용한 자료구조는 위의 그림과 같이 배열과 연결 리스트로 구현된다.
저장할 key값과 value를 넣으면 해시함수는 int index = key.hashCode() % capacity 연산으로 배열의 인덱스를 구하여 해당 인덱스에 저장된 연결 리스트에 데이터를 저장하게 된다.
ex) key = 16이라면, hashCode() 메소드가 해당하는 int값을 그대로 반환하며, 16크기의 배열이 존재하므로 이 key의 인덱스는 16%16 = 0 이 된다. 따라서 첫번째 요소에 연결된 연결 리스트에서 검색을 시작한다.
HashSet의 기본 생성자는 다음과 같다.
| Set<E> set = new HashSet<E>(); |
HashSet는 순서 없이, 동일한 객체의 중복 저장 없이 저장을 수행한다.
따라서 add() 메소드를 사용하여 해당 HashSet에 이미 존재하고 있는 요소를 추가하려하면, 해당하는 요소를 바로 저장하지 않고 내부적으로 객체의 hashCode()메소드와 equals() 메소드를 호출하며 검사한다.
이 때 사용하는 hashCode()와 equals() 코드는 자신이 정의한 클래스 인스턴스에 대해 프로그래머가 직접 오버라이딩하여 구현할 수 있다.
String 클래스에서도 두 메소드를 오버라이딩해서 사용한다.
문자열을 HashSet에 저장할 경우, 같은 문자열을 갖는 String 객체는 동등한 객체로, 다른 문자열을 갖는 String 객체는 다른 객체로 간주된다. 그 이유는 String 클래스가 hashCode()와 equals()메소드를 오버라이딩하여, 같은 문자열일 경우 hashCode()의 리턴값을 같게, equals()의 리턴값은 true로 나오도록 구현해놓았기 때문이다.
3. Map : 인터페이스
Map 컬렉션에는 키(key)와 값(value)으로 구성된 Entry 객체를 저장하는 구조를 가지고 있다. 여기서 키와 값은 모두 객체이다.
값은 중복 저장이 가능하지만, 키는 중복 저장이 불가능하다. Set과 마찬가지로, Map 컬렉션에서는 키 값의 중복 저장이 허용되지 않는 데, 만약 중복 저장 시 먼저 저장된 값은 저장되지 않은 상태가 된다. 즉, 기존 값은 없어지고 새로운 값으로 대체되는 것이다.
HashSet에서처럼, 프로그래머는 HashMap과 HashTable 모두 키로 사용할 객체에 대해 hashCode()와 equals() 메소드를 오버라이딩하여 같은 객체가 될 조건을 정의할 수 있다.
<HashMap>
Map 인터페이스 구현을 위해 해시테이블을 사용한 클래스
- 중복을 허용하지 않고 순서를 보장하지 않는다.
- HashTable과 다르게 HashMap 은 키와 값으로 null 이 허용된다.
* HashMap의 생성자 생성 방법
| Map<K,V> map = new HashMap<K,V>(); |
ex) 제네릭 해시맵(HashMap)을 이용하여 전화번호 관리 프로그램을 만들었다.
Phone 클래스는 전화번호 정보를 표현한 필드를 담은 클래스로, value에 해당한다.
따라서 value는 Phone 타입, key값은 name 필드이다.
import java.util.*;
class Phone{
private String name;
private String address;
private String telephone;
Phone(String name, String address, String telephone){
this.name = name;
this.address= address;
this.telephone = telephone;
}
public String getName(){ return name; }
public String getAddress(){ return address; }
public String getTelephone(){ return telephone; }
}
public class TelManagement {
//삽입
public static void insert(HashMap<String, Phone> map){
Phone p;
String name, address, telephone;
Scanner s = new Scanner(System.in);
System.out.print("이름 >> ");
name = s.next();
System.out.print("주소 >> ");
address = s.next();
System.out.print("전화번호 >> ");
telephone = s.next();
p = new Phone(name, address, telephone);
map.put(p.getName(), p);
}
//삭제
public static void delete(HashMap<String, Phone> map){
String deletename;
Scanner s = new Scanner(System.in);
System.out.print("이름>> ");
deletename = s.next();
if(map.containsKey(deletename)){
map.remove(deletename);
System.out.println("삭제가 정상적으로 완료되었습니다.");
}
else System.out.println(deletename + "은 등록되지 않은 사람입니다.");
}
//찾기
public static void search(HashMap<String, Phone> map){
Scanner s = new Scanner(System.in);
String searchname;
System.out.print("이름 >> ");
searchname = s.next();
if(map.containsKey(searchname))
System.out.println(searchname + " " + map.get(searchname).getAddress() + " "
+ map.get(searchname).getTelephone());
else System.out.println(searchname + "은 등록되지 않은 사람입니다. ");
}
//전체보기
public static void printall(HashMap<String, Phone> map){
Set<String> names = map.keySet();
Iterator<String> it = names.iterator();
while(it.hasNext()){
String name = it.next();
Phone student = map.get(name);
System.out.println(name + " " + student.getAddress() + " " + student.getTelephone());
}
}
//main
public static void main(String[] args){
int menu;
HashMap<String, Phone> map = new HashMap<String, Phone>();
Scanner s = new Scanner(System.in);
System.out.println("----------------------------------------------------");
System.out.println(" 전화번호 관리 프로그램을 시작합니다. ");
System.out.println("----------------------------------------------------");
while(true){
System.out.print("삽입:0, 삭제:1, 찾기:2, 전체보기:3, 종료:4 >> ");
menu = s.nextInt();
switch(menu){
case 0:
insert(map);
break;
case 1:
delete(map);
break;
case 2:
search(map);
break;
case 3:
printall(map);
break;
case 4:
System.out.println("프로그램을 종료합니다.");
return;
default:
System.out.println("잘못 입력하셨습니다. 다시 입력해주세요.");
}
}
}
}
HashMap을 포함한 Map 컬렉션에서 Key값을 알고 싶다면 get() 메소드로 쉽게 구현하여 알아 낼 수 있다.
하지만 맵 안에 존재하는 value를 포함한 데이터 하나하나를 전부 얻어내 출력하고 싶다면, 그 방법은 2가지가 있다.
첫번째는, 위의 코드(66 line)에서 구현한대로 Key를 Set 타입으로 뽑아 그 Key들을 하나하나 iterator 로 반복하여그 Key 값을 통해 value를 얻어내는 방법이다.
두번째 방법은 entrySet을 통해 Entry 객체를 Set 타입으로 뽑아, Key와 value를 동시에 한번에 얻어낼 수 있는 방법이다.
public static void printall(HashMap<String, Phone> map){
Set<Map.Entry<String, Phone>> entries = map.entrySet();
Iterator<Map.Entry<String, Phone>> it = entries.iterator();
while(it.hasNext()){
Map.Entry<String, Phone> mapEntry = it.next();
System.out.println(mapEntry.getKey() + " " + mapEntry.getValue().getAddress() + " " + mapEntry.getValue().getTelephone());
}
}
위의 코드는 DTO를 활용한 데이터 처리 방식을 채택하였다. 일반적으로 대량 데이터를 효율적으로 관리하기 위해 DTO(Data Transfer Object) 클래스와 컬렉션 API를 함께 사용하는 데, DTO는 이 때 데이터의 교환을 위한 객체를 의미한다.
즉, Phone 클래스는 DTO 클래스로 설계되었다 할 수 있다.
