240115 Java

LinkedList 클래스

배열의 번거로움을 개선한 자료 구조이다.

링크드 리스트의 각요소는 다음 요소를 가리키는 주소 값을 가진다.

따라서 메모리는 떨어져 있어도 논리적으로는 앞뒤 순서가 있다.

같은 List 인터페이스를 구현한 ArrayList에 비해 중간에 자료를 넣고 제거하는 데 시간이 젝거 걸리며,

크기를 동적으로 증가시킬 수 있다.

package collection;

import java.util.LinkedList;

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

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

//링크드 리스트에 요소 추가
myList.add("A");
myList.add("B");
myList.add("C");
System.out.println(myList); //리스트 전체 출력

myList.add(1, "D"); //링크드 리스트의 첫 번째 위치에 추가
System.out.println(myList); //리스트 전체 출력

myList.addFirst("0"); //연결 리스트의 맨 앞에 추가
System.out.println(myList); //리스트 전체 출력

System.out.println(myList.removeLast()); //연결 리시트의 맨 뒤 요소 삭제 후 해당 요소를 출력
System.out.println(myList); //리스트 전체 출력

	}
}

 

[A, B, C]

[A, D, B, C]

[0, A, D, B, C]

C

[0, A, D, B]

 

addFirst(), removeFirst() : 맨 앞 요소를 추가, 삭제하는 메소드

addLast(), removeLast() : 맨 뒤 요소를 추가, 삭제하는 메소드

 

스택과 큐

스택은 상자를 쌓듯이 자료를 관리하는 방식, 맨 나중에 올린 상자를 먼저 꺼내는(Last In First Out : LIFO) 방식

package collection.arraylist;

import java.util.ArrayList;

class MyStack{

private ArrayList<String> arrayStack = new ArrayList<String>();
//스택의 맨 뒤에 요소를 추가
public void push(String data) {
arrayStack.add(data);
}

//스택의 맨 뒤에서 요소를 꺼냄
public String pop() {
int len = arrayStack.size(); //ArrayList에 저장된 유효한 자료의 개수
if(len==0) {
System.out.println("스택이 비었음");
return null;
	}
return(arrayStack.remove(len-1)); //맨 뒤에 있는 자료 반환하고 배열에서 제거
	}
}
public class StackTest {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
	}
}

 

C

B

A

 

스택 메모리 구조는 스택 자료 구조 형식이다.

 

큐는 줄을 선 대기열 처럼 먼저 추가된 데이터부터 꺼내서 사용하는 방식(First In Fist Out : FIFO)

package collection.arraylist;

import java.util.ArrayList;

class MyQueue{
private ArrayList<String> arrayQueue = new ArrayList<String>();
//큐의 맨뒤에 추가
public void enQueue(String date) {
arrayQueue.add(date);
}

//큐의 맨 앞에서 꺼냄
public String deQueue() {
int len = arrayQueue.size();
if(len==0) {
System.out.println("큐가 비었음");
return null;
}
return (arrayQueue.remove(0)); //맨 앞의 자료 반환하고 배열에서 제거
}
}

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

MyQueue queue = new MyQueue();
queue.enQueue("A");
queue.enQueue("B");
queue.enQueue("C");

System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());

	}
}

 

A

B

C

 

Collection 요소를 순회하는 Iterator

순서가 없는 Set 인터페이스를 구현한 경우에는 get(i) 메소드를 사용할 수 없다. 이 때 Iterator를 사용한다.

• boolean hasNext()
  이후에 요소가 더 있는지 체크하는 메소드이며, 요소가 있다면 true를 반환
• E next()
  다음에 있는 요소를 반환

MemberArrayList 클래스의 removeMember() 메소드 수정

package collection.arraylist;

import java.util.ArrayList;
import java.util.Iterator;
import collection.Member; //Member 클래스는 collection 패키지에 있으므로 import해줘야함

