자료구조 클래스: ArrayList, LinkedList, HashMap, HashSet

자료구조

데이터 추가, 삭제, 검색을 효율적으로 할 수 있도록 만들어 놓은 구조

자료구조 클래스의 종류 : 리스트, 스택, 큐, 해쉬 테이블, 집합

1. 리스트 : 데이터를 1차원으로 늘어놓은 자료구조. 배열과 달리 데이터의 검색과 추가, 삭제 가능 

ArrayList LinkedList Vector

2. 스택 LinkedList Stack

3. 큐 LinkedList

4. 해쉬 테이블 :  데이터를 키(Key)로 검색이 가능하고, 키(Key), 값(Value) 한쌍으로 데이터 사용. HashMap HashTable

4. 집합 : 데이터가 중복 저장되지 않는 구조 HashSet

1. ArrayList

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

list.add("String타입");

ArrayList 예제)

package 자료구조;

import java.util.*;

public class ArrayListExample1 {

public static void main(String[] args) {

ArrayList<String> list = new ArrayList<String>(); // ArrayList 객체를 생성

list.add("포도"); // ArrayList에 3개의 데이터를 추가

list.add("딸기");

list.add("복숭아");

list.add(2, "키위");  // 해당 위치에 끼워넣음, 딸기 다음 복숭아 위치에

list.set(0, "오렌지"); // 해당 위치에 대신 넣음, 포도 키위로 변경

list.remove(1); // 해당 위치를 지움, 딸기 삭제

list.remove("키위"); // 키위를 아예 삭제

int num = list.size(); // .size는 개수를 나타내는 메소드

for (int cnt = 0; cnt < num; cnt++) {

String str = list.get(cnt); // get은 객체 속성값을 가져옴

System.out.println(str);

}

}

}

문제 1. ArrayList

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

ArrayList에 for문을 이용하여 5개의 먹고 싶은 음식을 키보드로 입력하고 아래와 같이 출력하시오. 

(키보드 입력 for, 출력 for로 작성)

1: XXX

2: XXX

3: XXX

4: XXX

5: XXX 

import java.util.*;
public class ArrayList_test01 {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

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

System.out.println("먹고싶은 음식 5개를 쓰시오.");
for (int cnt=0; cnt<5; cnt++) { 
    foodList.add(scan.next());

scan.close(); 

}

int num = foodList.size();
for (int cnt=0; cnt<num; cnt++) {
    String str = foodList.get(cnt);
    System.out.println((cnt+1)+": "+str);
    }
}
}

문제 2. ArrayList

ArrayList를 이용한 1.음식추가 2.음식삭제 3.음식목록 출력 0.종료 클래스 만들기

별도의 동작 클래스 만들어서 제작할 것

1) 메뉴를 출력하고 실행하는 메인 프로그램

package 자료구조;

import java.util.*;

public class ArrayListExam02exe {

public static void main(String[] args){

ArrayListExam02 obj = new ArrayListExam02();  // 메소드를 포함한 클래스를 사용하는 선언

Scanner scan = new Scanner(System.in);

int cmdNo;

String str ="";

while(true) {

System.out.print("1.음식추가 2.음식삭제 3.음식목록 출력 0.종료 "); // 1 음식 추가 2 음식 삭제 3 음식 목록 출력

cmdNo = scan.nextInt();

if(cmdNo == 1) {

System.out.println("추가할 음식:");

str = scan.next();

obj.foodAdd(str);

}

else if(cmdNo == 2) {

System.out.println("삭제할 음식:");

str = scan.next();

obj.foodRemove(str);

}

else if(cmdNo == 3) {

System.out.println("음식 목록:");

obj.foodListPrint();

}

else if(cmdNo == 0) {

System.out.println("종료");

scan.close();

break;

}

}

}

}

--------------------------------

2) 메뉴 추가, 삭제, 출력 메소드를 포함한 클래스

package 자료구조;

import java.util.ArrayList;

