[자바] java 자료구조
20210321
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
나중에 tresset이나 treemap 할떄 compaable인터페이스 구현해서 비교하게끔 구현할 거. 
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)
그래프의 예)
해싱 (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)에서 자료를 추가 함
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
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 자료형의 범위를 제한 할 수 있음
상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음
상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 기본으로 제공하는 메서드만 사용가능
T extends 를 사용한 프로그래밍
GenericPrinter
에 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 클래스는 이미 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값 기준으로 정렬하여 관리 할 수 있음
42
