Don't Panic
in java

[자바] java 자료구조

#Java

20210321

01. 여러가지 자료구조에 대해 알아봅시다.

자료구조란 무엇인가? (Data Structure)

  • 프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들

  • 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨

  • 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음

  • 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함

자료구조에는 어떤 것들이 있나?

  • 한 줄로 자료를 관리하기 (선형 자료구조)

배열 (Array) : 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음

array

연결 리스트 (LinkedList) : 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음

리스트에 자료 추가하기
listadd

리스트에서 자료 삭제하기

listdelete

스택 (Stack) : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First OUt)

stack

큐 (Queue) : 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out)

queue

  • 트리 (Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조

힙(heap) : Priority queue를 구현 (우선 큐) -> 우선순위 큐는 우선순위가 높은 순으로 꺼내므로 힙을 이용해서 구현한다. (최대힙이 부모노드가 자식노드보다 항상 크기떄문 반대인 최소힙으로도 가능.)

Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우

Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우

heap정렬에 활용 할 수 있음

이진 트리 (binary tree) : 부모노드에 자식노드가 두 개 이하인 트리

binary1

이진 검색 트리 (binary search tree)

binary3

자료(key)의 중복을 허용하지 않음

왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐

자료를 검색에 걸리는 시간이 평균 log(n) 임

inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨

예) [23, 10, 28, 15, 7, 22, 56] 순으로 자료를 넣을때 BST

나중에 tresset이나 treemap 할떄 compaable인터페이스 구현해서 비교하게끔 구현할 거. binary2

jdk 클래스 : TreeSet, TreeMap (Tree로 시작되는 클래스는 정렬을 지원 함)

  • 그래프 (Graph) : 정점과 간선들의 유한 집합 G = (V,E)

-> 네비게이션, 구글맵 이런게 다 그래프에 기반해서 구현.

정점(vertex) : 여러 특성을 가지는 객체, 노드(node)

간선(edge) : 이 객체들을 연결 관계를 나타냄. 링크(link)

간선은 방향성이 있는 경우와 없는 경우가 있음(노드와 노드 연결하는걸 edge나 link라고 한다.)

그래프를 구현하는 방법 : 인접 행렬(adjacency matrix), 인접 리스트(adjacency list)

그래프를 탐색하는 방법 : BFS(bread first search), DFS(depth first search)

그래프의 예)

graph

  • 해싱 (Hashing) : 자료를 검색하기 위한 자료 구조

    검색을 위한 자료 구조

    키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조

    key는 유일하고 이에 대한 value를 쌍으로 저장

    index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨

    해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1)

    저장되는 메모리 구조를 해시테이블이라 함

    jdk 클래스 : HashMap, Properties

키는 중복 되지 않음. 나머지를 구하는게 해시함수(123%100해서 23번쨰 자리에 저장) 해시테이블

hash

체이닝

hash2

해시는 키에대한 밸류가 있다.

키는 유해서 키는 중복될 수 없다. 키만 알면 밸류를 꺼낼 수 없다. 해시는 들어가는 순서와 상관이 없다. 배열과 비슷하게 생겨서 많이 오해. 해시펑션에 의해 정해져서 순서랑은 무관하다.

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)에서 자료를 추가 함

  • Fist 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 : 제네릭 자료형

  • 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);

	}

}

다이아몬드 연산자 <>

  • 에서 <>를 다이아몬드 연산자라 함

  • ArrayList list = new ArrayList<>(); //다이아몬든 연산자 내부에서 자료형은 생략가능 함

  • 제네릭에서 자료형 추론(자바 10부터)

    ArrayList list = new ArrayList() => var list = new ArrayList();

07. <T extends 클래스> 사용하기

상위 클래스의 필요성

  • T 자료형의 범위를 제한 할 수 있음

  • 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음

  • 상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 기본으로 제공하는 메서드만 사용가능

T extends 를 사용한 프로그래밍

  • GenericPrinter 에 material 변수의 자료형을 상속받아 구현

  • T에 무작위 클래스가 들어갈 수 없게 Material 클래스를 상속받은 클래스로 한정

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

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 클래스는 이미 Comprable 인터페이스가 구현되어 있으므로 오름차순으로 정렬되어 출력됨

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값 기준으로 정렬하여 관리 할 수 있음