public class ArrayListExam02 {

public ArrayList<String> foodList = new ArrayList<String>();

public void foodAdd(String food) {  // 메뉴 추가 메소드

foodList.add(food);

}

public void foodRemove(String food) { // 메뉴 삭제 메소드

foodList.remove(food);

}

public void foodListPrint() {  // 메뉴 목록 출력 메소드

int num = foodList.size();

for(int i=0;i<num;i++) {

String str = foodList.get(i);

System.out.println(str);

}

}

}

2. LinkedList

ArrayList와 메소드 및 기본 사용법은 동일하나 객체 내부에서 일어나는 일이 다르다.

- 객체 생성시 데이터 저장 영역이 생기는 것이 아니라 서로 인접 데이터를 가리키는 방식으로 작동한다.

- LinkedList : 데이터 추가와 삭제가 빈번한 경우 ArrayList보다 성능이 우수

- ArrayList : 인덱스로 데이터 항목을 찾는 경우 배열을 이용하므로 LinkedList보다 우수하다.

ArrayList는 ArrayList<String> List = new ArrayList<String>(); 

// 객체 생성과 함께 데이터를 저장할 수 있는 영역이 생긴다.

LinkedList는 LinkedList<String> list = new LinkedList<String>(); 

// 객체 생성시 데이터 저장 영역이 생기지 않으며, 서로 인접 데이터를 가리키는 방식으로 작동된다.

예제) LinkedList의 사용 예

import java.util.LinkedList;

public class LinkedListExample2 {

public static void main(String[] args) {

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

list.add("포도"); // add는 추가

list.add("딸기");

list.add("복숭아");

list.add(2, "키위");

list.set(0, "오렌지"); // set은 변경

list.remove(1); // remove는 삭제

list.remove("키위");

int num = list.size();

for (int cnt = 0; cnt < num; cnt++) {

String str = list.get(cnt);

System.out.println(str);

}

}

}

1) 이터레이터(Iterator)를 이용한 데이터의 순차 접근

- LinkedList의 get 메소드는 데이터를 읽을 때 첫번째 데이터부터 링크를 따라가며 찾게 된다. (비효울적)

- 앞서 찾은 데이터의 위치를 기억하다가 다음 번에 그 다음 데이터를 읽는 Iterator 메소드를 쓰는 것이 효율적

Iterator<String> iterator = list.iterator();

iterator는 java.util 패키지의 인터페이스로,이 인터페이스 이름 뒤에는 타입 파라미터 <String>을 써야 한다.

(이 타입 파라미터는 LinkedList에서 사용한 타입 파라미터와 맞아야 한다.)

Iterator 객체를 얻은 다음에는 이 객체에 대해 next 메소드를 호출해서 LinkedList의 데이터를 순서대로 읽어올 수 있다.

String str = iterator.next();

.next(); 메소드는 처음 호출했을 때 리스트의 첫 번째 데이터를 리턴, 그 다음에는 2번째, 3번째에는 3번째 데이터를 리턴한다. 매번 첫번째 데이터부터 링크를 따라가며 찾는 것이 아니라 마지막에 읽은 데이터 위치를 기억하고 있다가 사용하므로 LinkedList에서 효율적이다.

next 메소드에는 더 이상 읽을 데이터가 없으면 NoSuchElementException을 발생시키므로 hasNext 메소드를 호출해서 더 읽을 데이터가 있는지 검사해야 한다. 데이터가 있을 때 true, 없을 때 false를 리턴한다.

while (iterator.hasNext()) { // hasNext 메소드 리턴값이 true일 동안 next 메소드를 반복 호출

String str = iterator.next(); // next 메소드를 반복 호출

 // next 메소드로 가져온 데이터를 처리하는 부분

}

예제) iterator의 사용 예

import java.util.Iterator;

import java.util.LinkedList;

public class LinkedListExample3 {

public static void main(String[] args) {

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

list.add("망고");

list.add("파인애플");

list.add("바나나");

Iterator<String> iterator = list.iterator(); // iterator 메소드를 호출하여 Iterator 객체를 얻는다.

while (iterator.hasNext()) { // Iterator 객체를 이용하여 리스트의 데이터를 순서대로 출력

String str = iterator.next();

System.out.println(str);

}

}

}

