JAVA & Spring 강의 (자바 인강 6주차) 자바와 자료구조

배열(Array)

동일한 데이터 타입을 순서에 따라 관리하는 자료구조이다.

크기가 정해져있고, 논리적 위치와 물리적 위치가 동일하다.

그래서 Array[0]이런식으로 배열의 i번째 요소를 찾는 연산이 빠르다.

 

ex) 아래 메서드 구현

MyArray()

addElement(int num) 

insertElement(int position, int num) 

removeElement(int position)

getSize()

isEmpty()

getElement(int position)

printAll()

removeAll()

package ch02;

public class MyArray {

	int[] intArr;
	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 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;
		
		//예외 상황 처리(position이 0보다 작을 경우, count보다 position이 큰 경우)
		if(position < 0 || position > count) {
			System.out.println("오류");
			return;
		}
		
		//예외 상황 처리(메모리 초과)
		if(count >= ARRAY_SIZE) {
			System.out.println("오류");
			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("오류");
			return ret;
		}
		
		//예외 상황 처리(position이 0보다 작을 경우, count-1보다 position이 큰 경우)
		if(position < 0 || position > count-1 ) {
			System.out.println("오류");
			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;

	}
}

테스트 케이스

package ch02;

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

출력결과

---

연결 리스트 (LinkedList)

동일한 데이터 타입을 순서에 따라 관리하는 자료 구조이다.

head를 시작으로 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있다.

그러다보니, 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결하면 된다.

그래서 배열보다 i번째 요소를 찾는 시간이 오래 걸린다. 

 

ex)

package ch03;

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)
	{

		MyListNode tempNode = head;
		MyListNode preNode = null;
		
		MyListNode newNode = new MyListNode(data);
		
		if(position<0 || position>count) {
			return null;
		}
		
		if(position == 0) {
			newNode.next = head;
			head = newNode;
		}
		else {
			for(int 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)
	{
		MyListNode tempNode = head;
		MyListNode preNode = null;
		
		if(position == 0) {
			head = tempNode.next;
		}
		else {
			for(int i=0; i<position;i++) {
				preNode = tempNode;
				tempNode = tempNode.next;
			}
			preNode.next = tempNode.next;
		}
		count--;
		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;
	}

}

package ch03;

public class MyListNode {

	private String data;
	public MyListNode next;
	
	//입력값 없을 경우
	public MyListNode() {
		data = null;
		next = null;
	}
	
	//data입력값만 있을 경우
	public MyListNode(String data) {
		this.data = data;
		this.next = null;
	}
	
	//data, next 입력값
	public MyListNode(String data, MyListNode link) {
		this.data = data;
		this.next = link;
	}
	
	//getData 데이터 호출
	public String getData() {
		return data;
	}
}

package ch03;

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

}

출력값

---

스택(Stack)

후입선출 Last In First Out 구조이다.

책이 쌓여있다고 생각하면 된다. 맨 위에서만(맨 마지막) 자료의 추가, 삭제, 꺼내볼 수 있다.

ex)

package ch04;

import ch02.MyArray;

public class MyArrayStack {

	MyArray arrayStack;
	int top;
	
	//아무것도 없는 경우
	public MyArrayStack() {
		top = 0; 
		arrayStack = new MyArray();
	}
	
	//size값이 들어오는 경우
	public MyArrayStack(int size) {
		top = 0;
		arrayStack = new MyArray(size);
	}
	
	//값을 넣는다 add
	public void push(int data) {
		if(isFull()) {
			System.out.println("stact is full");
			return;
		}

		arrayStack.addElement(data);
		top++;
	}
	
	//값을 꺼낸다 remove
	public int pop() {
		if(isEmpty()) {
			System.out.println("stact is empty");
			return MyArray.ERROR_NUM;
		}
		
		return arrayStack.removeElement(--top);
	}
	
	//값을 본다 get
	public int peek() {
		if(isEmpty()) {
			System.out.println("stact is empty");
			return MyArray.ERROR_NUM;
		}
		
		return arrayStack.getElement(--top);
	}
	
	public boolean isFull() {
		if(top == arrayStack.ARRAY_SIZE) {
			return true;
		}
		else {
			return false;
		}
	}
	
	public boolean isEmpty() {
		if(top == 0) {
			System.out.println("stack is empty");
			return true;
		}
		else {
			return false;
		}
	}
	
	public void printAll() {
		arrayStack.printAll();
	}
	
}

package ch04;

public class MyArrayStackTest {
	public static void main(String[] args) {
		
		MyArrayStack stack = new MyArrayStack();
		stack.push(10);
		stack.push(20);
		stack.push(30);
		stack.push(40);
		
		stack.printAll();
		
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.peek());
		
	}
}

출력결과

---

큐(Queue)

Front(맨 앞)에서 자료를 꺼내거나 삭제하고,

Rear(맨 뒤)에서 자료를 추가한다.

선입선출 First In First Out 형태.

콜센터에 들어온 문의 전화, 메세지 등에 활용!

 