public class MemberArrayList {
private ArrayList<Member> arrayList; //ArrayList 선언
public MemberArrayList() {
arrayList = new ArrayList<Member>(); //Member형으로 선언한 ArrayList 생성
}
//ArrayList에 회원을 추가하는 메소드
public void addMember(Member member) {
arrayList.add(member);
}

// //해당 아이디를 가진 회원을 ArrayList에서 찾아 제거
// public boolean removeMember(int memberId) {
// for(int i = 0 ; i < arrayList.size(); i++) {
// Member member = arrayList.get(i); //get()메소드로 회원을 순차적으로 가져옴
// int tempId = member.getMemberId() ;
// if(tempId==memberId) { //회원 아이디가 매개변수와 일치하면
// arrayList.remove(i); //해당 회원을 삭제
// return true;
// }
// }
// //반복문이 끝날 때까지 해당 아이디를 찾지 못한 경우
// System.out.println(memberId + "가 존재하지 않음");
// return false;
// }

public boolean removeMember(int memberId) {
Iterator<Member> ir = arrayList.iterator(); //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;
}

//전체 회원을 출력하는 메소드
public void showAllMember() {
for(Member member : arrayList) {
System.out.println(member);
}
System.out.println();
}
}

 

A

B

C

 

arrayList.iterator() 메소드를 호출하여 Iterator를 가져온다. Iterator<Member>와 같이 제네릭 자료형으로 Iterator가 순회할 요소의 자료형을 지정한다. Iterator는 각 요소를 순회하기 때문에 hashNext()의 결과가 true이면 다음 요소를 가져오는 next() 메소드를 호출한다. 나머지 비교 부분은 for문과 get(i) 메소드를 사용하는 경우와 같다. 순서가 없는 클래스도 Iterator를 사용하면 요소를 순회할 수 있다.

 

Set 인터페이스

순서와 상관없이 중복을 허용하지 않는 경우에는 Set인터페이스를 구현한 클래스를 사용한다.

 

HashSet 클래스

집합 자료 구조를 구현하며 중복을 허용하지 않는다.

package collection.hashset;

 

import java.util.HashSet;

 

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("HTML"));

hashSet.add(new String("CSS"));

hashSet.add(new String("JSP"));

hashSet.add(new String("DB"));

 

System.out.println(hashSet);

 

}

 

}

[CSS, JSP, HTML, 자바, DB]

 

hashSet에 동일한 자료 '자바'를 추가했다. 결과는 같은 자료는 중복되어 출력되지 않음을 확인할 수 있다.

출력 결과를 통해 알 수 있는 것은 첫째, HashSet에 주복된 값은 추가되지 않는다. 둘째 HashSet는 자료가 추가된 순서와 상관없이 출력된다.

package collection.hashset;

 

import java.util.HashSet;

import java.util.Iterator;

 

import collection.Member;

 

public class MemberHashSet {

 

private HashSet<Member> hashSet; //HashSet 선언

 

public MemberHashSet() {

hashSet = new HashSet<Member>(); //HashSet 생성

}

 

//HashSet에 회원 추가

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

}

}

 

• boolean remove(Object o)
  매개변수로 받은 객체를 삭제하고 삭제 여부를 true, false로 반환

HashSet에서는 해당하는 아이디를 가진 회원을 찾기 위해 Iterator를 사용한다.

package collection.hashset;

 

import collection.Member;

 

public class MemberHashSetTest {

 

public static void main(String[] args) {

MemberHashSet memberHashSet = new MemberHashSet();

 

Member m1 = new Member(101, "HTML");

Member m2 = new Member(102, "CSS");

Member m3 = new Member(103, "자바");

 

memberHashSet.addMember(m1);

memberHashSet.addMember(m2);

memberHashSet.addMember(m3);

memberHashSet.showAllMember();

 

Member m4 = new Member(103, "자바스크립트");

memberHashSet.addMember(m4);

memberHashSet.showAllMember();

 

}

 

}

HTML 회원님의 아이디는 101입니다.

자바 회원님의 아이디는 103입니다.

CSS 회원님의 아이디는 102입니다.

 

HTML 회원님의 아이디는 101입니다.

자바스크립트 회원님의 아이디는 103입니다.

자바 회원님의 아이디는 103입니다.

CSS 회원님의 아이디는 102입니다.

 

같은 아이디 103, 자바와 자바스크립트가 그대로 출력되었다.

 

기본적으로 인스턴스 주소가 같으면 같은 객체이다. 하지만 아이기가 같아도 같은 회원이다.

package collection;

 

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

return memberName + " 회원님의 아이디는 " + memberId +"입니다.";

}

 

@Override

public int hashCode() {

return memberId; //hashCode()메소드가 회원 아이디를 반환하도록 재정의

}

 

@Override

public boolean equals(Object obj) {

if(obj instanceof Member) {

Member member = (Member)obj;

//매개변수로 받은 회원 아이디가 자신의 회원아이디와 같다면 true를 반환

if(this.memberId == member.memberId) {

return true;

}else {

return false;

}

}

return false;

}

}

 

