[Java] java 자료구조
목차
작성일: 2021-03-21
01. 여러 가지 자료구조에 대해 알아봅시다
자료구조란 무엇인가? (Data Structure)
- 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들이다.
- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다.
- 자료의 효율적인 관리는 프로그램의 수행 속도와 밀접한 관련이 있다.
- 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로, 자료구조에 대한 이해가 중요하다.
자료구조에는 어떤 것들이 있나?
선형 자료구조 (한 줄로 자료를 관리)
배열 (Array): 선형으로 자료를 관리한다. 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같다.
연결 리스트 (LinkedList): 선형으로 자료를 관리한다. 자료가 추가될 때마다 메모리를 할당받고, 자료는 링크로 연결된다. 자료의 물리적 위치와 논리적 위치가 다를 수 있다.
리스트에 자료 추가하기
리스트에서 자료 삭제하기
스택 (Stack): 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료구조 (Last In First Out)
큐 (Queue): 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료구조 (First In First Out)
트리 (Tree)
부모 노드와 자식 노드 간의 연결로 이루어진 자료구조다.
힙 (heap): 우선순위 큐(Priority Queue)를 구현한다. 우선순위 큐는 우선순위가 높은 순으로 꺼내므로 힙을 이용해서 구현한다. (최대 힙은 부모 노드가 자식 노드보다 항상 크기 때문이며, 반대인 최소 힙으로도 가능하다.)
- Max heap: 부모 노드가 자식 노드보다 항상 크거나 같은 값을 갖는 경우
- Min heap: 부모 노드가 자식 노드보다 항상 작거나 같은 값을 갖는 경우
heap 정렬에 활용할 수 있다.
이진 트리 (binary tree): 부모 노드에 자식 노드가 두 개 이하인 트리
이진 검색 트리 (binary search tree)
- 자료(key)의 중복을 허용하지 않는다.
- 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가진다.
- 자료 검색에 걸리는 시간이 평균 log(n)이다.
- inorder traversal 탐색을 하면 자료가 정렬되어 출력된다.
예) [23, 10, 28, 15, 7, 22, 56] 순으로 자료를 넣을 때의 BST
나중에 TreeSet이나 TreeMap을 할 때 Comparable 인터페이스를 구현해서 비교하게끔 구현할 것이다.
- JDK 클래스: TreeSet, TreeMap (Tree로 시작되는 클래스는 정렬을 지원한다.)
그래프 (Graph)
정점과 간선들의 유한 집합 G = (V, E)이다. 네비게이션, 구글맵 등이 모두 그래프에 기반해서 구현된다.
- 정점(vertex): 여러 특성을 가지는 객체, 노드(node)
- 간선(edge): 객체들을 연결하는 관계를 나타냄. 링크(link)
- 간선은 방향성이 있는 경우와 없는 경우가 있다. (노드와 노드를 연결하는 것을 edge나 link라고 한다.)
- 그래프를 구현하는 방법: 인접 행렬(adjacency matrix), 인접 리스트(adjacency list)
- 그래프를 탐색하는 방법: BFS(breadth first search), DFS(depth first search)
그래프의 예)
해싱 (Hashing)
자료를 검색하기 위한 자료구조다.
- 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료구조
- key는 유일하고, 이에 대한 value를 쌍으로 저장
index = h(key): 해시 함수가 key에 대한 인덱스를 반환해주며, 해당 인덱스 위치에 자료를 저장하거나 검색- 해시 함수에 의해 인덱스 연산이 산술적으로 가능하여 O(1)
- 저장되는 메모리 구조를 해시 테이블이라 함
- JDK 클래스: HashMap, Properties
키는 중복되지 않으며, 나머지를 구하는 것이 대표적인 해시 함수다(예: 123 % 100을 해서 23번째 자리에 저장).
해시 테이블
체이닝
해시 정리:
- 해시는 키에 대한 밸류가 있다.
- 키는 유일하여 중복될 수 없다.
- 해시는 들어가는 순서와 상관이 없다.
- 배열과 비슷하게 생겨서 많이 오해하는데, 해시 함수에 의해 위치가 정해지므로 순서와는 무관하다.
02. 배열(Array) 구현하기
Array의 특징
- 동일한 데이터 타입을 순서에 따라 관리하는 자료구조
- 정해진 크기가 있음
- 요소의 추가와 제거 시 다른 요소들의 이동이 필요함
- 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름
- JDK 클래스: ArrayList, Vector
Array 구현하기
MyArray.java
public class MyArray {
int[] intArr; //int array
int count; //개수
public int ARRAY_SIZE;
public static final int ERROR_NUM = -999999999;
public MyArray()
{
count = 0;
ARRAY_SIZE = 10;
intArr = new int[ARRAY_SIZE];
}
public MyArray(int size)
{
count = 0;
ARRAY_SIZE = size;
intArr = new int[size];
}
public void addElement(int num)
{
if(count >= ARRAY_SIZE){
System.out.println("not enough memory");
return;
}
intArr[count++] = num;
}
public void insertElement(int position, int num)
{
int i;
if(count >= ARRAY_SIZE){ //꽉 찬 경우
System.out.println("not enough memory");
return;
}
if(position < 0 || position > count ){ //index error
System.out.println("insert Error");
return;
}
for( i = count-1; i >= position ; i--){
intArr[i+1] = intArr[i]; // 하나씩 이동
}
intArr[position] = num;
count++;
}
public int removeElement(int position)
{
int ret = ERROR_NUM;
if( isEmpty() ){
System.out.println("There is no element");
return ret;
}
if(position < 0 || position >= count ){ //index error
System.out.println("remove Error");
return ret;
}
ret = intArr[position];
for(int i = position; i<count -1; i++ )
{
intArr[i] = intArr[i+1];
}
count--;
return ret;
}
public int getSize()
{
return count;
}
public boolean isEmpty()
{
if(count == 0){
return true;
}
else return false;
}
public int getElement(int position)
{
if(position < 0 || position > count-1){
System.out.println("검색 위치 오류. 현재 리스트의 개수는 " + count +"개 입니다.");
return ERROR_NUM;
}
return intArr[position];
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
for(int i=0; i<count; i++){
System.out.println(intArr[i]);
}
}
public void removeAll()
{
for(int i=0; i<count; i++){
intArr[i] = 0;
}
count = 0;
}
}MyArrayTest.java
public class MyArrayTest {
public static void main(String[] args) {
MyArray array = new MyArray();
array.addElement(10);
array.addElement(20);
array.addElement(30);
array.insertElement(1, 50);
array.printAll();
System.out.println("===============");
array.removeElement(1);
array.printAll();
System.out.println("===============");
array.addElement(70);
array.printAll();
System.out.println("===============");
array.removeElement(1);
array.printAll();
System.out.println("===============");
System.out.println(array.getElement(2));
}
}MyObjectArray.java
public class MyObjectArray {
private int cout;
private Object[] array;
public int ARRAY_SIZE;
public MyObjectArray()
{
ARRAY_SIZE = 10;
array = new Object[ARRAY_SIZE];
}
public MyObjectArray(int size)
{
ARRAY_SIZE = size;
array = new Object[ARRAY_SIZE];
}
}02. 연결 리스트 (LinkedList) 구현하기
LinkedList 특징
- 동일한 데이터 타입을 순서에 따라 관리하는 자료구조
- 자료를 저장하는 노드에는 자료와, 다음 요소를 가리키는 링크(포인터)가 있음
- 자료가 추가될 때 노드만큼의 메모리를 할당받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
- 연결 리스트의 i 번째 요소를 찾는 데 걸리는 시간은 요소의 개수에 비례: O(n)
- JDK 클래스: LinkedList
LinkedList 구현하기
MyListNode.java
public class MyListNode {
private String data; // 자료
public MyListNode next; // 다음 노드를 가리키는 링크
public MyListNode(){
data = null;
next = null;
}
public MyListNode(String data){
this.data = data;
this.next = null;
}
public MyListNode(String data, MyListNode link){
this.data = data;
this.next = link;
}
public String getData(){
return data;
}
}MyLinkedList.java
public class MyLinkedList {
private MyListNode head;
int count;
public MyLinkedList()
{
head = null;
count = 0;
}
public MyListNode addElement( String data )
{
MyListNode newNode;
if(head == null){ //맨 처음일때
newNode = new MyListNode(data);
head = newNode;
}
else{
newNode = new MyListNode(data);
MyListNode temp = head;
while(temp.next != null) //맨 뒤로 가서
temp = temp.next;
temp.next = newNode;
}
count++;
return newNode;
}
public MyListNode insertElement(int position, String data )
{
int i;
MyListNode tempNode = head;
MyListNode newNode = new MyListNode(data);
if(position < 0 || position > count ){
System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 앞으로 들어가는 경우
newNode.next = head;
head = newNode;
}
else{
MyListNode preNode = null;
for(i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next;
}
newNode.next = preNode.next;
preNode.next = newNode;
}
count++;
return newNode;
}
public MyListNode removeElement(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 앞을 삭제하는
head = tempNode.next;
}
else{
MyListNode preNode = null;
for(i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next;
}
preNode.next = tempNode.next;
}
count--;
System.out.println(position + "번째 항목 삭제되었습니다.");
return tempNode;
}
public String getElement(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return new String("error");
}
if(position == 0){ //맨 인 경우
return head.getData();
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode.getData();
}
public MyListNode getNode(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 인 경우
return head;
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode;
}
public void removeAll()
{
head = null;
count = 0;
}
public int getSize()
{
return count;
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
MyListNode temp = head;
while(temp != null){
System.out.print(temp.getData());
temp = temp.next;
if(temp!=null){
System.out.print("->");
}
}
System.out.println("");
}
public boolean isEmpty()
{
if(head == null) return true;
else return false;
}
}MyLinkedListTest.java
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addElement("A");
list.addElement("B");
list.addElement("C");
list.printAll();
list.insertElement(3, "D");
list.printAll();
list.removeElement(0);
list.printAll();
list.removeElement(1);
list.printAll();
list.insertElement(0, "A-1");
list.printAll();
System.out.println(list.getSize());
list.removeElement(0);
list.printAll();
System.out.println(list.getSize());
list.removeAll();
list.printAll();
list.addElement("A");
list.printAll();
System.out.println(list.getElement(0));
list.removeElement(0);
}
}03. 스택(Stack) 구현하기
Stack의 특징
- 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있음 (중간의 자료를 꺼낼 수 없음)
- Last In First Out (후입선출) 구조
- 택배 상자가 쌓여 있는 모양
- 가장 최근의 자료를 찾아오거나, 게임에서 히스토리를 유지하고 이를 무를 때 사용할 수 있음
- 함수의 메모리는 호출 순서에 따른 stack 구조
- JDK 클래스: Stack
배열을 활용하여 Stack 구현하기
MyArrayStack.java
import array.MyArray;
public class MyArrayStack {
int top;
MyArray arrayStack;
public MyArrayStack()
{
top = 0;
arrayStack = new MyArray();
}
public MyArrayStack(int size)
{
arrayStack = new MyArray(size);
}
public void push(int data)
{
if(isFull()){
System.out.println("stack is full");
return;
}
arrayStack.addElement(data);
top++;
}
public int pop()
{
if (top == 0){
System.out.println("stack is empty");
return MyArray.ERROR_NUM;
}
return arrayStack.removeElement(--top);
}
public int peek()
{
if (top == 0){
System.out.println("stack is empty");
return MyArray.ERROR_NUM;
}
return arrayStack.getElement(top-1);
}
public int getSize()
{
return top;
}
public boolean isFull()
{
if(top == arrayStack.ARRAY_SIZE){
return true;
}
else return false;
}
public boolean isEmpty()
{
if (top == 0){
return true;
}
else return false;
}
public void printAll()
{
arrayStack.printAll();
}
}MyArrayStackTest.java
public class MyArrayStackTest {
public static void main(String[] args) {
MyArrayStack stack = new MyArrayStack(3);
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.printAll();
System.out.println("top element is " + stack.pop());
stack.printAll();
System.out.println("stack size is " + stack.getSize());
}
}04. 큐(Queue) 구현하기
Queue의 특징
- 맨 앞(front)에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가함
- First In First Out (선입선출) 구조
- 일상생활에서 일렬로 줄 서 있는 모양
- 순차적으로 입력된 자료를 순서대로 처리하는 데 많이 사용되는 자료구조
- 콜센터에 들어온 문의 전화, 메시지 큐 등에 활용됨
- JDK 클래스: ArrayList
연결 리스트를 활용하여 Queue 구현하기
MyListQueue.java
import linkedlist.MyListNode;
import linkedlist.MyLinkedList;
interface IQueue{
public void enQueue(String data);
public String deQueue();
public void printAll();
}
public class MyListQueue extends MyLinkedList implements IQueue{
MyListNode front;
MyListNode rear;
public MyListQueue()
{
front = null;
rear = null;
}
public void enQueue(String data)
{
MyListNode newNode;
if(isEmpty()) //처음 항목
{
newNode = addElement(data);
front = newNode;
rear = newNode;
}
else
{
newNode = addElement(data);
rear = newNode;
}
System.out.println(newNode.getData() + " added");
}
public String deQueue()
{
if(isEmpty()){
System.out.println("Queue is Empty");
return null;
}
String data = front.getData();
front = front.next;
if( front == null ){ // 마지막 항목
rear = null;
}
return data;
}
public void printAll()
{
if(isEmpty()){
System.out.println("Queue is Empty");
return;
}
MyListNode temp = front;
while(temp!= null){
System.out.print(temp.getData() + ",");
temp = temp.next;
}
System.out.println();
}
}MyListQueueTest.java
public class MyListQueueTest {
public static void main(String[] args) {
MyListQueue listQueue = new MyListQueue();
listQueue.enQueue("A");
listQueue.enQueue("B");
listQueue.enQueue("C");
listQueue.enQueue("D");
listQueue.enQueue("E");
System.out.println(listQueue.deQueue());
listQueue.printAll();
}
}06. 무엇이든 담을 수 있는 제네릭(Generic) 프로그래밍
제네릭 자료형 정의
- 클래스에서 사용하는 변수의 자료형이 여러 개일 수 있고 그 기능(메서드)은 동일한 경우, 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정할 수 있도록 선언한다.
- 실제 사용되는 자료형의 변환은 컴파일러에 의해 검증되므로 안정적인 프로그래밍 방식이다.
- 컬렉션 프레임워크에서 많이 사용되고 있다.
제네릭 타입을 사용하지 않는 경우의 예:
재료가 Powder인 경우
public class ThreeDPrinter1{
private Powder material;
public void setMaterial(Powder material) {
this.material = material;
}
public Powder getMaterial() {
return material;
}
}재료가 Plastic인 경우
public class ThreeDPrinter2{
private Plastic material;
public void setMaterial(Plastic material) {
this.material = material;
}
public Plastic getMaterial() {
return material;
}
}여러 타입을 대체하기 위해 Object를 사용할 수 있다:
public class ThreeDPrinter{
private Object material;
public void setMaterial(Object material) {
this.material = material;
}
public Object getMaterial() {
return material;
}
}단, Object를 사용하는 경우는 형 변환을 해야 한다:
ThreeDPrinter printer = new ThreeDPrinter();
Powder powder = new Powder();
printer.setMaterial(powder);
Powder p = (Powder)printer.getMaterial();제네릭 클래스 정의:
GenericPrinter.java
public class GenericPrinter<T> {
private T material;
public void setMaterial(T material) {
this.material = material;
}
public T getMaterial() {
return material;
}
public String toString(){
return material.toString();
}
}- 자료형 매개변수 T(type parameter): 이 클래스를 사용하는 시점에 실제 사용할 자료형을 지정한다. static 변수에는 사용할 수 없다.
GenericPrinter<T>: 제네릭 자료형- E: element, K: key, V: value 등 여러 알파벳을 의미에 따라 사용할 수 있다.
제네릭 클래스 사용하기
Powder.java
public class Powder {
public String toString() {
return "재료는 Powder 입니다";
}
}Plastic.java
public class Plastic {
public String toString() {
return "재료는 Plastic 입니다";
}
}GenericPrinter.java
public class GenericPrinter<T> {
private T material; //T 자료형으로 선언한 변수
public void setMaterial(T material) {
this.material = material;
}
public T getMaterial() { //T 자료형을 반환하는 제네릭 메서드
return material;
}
public String toString(){
return material.toString();
}
}GenericPrinterTest.java
public class GeneriPrinterTest {
public static void main(String[] args) {
GenericPrinter<Powder> powderPrinter = new GenericPrinter<Powder>();
powderPrinter.setMaterial(new Powder());
System.out.println(powderPrinter);
GenericPrinter<Plastic> plasticPrinter = new GenericPrinter<Plastic>();
plasticPrinter.setMaterial(new Plastic());
System.out.println(plasticPrinter);
}
}다이아몬드 연산자 <>
<T>에서<>를 다이아몬드 연산자라 한다.ArrayList<String> list = new ArrayList<>();— 다이아몬드 연산자 내부에서 자료형은 생략 가능하다.- 제네릭에서 자료형 추론(자바 10부터):
ArrayList<String> list = new ArrayList<String>()=>var list = new ArrayList<String>();
07. <T extends 클래스> 사용하기
상위 클래스의 필요성
- T 자료형의 범위를 제한할 수 있음
- 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음
- 상속을 받지 않는 경우 T는 Object로 변환되어, Object 클래스가 기본으로 제공하는 메서드만 사용 가능
T extends 를 사용한 프로그래밍
GenericPrinter<T>에 material 변수의 자료형을 상속받아 구현- T에 무작위 클래스가 들어갈 수 없게, Material 클래스를 상속받은 클래스로 한정
Material.java
public abstract class Material {
public abstract void doPrinting();
}Powder.java
public class Powder extends Material{
public void doPrinting() {
System.out.println("Powder 재료로 출력합니다");
}
public String toString() {
return "재료는 Powder 입니다";
}
}Plastic.java
public class Plastic extends Material{
public void doPrinting() {
System.out.println("Plastic 재료로 출력합니다");
}
public String toString() {
return "재료는 Plastic 입니다";
}
}GenericPrinter.java
public class GenericPrinter<T extends Material> {
private T material;
public void setMaterial(T material) {
this.material = material;
}
public T getMaterial() {
return material;
}
public String toString(){
return material.toString();
}
public void printing() {
material.doPrinting();
}
}GenericPrinterTest.java
public class GenericPrinterTest {
public static void main(String[] args) {
GenericPrinter<Powder> powderPrinter = new GenericPrinter<Powder>();
powderPrinter.setMaterial(new Powder());
Powder powder = powderPrinter.getMaterial(); // 형변환 하지 않음
System.out.println(powderPrinter);
GenericPrinter<Plastic> plasticPrinter = new GenericPrinter<Plastic>();
plasticPrinter.setMaterial(new Plastic());
Plastic plastic = plasticPrinter.getMaterial(); // 형변환 하지 않음
System.out.println(plasticPrinter);
/* GenericPrinter powderPrinter2 = new GenericPrinter();
powderPrinter2.setMaterial(new Powder());
Powder powder = (Powder)powderPrinter.getMaterial();
System.out.println(powderPrinter);
*/
//GenericPrinter<Water> printer = new GenericPrinter<Water>();
}
}08. 제네릭 메서드 활용하기
제네릭 메서드란?
- 자료형 매개변수를 메서드의 매개변수나 반환 값으로 가지는 메서드다.
- 자료형 매개변수가 하나 이상인 경우도 있다.
- 제네릭 클래스가 아니어도 내부에 제네릭 메서드를 구현하여 사용할 수 있다.
- 형식:
public <자료형 매개 변수> 반환형 메서드 이름(자료형 매개변수.....) { }
제네릭 메서드의 활용 예
- 두 점(top, bottom)을 기준으로 사각형을 만들 때 사각형의 너비를 구하는 메서드를 만들어 보자.
- 두 점은 정수인 경우도 있고 실수인 경우도 있으므로, 제네릭 타입을 사용하여 구현한다.
Point.java
public class Point<T, V> {
T x;
V y;
Point(T x, V y){
this.x = x;
this.y = y;
}
public T getX() {
return x;
}
public V getY() {
return y;
}
}GenericMethod.java
public class GenericMethod {
public static <T, V> double makeRectangle(Point<T, V> p1, Point<T, V> p2) {
double left = ((Number)p1.getX()).doubleValue();
double right =((Number)p2.getX()).doubleValue();
double top = ((Number)p1.getY()).doubleValue();
double bottom = ((Number)p2.getY()).doubleValue();
double width = right - left;
double height = bottom - top;
return width * height;
}
public static void main(String[] args) {
Point<Integer, Double> p1 = new Point<Integer, Double>(0, 0.0);
Point<Integer, Double> p2 = new Point<>(10, 10.0);
double rect = GenericMethod.<Integer, Double>makeRectangle(p1, p2);
System.out.println("두 점으로 만들어진 사각형의 넓이는 " + rect + "입니다.");
}
}09. 자바에서 제공되는 자료구조 구현 클래스들 - 컬렉션 프레임워크
컬렉션 프레임워크
- 프로그램 구현에 필요한 자료구조(Data Structure)를 구현해 놓은 JDK 라이브러리
java.util패키지에 구현되어 있음- 개발에 소요되는 시간을 절약하면서 최적화된 알고리즘을 사용할 수 있음
- 여러 구현 클래스와 인터페이스의 활용에 대한 이해가 필요함
Collection 인터페이스
- 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스
- 하위에 List와 Set 인터페이스가 있음
List 인터페이스
- 객체를 순서에 따라 저장하고 관리하는 데 필요한 메서드가 선언된 인터페이스
- 자료구조 리스트(배열, 연결 리스트)의 구현을 위한 인터페이스
- 중복을 허용함
- ArrayList, Vector, LinkedList, Stack, Queue 등
Set 인터페이스
- 순서와 관계없이 중복을 허용하지 않고, 유일한 값을 관리하는 데 필요한 메서드가 선언됨
- 아이디, 주민번호, 사번 등을 관리하는 데 유용
- 저장된 순서와 출력되는 순서는 다를 수 있음
- HashSet, TreeSet 등
Map 인터페이스
- 쌍(pair)으로 이루어진 객체를 관리하는 데 사용하는 메서드들이 선언된 인터페이스
- 객체는 key-value의 쌍으로 이루어짐
- key는 중복을 허용하지 않음
- HashTable, HashMap, Properties, TreeMap 등이 Map 인터페이스를 구현함
10. 순차적으로 자료를 관리하는 List 인터페이스를 구현한 클래스와 그 활용
멤버십 관리하기
- Member 클래스를 만들고, 아이디와 이름을 멤버 변수로 선언한다.
- Member 클래스로 생성된 인스턴스들을 관리하는 클래스를 컬렉션 프레임워크 클래스들을 활용하여 구현한다.
ArrayList 활용하기
- 멤버를 순차적으로 관리한다.
Member.java
public class Member {
private int memberId; //회원 아이디
private String memberName; //회원 이름
public Member(int memberId, String memberName){ //생성자
this.memberId = memberId;
this.memberName = memberName;
}
public int getMemberId() { //
return memberId;
}
public void setMemberId(int memberId) {
this.memberId = memberId;
}
public String getMemberName() {
return memberName;
}
public void setMemberName(String memberName) {
this.memberName = memberName;
}
@Override
public String toString(){ //toString 메소드 오버로딩
return memberName + " 회원님의 아이디는 " + memberId + "입니다";
}
}MemberArrayList.java
public class MemberArrayList {
private ArrayList<Member> arrayList; // ArrayList 선언
public MemberArrayList(){
arrayList = new ArrayList<Member>(); //멤버로 선언한 ArrayList 생성
}
public void addMember(Member member){ //ArrayList 에 멤버 추가
arrayList.add(member);
}
public boolean removeMember(int memberId){ // 멤버 아이디를 매개변수로, 삭제 여부를 반환
for(int i =0; i<arrayList.size(); i++){ // 해당 아이디를 가진 멤버를 ArrayList에서 찾음
Member member = arrayList.get(i);
int tempId = member.getMemberId();
if(tempId == memberId){ // 멤버아이디가 매개변수와 일치하면
arrayList.remove(i); // 해당 멤버를 삭제
return true; // true 반환
}
}
System.out.println(memberId + "가 존재하지 않습니다"); //for 가 끝날때 까지 return 이 안된경우
return false;
}
public void showAllMember(){
for(Member member : arrayList){
System.out.println(member);
}
System.out.println();
}
}MemberArrayListTest.java
public class MemberArrayListTest {
public static void main(String[] args) {
MemberArrayList memberArrayList = new MemberArrayList();
Member memberLee = new Member(1001, "이순신");
Member memberKim = new Member(1002, "김유신");
Member memberKang = new Member(1003, "강감찬");
Member memberHong = new Member(1004, "홍길동");
memberArrayList.addMember(memberLee);
memberArrayList.addMember(memberKim);
memberArrayList.addMember(memberKang);
memberArrayList.addMember(memberHong);
memberArrayList.showAllMember();
memberArrayList.removeMember(memberHong.getMemberId());
memberArrayList.showAllMember();
}
}11. Collection 요소를 순회하는 Iterator
요소의 순회란?
- 컬렉션 프레임워크에 저장된 요소들을 하나씩 차례로 참조하는 것이다.
- 순서가 있는 List 인터페이스의 경우는 Iterator를 사용하지 않고
get(i)메서드를 활용할 수 있다. - Set 인터페이스의 경우
get(i)메서드가 제공되지 않으므로 Iterator를 활용하여 객체를 순회한다.
Iterator 사용하기
boolean hasNext(): 이후에 요소가 더 있는지 체크하는 메서드. 요소가 있다면 true를 반환한다.E next(): 다음에 있는 요소를 반환한다.
MemberArrayList.java의 removeMember() 메서드를 Iterator를 활용하여 구현:
public boolean removeMember(int memberId){ // 멤버 아이디를 매개변수로, 삭제 여부를 반환
Iterator<Member> ir = arrayList.iterator();
while(ir.hasNext()) {
Member member = ir.next();
int tempId = member.getMemberId();
if(tempId == memberId){ // 멤버아이디가 매개변수와 일치하면
arrayList.remove(member); // 해당 멤버를 삭제
return true; // true 반환
}
}
System.out.println(memberId + "가 존재하지 않습니다"); //for 가 끝날때 까지 return 이 안된경우
return false;
}12. 중복되지 않게 자료를 관리하는 Set 인터페이스를 구현한 클래스와 그 활용
HashSet 클래스
- Set 인터페이스를 구현한 클래스다.
- 멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 한다.
- 동일성 구현을 위해 필요에 따라
equals()와hashCode()메서드를 재정의한다.
HashSetTest.java
public class HashSetTest {
public static void main(String[] args) {
HashSet<String> hashSet = new HashSet<String>();
hashSet.add(new String("김유신"));
hashSet.add(new String("이순신"));
hashSet.add(new String("홍연의"));
hashSet.add(new String("강감찬"));
hashSet.add(new String("강감찬"));
System.out.println(hashSet);
}
}MemberHashSet.java
public class MemberHashSet {
private HashSet<Member> hashSet;
public MemberHashSet(){
hashSet = new HashSet<Member>();
}
public void addMember(Member member){
hashSet.add(member);
}
public boolean removeMember(int memberId){
Iterator<Member> ir = hashSet.iterator();
while( ir.hasNext()){
Member member = ir.next();
int tempId = member.getMemberId();
if( tempId == memberId){
hashSet.remove(member);
return true;
}
}
System.out.println(memberId + "가 존재하지 않습니다");
return false;
}
public void showAllMember(){
for(Member member : hashSet){
System.out.println(member);
}
System.out.println();
}
}MemberHashSetTest.java
public class MemberHashSetTest {
public static void main(String[] args) {
MemberHashSet memberHashSet = new MemberHashSet();
Member memberLee = new Member(1001, "이순신");
Member memberKim = new Member(1002, "김유신");
Member memberKang = new Member(1003, "강감찬");
memberHashSet.addMember(memberLee);
memberHashSet.addMember(memberKim);
memberHashSet.addMember(memberKang);
memberHashSet.showAllMember();
Member memberHong = new Member(1003, "홍길동"); //1003 아이디 중복
memberHashSet.addMember(memberHong);
memberHashSet.showAllMember();
}
}아이디가 동일한 경우 같은 멤버이므로 중복되지 않도록, Member 클래스의 equals()와 hashCode() 메서드를 재정의한다.
Member.java
...
@Override
public int hashCode() {
return memberId;
}
@Override
public boolean equals(Object obj) {
if( obj instanceof Member){
Member member = (Member)obj;
if( this.memberId == member.memberId )
return true;
else
return false;
}
return false;
}
...13. 정렬을 위해 Comparable과 Comparator 인터페이스 구현하기
TreeSet 클래스 활용하기
- 객체의 정렬에 사용하는 클래스다.
- Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있다.
- 내부적으로 이진 검색 트리(binary search tree)로 구현된다.
- 이진 검색 트리에 저장하기 위해 각 객체를 비교해야 한다.
- 비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현해야 TreeSet에 추가될 수 있다.
- String, Integer 등 JDK의 많은 클래스들이 이미 Comparable을 구현했다.
TreeSetTest.java
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<String>();
treeSet.add("홍길동");
treeSet.add("강감찬");
treeSet.add("이순신");
for(String str : treeSet) {
System.out.println(str);
}
}
}String 클래스는 이미 Comparable 인터페이스가 구현되어 있으므로 오름차순으로 정렬되어 출력된다.
MemberTreeSet.java
public class MemberTreeSet {
private TreeSet<Member> treeSet;
public MemberTreeSet(){
treeSet = new TreeSet<Member>();
}
public void addMember(Member member){
treeSet.add(member);
}
public boolean removeMember(int memberId){
Iterator<Member> ir = treeSet.iterator();
while( ir.hasNext()){
Member member = ir.next();
int tempId = member.getMemberId();
if( tempId == memberId){
treeSet.remove(member);
return true;
}
}
System.out.println(memberId + "가 존재하지 않습니다");
return false;
}
public void showAllMember(){
for(Member member : treeSet){
System.out.println(member);
}
System.out.println();
}
}MemberTreeSetTest.java
public class MemberTreeSetTest {
public static void main(String[] args) {
MemberTreeSet memberTreeSet = new MemberTreeSet();
Member memberKim = new Member(1003, "김유신");
Member memberLee = new Member(1001, "이순신");
Member memberKang = new Member(1002, "강감찬");
memberTreeSet.addMember(memberKim);
memberTreeSet.addMember(memberLee);
memberTreeSet.addMember(memberKang);
memberTreeSet.showAllMember();
}
}Member 클래스가 아이디 오름차순으로 정렬되게 하기 위해 Comparable 인터페이스를 구현한다.
Member.java
public class Member implements Comparable<Member>{
......
@Override
public int compareTo(Member member) {
//return (this.memberId - member.memberId); //오름차순
return (this.memberId - member.memberId) * (-1); //내림 차순
}
}Comparator의 활용: 이미 Comparable이 구현된 경우, Comparator로 비교하는 방식을 다시 구현할 수 있다.
class MyCompare implements Comparator<String>{
@Override
public int compare(String s1, String s2) {
return (s1.compareTo(s2)) *-1 ;
}
}
public class ComparatorTest {
public static void main(String[] args) {
Set<String> set = new TreeSet<String>(new MyCompare());
set.add("aaa");
set.add("ccc");
set.add("bbb");
System.out.println(set);
}
}14. 쌍(pair)으로 자료를 관리하는 Map 인터페이스를 구현한 클래스와 그 활용
HashMap 클래스 활용하기
- Map 인터페이스를 구현한 클래스다.
- 가장 많이 사용되는 Map 인터페이스 기반 클래스다.
- key-value를 쌍으로 관리하는 메서드를 구현한다.
- 검색을 위한 자료구조다.
- key를 이용하여 값을 저장하고, key를 이용하여 값을 꺼내오는 방식 - hash 알고리즘으로 구현된다.
- key가 되는 객체는 중복될 수 없고, 객체의 유일성 비교를 위한
equals()와hashCode()메서드를 구현해야 한다.
// Member.java는 기존과 동일
MemberHashMap.java
public class MemberHashMap {
private HashMap<Integer, Member> hashMap;
public MemberHashMap()
{
hashMap = new HashMap<Integer, Member>();
}
public void addMember(Member member){
hashMap.put(member.getMemberId(), member);
}
public boolean removeMember(int memberId){
if(hashMap.containsKey(memberId)){
hashMap.remove(memberId);
return true;
}
System.out.println(memberId + "가 존재하지 않습니다");
return false;
}
public void showAllMember(){
Iterator<Integer> ir = hashMap.keySet().iterator();
while (ir.hasNext()){
int key = ir.next();
Member member = hashMap.get(key);
System.out.println(member);
}
System.out.println();
}
}MemberHashMapTest.java
public class MemberHashMapTest {
public static void main(String[] args) {
MemberHashMap memberHashMap = new MemberHashMap();
Member memberLee = new Member(1001, "이순신");
Member memberKim = new Member(1002, "김유신");
Member memberKang = new Member(1003, "강감찬");
Member memberHong = new Member(1004, "홍길동");
memberHashMap.addMember(memberLee);
memberHashMap.addMember(memberKim);
memberHashMap.addMember(memberKang);
memberHashMap.addMember(memberHong);
memberHashMap.showAllMember();
memberHashMap.removeMember(1004);
memberHashMap.showAllMember();
}
}TreeMap 클래스
- Map 인터페이스를 구현한 클래스이고, key에 대한 정렬을 구현할 수 있다.
- key가 되는 클래스에 Comparable이나 Comparator 인터페이스를 구현함으로써, key-value 쌍의 자료를 key값 기준으로 정렬하여 관리할 수 있다.