ex)

package ch05;

import ch03.MyLinkedList;
import ch03.MyListNode;

interface Queue{
	public void enQueue(String data); //입력
	public String deQueue(); //출력
	public void printQueue();
}

public class MyLinkedQueue extends MyLinkedList implements Queue{

	MyListNode front;
	MyListNode rear;
	
	//데이터 넣기
	@Override
	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");
	}

	//데이터 출력 후 삭제
	@Override
	public String deQueue() {
		if(isEmpty()) {
			return null;
		}
		String data = front.getData();
		front = front.next;
		
		if(front == null) {
			rear = null;
		}
		return data;
	}

	//데이터 출력
	@Override
	public void printQueue() {
		printAll();
	}

}

package ch05;

public class MyListQueueTest {
	public static void main(String[] args) {
		
		MyLinkedQueue listQueue = new MyLinkedQueue();
		listQueue.enQueue("A");
		listQueue.enQueue("B");
		listQueue.enQueue("C");
		
		listQueue.printAll();
		
		System.out.println(listQueue.deQueue());
		System.out.println(listQueue.deQueue());
	}
}

출력결과

---

제네릭(Generic)

제네릭 자료형 

클래스에서 사용하는 변수의 자료형이 여러개이면서, 그 기능(메서드)는 동일한 경우가 있다.

ex)

public class ThreeDPrinter2 {

	private Powder material;
	
	public Powder getMaterial() {
		return material;
	}

	public void setMaterial(Powder material) {
		this.material = material;
	}

	public String toString() {
		return "재료는  Powder 입니다.";
	}

public class ThreeDPrinter1 {

	private Plastic material;
	
	public Plastic getMaterial() {
		return material;
	}

	public void setMaterial(Plastic material) {
		this.material = material;
	}

	public String toString() {
		return "재료는  Plastic 입니다.";
	}
}

위의 두 클래스는 Powder, Plastic로 클래스가 다르지만 메서드 형식은 같다.

이런 경우 제너릭 자료형을 이용해

클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정 할 수 있도록 선언할 수 있다.

 

package ch06;

public class GenericPrinter<T> {

	private T material;

	public T getMaterial() {
		return material;
	}

	public void setMaterial(T material) {
		this.material = material;
	}
	
	public String toString() {
		return material.toString();
	}
}

Generic type T로 지정하였다. Test 출력을 해보면...

package ch06;

public class GenericPrinterTest {
	public static void main(String[] args) {
		
		Powder powder = new Powder();
		
		//<T>자리에 실제적으로 어떤 타입을 쓸건지 지정해준다.
		GenericPrinter<Powder> powderPrinter = new GenericPrinter<>();
		powderPrinter.setMaterial(powder);
		
		Powder p = powderPrinter.getMaterial(); //형변환 필요없음
		System.out.println(powderPrinter.toString());
	}
}

Object 등을 사용하여 처리하면 형변환을 해주어야하는 번거로움이 있다.

Generic 같은 경우는 형변환이 필요없다.

<T extends 클래스>

위의 예시처럼 Generic<T>를 활용하면, T에는 어떤 자료형이든 들어갈 수 있다.

위와같은 Printer예제에서 클래스로 water을 지정할수는 없지 않는가. 범위를 제한할 필요가 있다.

그래서 상속을 활용하여 T 자료형의 범위를 제한한다.

 

public abstract class Material {
	
	public abstract void doPrinting();
}

위와같이 Material class를 abstract 형태로 선언하여,

위의 재료들(Powder, Plastic)들이 extends 한다.

그렇게 되면 아까와 같이 형변환 없이 Generic만 제한된 상태로 사용가능하다.

---

제네릭 메서드 

<T>, <V>, <E>와 같이 자료형 매개변수가 하나 이상인 경우도 있다!

그리고 꼭 제네릭 클래스가 아니더라도 내부에 제네릭 메서드를 구현하여 사용할 수 있다.

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;
    }
}

제네릭 타입 <T, V>

package ch07;

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<Integer, Double>(10, 10.0);
		
		double size = GenericMethod.<Integer, Double>makeRectangle(p1, p2);
		System.out.println(size);
	}
}

---

컬렉션 프레임워크

프로그램 구현에 필요한 자료구조(Data Structure)를 구현해 놓은 JDK 라이브러리이다.

• Collection (하나의 객체를 관리하기 위한 메서드) (Student, Major 등)
  • List (객체를 순서에 따라 저장하고 관리) (중복 허용) (자료구조 리스트, 배열, 연결리스트 등)
    • ArrayList 
    • Vector
    • LinkedList
  • Set (객체를 순서와 관계없이 저장하고 관리)(중복 X, 유일한 값 관리) (아이디, 주민번호, 사번 등)
    • HashSet
    • TreeSet
• Map (쌍(pair)로 이루어진 객체를 관리하는데 사용하는 메서드)
  • HashTable
    • Properties
  • HashMap
  • TreeMap

---

ArrayList 활용예제