Member 클래스에 equals()와 hashCode() 메소드를 제정의하고 MemberHashSetTest를 출력해보면

HTML 회원님의 아이디는 101입니다.

CSS 회원님의 아이디는 102입니다.

자바 회원님의 아이디는 103입니다.

 

HTML 회원님의 아이디는 101입니다.

CSS 회원님의 아이디는 102입니다.

자바 회원님의 아이디는 103입니다.

 

아이디가 같은 회원은 추가 되지 않는다.

 

TreeSet 클래스

자바의 Collection 인터페이스나 Map 인터페이스를 구현한 클래스 중 Tree로 시작하는 클래스는 데이터를 추가한 후

결과를 출력하면 결과 값이 정렬된다.

TreeSet는 자료의 중복을 허용하지 않으면서 출력 결과 값을 정렬하는 클래스이다.

package collection.treeset;

 

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

}

 

}

 

}

데이터베이스

자바

자바스크립트

 

TreeSet에 자바, 자바스크립트, 데이터베이스 순으로 요소를 추가했지만, 결과 값은 데이터베이스, 자바, 자바스크립트로 출력되었다. 이 정렬은 '이진 트리(binary tree)'로 정렬되었다.

 

트리는 자료 사이의 계층 구조를 나타내는 자료 구조이다.

이진 검색 트리(Binary Search Tree)

부모노드(parent node) - 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)

트리 자료 구조에서 각 자료가 들어가는 공간을 노드라고 한다. 위 아래로 연결된 노드의 관계를 부모-자식 노드 라고 한다.

이진 검색 트리는 노드에 저장되는 자료의 중복을 허용하지 않고, 부모가 가지는 자식 노드의 수가 2개 이하이다.

왼쪽 자식 노드는 부모 노드보다 항상 작은 값을 가진다. 오른쪽 자식 노드는 부모 노드보다 항상 큰 값을 가진다.

ex) 23, 10 ,48, 15 , 7, 22, 56 → 7 10 15 22 23 48 56

 

package collection.treeset;

 

import java.util.Iterator;

import java.util.TreeSet;

 

import collection.Member;

 

public class MemberTreeSet {

private TreeSet<Member> treeSet;

 

public MemberTreeSet() {

treeSet = new TreeSet<Member>();

}

 

//TreeSet에 회원을 추가하는 메소드

public void addMember(Member member) {

treeSet.add(member);

}

 

//TreeSet에서 회원을 삭제하는 메소드

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

}

 

}

 

package collection.treeset;

 

import collection.Member;

 

public class MemberTreeSetTest {

 

public static void main(String[] args) {

MemberTreeSet memberTreeSet = new MemberTreeSet();

 

Member m1 = new Member(101, "HTML");

Member m2 = new Member(102, "CSS");

Member m3 = new Member(103, "JS");

 

memberTreeSet.addMember(m1);

memberTreeSet.addMember(m2);

memberTreeSet.addMember(m3);

memberTreeSet.showAllMember();

 

Member m4 = new Member(103, "Java");

memberTreeSet.addMember(m4);

memberTreeSet.showAllMember();

}

 

}

Exception in thread "main" java.lang.ClassCastException: class collection.Member cannot be cast to class java.lang.Comparable (collection.Member is in module collection_framework of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

at java.base/java.util.TreeMap.compare(TreeMap.java:1569)

at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:776)

at java.base/java.util.TreeMap.put(TreeMap.java:785)

at java.base/java.util.TreeMap.put(TreeMap.java:534)

at java.base/java.util.TreeSet.add(TreeSet.java:255)

at collection_framework/collection.treeset.MemberTreeSet.addMember(MemberTreeSet.java:17)

at collection_framework/collection.treeset.MemberTreeSetTest.main(MemberTreeSetTest.java:14)

 

Member 클래스가 Comparable 인터페이스를 구현하지 않았다는 의미의 오류가 발생.

Comparable 인터페이스를 구현하지 않았다는 의미는 Member 클래스를 TreeSet의 요소로 추가할 때 어떤 기준으로

노드를 비교하여 트리를 형성해야 하는지를 구현하지 않았다는 뜻이다.

따라서 회원을 TreeSet에 추가할 때 어떤 기준으로 비교할 것인지를 구현해 주어야 한다.

이때 사용하는 인터페이스가 Comparable 또는 Comparator이다.

 

Comparable, Comparator 인터페이스

정렬을 구현할 수 있게 해주는 인터페이스이다.

정렬 방식을 정렬 기준 값이 있는 클래스에 구현해야한다.