JDK 5.0부터 지원하는 향상된 for문으로 다음과 같이 리스트 객체를 사용할 수도 있다.

for (String str : list) { // 변수 타입 변수명 : 리스트 객체 순

 // next 메소드로 가져온 데이터를 처리하는 부분

}

이렇게 작성된 for문에서는 리스트 객체로부터 얻은 Iterator 객체를 이용해서 읽어온 데이터가 반복 실행 부분을 시작하기 전에 매번 str 변수에 자동으로 대입되기 때문에 iterator 메소드나 next, hasNext 메소드를 호출할 필요가 없다.

2) 스택(Stack)으로 사용할 수 있는 클래스

- 스택(Stack)은 리스트처럼 일차원적으로 데이터를 저장하는 자료구조. 데이터를 넣은 순서의 역순으로만 꺼낼 수 있다. (LIFO)

- LIFO(Last-In First-Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 입출력 방식

- LinkedList가 스택으로 사용하기에 가장 적합한 클래스.

LinkedList 클래스를 스택으로 사용하려면 먼저 스택에 넣을 데이터 타입을 정하고 그 타입을 파라미터로 삼아 LinkedList 객체를 생성해야 한다.

LinkedList<Integer> stack = new LinkedList<Inteter>(); 

LinkedList 객체를 스택으로 사용하려면 리스트의 어느쪽을 스택 입구로 사용할지도 정해야 한다.

1) 리스트의 앞 부분에 데이터를 추가, 삭제, 가져오는 LinkedList 메소드

addFirst, removeFirst, getFirst

2) 리스트의 끝 부분에 데이터를 추가, 삭제, 가져오는 LinkedList 메소드

addLast, removeLast, getLast

예제) LinkedList 클래스를 스택으로 사용하는 예

import java.util.LinkedList;

public class StackExample1 {

public static void main(String[] args) {

LinkedList<Integer> stack = new LinkedList<Integer>(); //스택으로 사용할 LinkedList 객체 생성

stack.addLast(new Integer(12)); // 리스트의 끝 부분을 스택 입구로 사용하여 추가

stack.addLast(new Integer(59));

stack.addLast(new Integer(7));

while(!stack.isEmpty()) { // 루프를 돌며 스택 데이터를 모두 가져와 출력

Integer num = stack.removeLast();

System.out.println(num);

}

}

}

※ isEmpty 메소드 : LinkedList 객체 안에 데이터가 하나도 없을 때 true, 하나라도 있으면 false를 리턴하는 메소드

3) 큐(Queue)로 사용할 수 있는 클래스

- 큐(queue)도 스택과 반대로 데이터를 넣은 순서와 같은 순서로만 꺼낼 수 있다.

- FIFO(First-In First-Out) : 가장 처음에 넣은 데이터를 가장 먼저 꺼내는 입출력 방식

- LinkedList가 큐로 사용하기에도 가장 적합한 클래스.

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

- LinkedList 객체를 생성 후 offer 메소드를 사용하여 이 객체에 데이터를 추가. queue.offer("토끼");

- poll 메소드는 큐에 있는 데이터를 제거하면서 가져옴 str = queue.poll();

- peek 메소드는 큐에 있는 데이터를 가져옴 str = queue.peek();

예제) LinkedList 클래스를 큐로 사용하는 예

import java.util.*;

public class QueueExample1 {

public static void main(String args[]) {

LinkedList<String> queue = new LinkedList<String>(); //큐로 사용할 LinkedList 객체 생성

queue.offer("토끼"); // 큐에 데이터 추가

queue.offer("사슴");

queue.offer("호랑이");

while(!queue.isEmpty()) {

String str = queue.poll(); // 큐의 데이터를 가져와 출력

System.out.println(str);

}

}

}

-----------------------------------------------------

3. Hashmap : key, value 데이터 구조

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

hashtable.put("해리", new Integer(95));

hashtable.put("마리", new Integer(85));

Integer num = hashtable.get("해리");

hashtable.remove("마리");

* JDK 최신 버전에서는 hashtable.put("해리", 95); 이런식으로 쓸 수도 있으나 기본문법은 new integer 꼭 넣음.