멤버를 순차적으로 관리하는 예제

package ch10;

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 + "입니다";
	}
}

Member 선언

package ch10;

import java.util.ArrayList;

public class MemberArrayList {

	private ArrayList<Member> arrayList;
	
	public MemberArrayList() {
		arrayList = new ArrayList<>();
	}
	
	public MemberArrayList(int size) {
		arrayList = new ArrayList<>(size);
	}
	
	public void addMember(Member member) {
		arrayList.add(member);
	}
	
	public boolean removeMember(int memberId) {
		for(int i=0;i<arrayList.size();i++) {
			Member member = arrayList.get(i);
			
			int tempId = member.getMemberId();
			if(tempId == memberId) {
				arrayList.remove(i);
				return true;
			}
		}
		System.out.println(memberId + "가 존재하지 않습니다.");
		return false;
	}
	
	public void showAllMember() {
		for( Member member : arrayList) {
			System.out.println(member);
		}
		System.out.println();
	}
}

MemberArrayList 선언하여, 추가 삭제 구현

package ch10;

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(memberKim.getMemberId());
		memberArrayList.showAllMember();

	}
}

List 순서대로 입출력 되는 것을 알 수 있음

---

Iterator

Collection 요소를 순회하는 것, 컬렉션 프레임워크에 저장된 요소들을 하나씩 차례로 참조하는것이다.

Set 인터페이스의 경우 List와 다르게 get(i) 메서드가 제공되지 않으므로, Iterator를 활용하여 객체를 순회한다.

Iterator<Member> ir = arrayList.iterator();
		
		while(ir.hasNext()) {
			
			Member member =  ir.next();
			
			int tempId = member.getMemberId();
			if( tempId == memberId ) {
				arrayList.remove(member);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다.");
		return false;

Iterator<Member>을 선언하고,

.hasNext() => True, False 반환

.next() => 다음에 있는 요소를 반환

---

HashSet 클래스

Set은 중복이 허용되지 않기 때문에,

멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 한다.

필요에 따라 equals와 hashcode 메서드를 재정의하여 중복체크를 해야한다.

 

	@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;
	}

hashCode와 equals를 재정의하여 유효성 검사

위의 MemberArrayList에서 arrayList를 hashCode로 변경하기만 하면 된다.

package ch12;

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);
		
		Member memberHong = new Member(1003, "홍길동");
		memberHashSet.addMember(memberHong);
		
		
		memberHashSet.showAllMember();
	}
}

---

TreeSet 클래스

중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬

내부적으로 이진검색트리(binary search tree)로 구현됨. 자신과 비교하여 왼쪽은 small 오른쪽은 big 한 형태

 

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 인터페이스가 구현되어 있어 오름차순으로 정렬되어 출력된다.

@Override
	public int compareTo(Member member) {
		
		//return (this.memberId - member.memberId);   //오름차순
		return (this.memberId - member.memberId) *  (-1);   //내림 차순
	}

Member클래스가 아이디 오름차순으로 정렬되게 하기 위해 Comparable 인터페이스를 구현한다.

---

HashMap 클래스

쌍(pair)으로 자료를 관리한다.

key-value로 이루어져있고, 검색을 위한 자료구조이다.

key가 되는 객체는 중복될 수 없고 객체의 유일성을 비교를 위한 equals()와 hashCode() 메서드를 구현해야 한다.

 

package ch14;

import java.util.HashMap;
import java.util.Iterator;

public class MemberHashMap {

	private HashMap<Integer, Member> hashMap;
	
	public MemberHashMap() {
		hashMap = new HashMap<>();
	}
	
	public void addMember(Member member) {
		hashMap.put(member.getMemberId(), member);
	}
	
	public boolean removeMember(int memberId) {
		if(hashMap.containsKey(memberId)) {
			hashMap.remove(memberId);
		}
		System.out.println("no element");
		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);
		}
	}
	
}

package ch14;

import java.util.HashMap;

public class MemberHashMapTest {
	public static void main(String[] args) {
		

		MemberHashMap memberHashMap = new MemberHashMap();
		
		Member memberHong = new Member(1004, "홍순신");
		Member memberLee = new Member(1001, "이순신");
		Member memberKim = new Member(1002, "김유신");
		Member memberKang = new Member(1003, "강감찬");
		
		
		memberHashMap.addMember(memberLee);
		memberHashMap.addMember(memberKim);
		memberHashMap.addMember(memberKang);
		memberHashMap.addMember(memberHong);
		
		
		memberHashMap.showAllMember();
		
		HashMap<Integer, String> hashMap = new HashMap<Integer, String>();
		hashMap.put(1001, "Kim");
		hashMap.put(1002, "Lee");
		hashMap.put(1003, "Park");
		hashMap.put(1004, "Hong");
		
		System.out.println(hashMap);
		/*
		
		TreeSet<String> set = new TreeSet<String>();
		set.add("홍길동");
		set.add("강감찬");
		set.add("이순신");
		
		System.out.println(set);
		
		*/
	}
}