Comparable 인터페이스는 compareTo() 추상 메소드가 포함되어 있기 때문에 compareTo()메소드를 구현해야한다.

package collection;

 

public class Member implements Comparable<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() {

return memberName + " 회원님의 아이디는 " + memberId +"입니다.";

}

 

@Override

public int hashCode() {

return memberId; //hashCode()메소드가 회원 아이디를 반환하도록 재정의

}

 

@Override

public boolean equals(Object obj) {

if(obj instanceof Member) {

Member member = (Member)obj;

//매개변수로 받은 회원 아이디가 자신의 회원아이디와 같다면 true를 반환

if(this.memberId == member.memberId) {

return true;

}else {

return false;

}

}

return false;

}

 

//compareTo() 메소드 재정의. 추가한 회원 아이디와 매개변수로 받은 회원 아이디를 비교함.

@Override

public int compareTo(Member member) {

return (this.memberId - member.memberId);

}

}

 

새로 추가한 회원 아이디와 compareTo() 메소드의 매개변수로 전달된 회원 아이디다. 두 값을 비교하여 새로 추가한 회원 아이디가 더 크면 양수, 그렇지 않으면 음수, 같으면 0을 반환하도록 함. 이렇게 구현하면 출력 결과 값은 오름차순으로 정렬된다.

 

Member 클래스에 Comparable 인터페이스를 구현한 후 compareTo() 메소드를 재정의하면

HTML 회원님의 아이디는 101입니다.

CSS 회원님의 아이디는 102입니다.

JS 회원님의 아이디는 103입니다.

 

HTML 회원님의 아이디는 101입니다.

CSS 회원님의 아이디는 102입니다.

JS 회원님의 아이디는 103입니다.

 

결과가 출력된다.

아이디 오름차순으로 정렬됨.

만약 내림차순으로 정렬하려고 한다면

package collection;

 

public class Member implements Comparable<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() {

return memberName + " 회원님의 아이디는 " + memberId +"입니다.";

}

 

@Override

public int hashCode() {

return memberId; //hashCode()메소드가 회원 아이디를 반환하도록 재정의

}

 

@Override

public boolean equals(Object obj) {

if(obj instanceof Member) {

Member member = (Member)obj;

//매개변수로 받은 회원 아이디가 자신의 회원아이디와 같다면 true를 반환

if(this.memberId == member.memberId) {

return true;

}else {

return false;

}

}

return false;

}

 

//compareTo() 메소드 재정의. 추가한 회원 아이디와 매개변수로 받은 회원 아이디를 비교함.

@Override

public int compareTo(Member member) {

return ((this.memberId - member.memberId)*(-1));

}

}

 

JS 회원님의 아이디는 103입니다.

CSS 회원님의 아이디는 102입니다.

HTML 회원님의 아이디는 101입니다.

 

JS 회원님의 아이디는 103입니다.

CSS 회원님의 아이디는 102입니다.

HTML 회원님의 아이디는 101입니다.

 

내림차순으로 변경된다.

 

Comparator 인터페이스도 정렬을 구현하는 데 사용하는 인터페이스이다.

Comparator 인터페이스는 compare() 메소드를 구현해야한다.

package collection;

 

import java.util.Comparator;

 

public class Member2 implements Comparator<Member2>{

 

private int memberId; //회원 아이디

private String memberName; //회원 이름

 

public Member2(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() {

return memberName + " 회원님의 아이디는 " + memberId +"입니다.";

}

 

@Override

public int hashCode() {

return memberId; //hashCode()메소드가 회원 아이디를 반환하도록 재정의

}

 

@Override

public boolean equals(Object obj) {

if(obj instanceof Member2) {

Member2 member = (Member2)obj;

//매개변수로 받은 회원 아이디가 자신의 회원아이디와 같다면 true를 반환

if(this.memberId == member.memberId) {

return true;

}else {

return false;

}

}

return false;

}

 

@Override

public int compare(Member2 m1, Member2 m2) {

return m1.getMemberId() - m2.getMemberId();

}

 

 

}

 

compare() 메소드는 전달되는 두 매개변수를 비교하며, 첫 번째 매개변수가 더 클 때 양수를 반환하여 오름차순으로 정렬된다.

 

Comparator를 사용할 때 유의할 점은 TreeSet 생성자에 Comparator를 구현한 객체를 매개 변수로 전달한다는 것이다.

TreeSet<Member> treeSet = new TreeSet<Member>(new Member());