1) 사람의 이름을 표현하는 Name 클래스

package 자료구조;

public class Name {

String firstName;  // 이름

String lastName;  // 성

Name(String firstName, String lastName) {   // 이름과 성 생성자

this.firstName = firstName;

this.lastName = lastName;

} public boolean equals(Object obj) {   // equals 메소드를 추가

if (!(obj instanceof Name))

return false;

Name name = (Name) obj;

if (firstName.equals(name.firstName) && lastName.equals(name.lastName))

return true;

else

return false;

}

public int hashCode() {   hashCode 메소드 추가

return firstName.hashCode() + lastName.hashCode();

}

}

- HashMap 클래스의 put, get, remove 메소드는 해쉬 테이블에 있는 통 번호를 계산할 때 키 값에 대해 Object 클래스의 hashCode 메소드를 호출하며, 데이터가 있는 통을 찾은 뒤 똑같은 키 값을 갖는 데이터를 찾기 위해 equals 메소드를 사용한다.

- 직접 작성한 클래스를 해쉬 테이블의 키로 사용할 때엔 equals 메소드와 hashCode 메소드를 오버라이드 해야만 한다.

- hashCode 메소드를 오버라이드 하는 규칙은 서로 다른 객체이더라도 같은 필드 값을 갖는 객체이면 같은 값을 리턴하도록 만들면 된다.

-----------------------------------------------

2) HashMap 클래스의 실행 예제

package 자료구조;

import java.util.*;

public class HashMapExample2 {

public static void main(String[] args) {

HashMap<Name, Integer> hashtable = new HashMap<Name, Integer>();

// Name 클래스를 키로 HashMap 객체 생성

hashtable.put(new Name("해리", "포터"), new Integer(95)); // hashtable에 5개의 데이터 추가

hashtable.put(new Name("허마이오니", "그레인져"), new Integer(100));

hashtable.put(new Name("론", "위즐리"), new Integer(85));

hashtable.put(new Name("드레이코", "말포이"), new Integer(93));

hashtable.put(new Name("네빌", "롱버텀"), new Integer(70));

Integer num = hashtable.get(new Name("허마이오니", "그레인져")); // 키값으로 hashtable 데이터 찾아 출력

System.out.println("허마이오니 그레인져의 성적은?" + num);

}

}

-----------------------------------------------

3) 결과

허마이오니 그레인져의 성적은?100

HashMap의 데이터를 모두 가져와 출력

HashMap은 keySet 메소드로 키값을 얻어온 뒤 hasNext를 while문으로 돌려 key값을 set으로 가져와 출력해야만 한다.

Set keys = map.keySet();

Iterator<String> iterator = keys.iterator(); Iterator 사용, KeySet 메소드

while (iterator.hasNext()) { 

String key = (String)iterator.next(); // key 값 얻기

System.out.print("key=" + key + " / value = " + map.get(key));  // key값과 그에 해당하는 value값 출력

}

Set keys = menuInfo.keySet();

Iterator itKeys = keys.iterator();

while(itKeys.hasNext()){

String key = (String)itKeys.next();

Integer value = menuInfo.get(key);

System.out.println(key+":"+value);

}

문제 1.

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

hashMap.put("a사원", new Integer(33));
hashMap.put("b사원", new Integer(35));
hashMap.put("c사원", new Integer(47));
위에 hashMap을 사용해서 아래 메뉴의 기능을 구현하시오.

1: 실적 추가
사원명과 실적 키보드로 입력 후 처리 ( get(), put() )
2: 실적 출력 
사원명 키보드로 입력 ( get() )
0:종료

정답 A) 1개의 클래스 내에서 처리하는 경우

import java.util.*;
public class HashMapExam01 {
public static void main(String[] args) {

HashMap <String, Integer> hashMap = new HashMap<String, Integer>();
hashMap.put("a사원", new Integer(33));
hashMap.put("b사원", new Integer(35));
hashMap.put("c사원", new Integer(47));

Scanner in = new Scanner(System.in);
int cmdNum=0, amt=0;
String empName;

while(true) {
    System.out.println("1:실적추가 2:실적출력 0:종료");
    cmdNum = in.nextInt();

if(cmdNum == 1) {
System.out.print("사원명:");
empName = in.next();
System.out.print("실적:");
amt = in.nextInt();
Integer oldAmt = hashMap.get(empName);
hashMap.put(empName, (oldAmt + amt));
}

else if(cmdNum == 2) {
System.out.print("사원명:");
empName = in.next();
Integer prnAmt = hashMap.get(empName);
System.out.println("실적:"+prnAmt);
}

}

}
}

정답 B) 클래스 2개로 나눠서 할 경우

1) 메뉴를 띄우고 실행하는 프로그램

package 자료구조;
import java.util.HashMap;
import java.util.Scanner;

public class HashMap_test01 { 
    public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    HashMap_test01_class obj = new HashMap_test01_class();
    int cmdNo; // 메뉴 넘버
    String str; // 입력받을 사원명
    int performance; // 입력받을 실적

while(true) {
    System.out.print("1.실적추가 2.실적출력 0.종료 ");
    cmdNo = scan.nextInt();

    if(cmdNo == 1) {
    System.out.print("실적 추가할 사원명: ");
    str = scan.next();
    System.out.print("실적 입력: "); 
    performance = scan.nextInt();
    obj.PerfomanceAdd(str, performance);
    }
    else if(cmdNo == 2) {
    System.out.print("실적 출력할 사원명: ");
    str = scan.next(); 
    obj.PerfomancePrint(str); 
    }
    else if(cmdNo == 0) {
    scan.close();
    System.out.println("종료");
    break;
    }
} 
} 
}
------------------------------------

2) 실적을 추가, 출력하는 메소드를 포함하는 클래스

// 클래스 내에서 HashMap 사용시에는 클래스명으로 생성자 처리

package 자료구조;

import java.util.HashMap;
public class HashMap_test01_class {
HashMap<String, Integer> hashmap = new HashMap<String, Integer>();

public HashMap_test01_class(){     클래스명과 같은 생성자로 처리할 것
    hashmap.put("a", new Integer(33));
    hashmap.put("b", new Integer(35));
    hashmap.put("c", new Integer(47));
}

public void PerfomanceAdd(String name, int perform) {
    Integer oldAmt = hashmap.get(name); // 기존 실적 입력받은 사원명에 담기
    hashmap.put(name, (oldAmt + perform)); // 기존 실적+입력 실적 합산 
    }

public void PerfomancePrint(String name) { 
    Integer prnAmt = hashmap.get(name); // 기존 실적 출력
    System.out.println(name+"사원의 실적:"+prnAmt);
    } 
}

--------------------------------------------------------------------------------------------------------

4. HashSet (집합)

집합으로 사용. 똑같은 값을 저장할 수 없다. (p556 참조)

HashSet 클래스는 내부에 있는 해쉬 테이블에 데이터를 저장한다.

HashSet<String> set = new HashSet<String>();

set.add("자바");

int num = set.size();  // 저장된 데이터 수

iterator 메소드

집합에는 데이터 순서가 없기 때문에 데이터를 읽어오려면 iterator 메소드를 사용해야만 한다.

Iterator it = set.iterator();  // 데이터를 읽어옴

while(it.hasNext()){     // hasNext는 다음 데이터가 있는지 없는지 체크한다.

String str = it.next();  읽어온 자료형을 변수에 담음

}

package 자료구조;

import java.util.*;

class SetExample1 {

    public static void main(String args[]) {

        HashSet<String> set = new HashSet<String>();  // 집합으로 사용할 HashSet 객체 생성

        set.add("자바");  // 집합에 데이터를 저장

        set.add("카푸치노");

        set.add("에스프레소");

        set.add("자바");

        System.out.println("저장된 데이터의 수 = " + set.size());

        Iterator<String> iterator = set.iterator(); // 집합에 있는 데이터를 모두 가져와서 출력

        while (iterator.hasNext()) {

            String str = iterator.next();

            System.out.println(str);

        }

    }

}

-----------------------------------------------------------------------------------------