반응형
자료구조
프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법으로 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
1. 배열
선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용. 자료의 물리적 위치와 논리적 위치가 같음
package ch02;
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;
}
}
2. 연결 리스트
선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결. 자료의 물리적 위치와 논리적 위치가 다를 수 있음
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 )
{
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;
}
}
3. 스택
가장 나중에 입력 된 자료가 가장 먼저 출력 (Last In First OUt)
package ch04;
import ch02.MyArray;
public class MyArrayStack {
MyArray arrayStack;
int top;
public MyArrayStack() {
top = 0;
arrayStack = new MyArray();
}
public MyArrayStack(int size) {
top = 0;
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(isEmpty()) {
System.out.println("stack is empty");
return MyArray.ERROR_NUM;
}
return arrayStack.removeElement(--top);
}
public int peek() {
if(isEmpty()) {
System.out.println("stack 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) {
return true;
}
else return false;
}
public void printAll() {
arrayStack.printAll();
}
}
4. 큐
가장 먼저 입력 된 자료가 가장 먼저 출력 (First In First Out)
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();
}
}
5. 트리
부모 노드와 자식 노드간의 연결로 이루어진 자료 구조
6. 그래프
여러 특성을 가지는 객체, 노드(node)를 연결, 링크(link). 방향성이 있는 경우와 없는 경우가 있음
그래프를 구현하는 방법 : 인접 행렬(adjacency matrix), 인접 리스트(adjacency list)
그래프를 탐색하는 방법 : BFS(bread first search), DFS(depth first search)
7. 해싱
키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조
해시 함수가 key에 대한 인덱스를 반환. 해당 인덱스 위치에 자료를 저장하거나 검색
해시테이블 : 저장되는 메모리 구조
8. 제네릭 프로그래밍
클래스에서 사용하는 변수의 자료형이 여러개 일 수 있고, 그 기능(메서드)은 동일한 경우 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정 할 수 있도록 선언
실제 사용되는 자료형의 변환은 컴파일러에 의해 검증되므로 안정적인 프로그래밍 방식
컬렉션 프레임워크에서 많이 사용
* 다이아몬드 연산자<>
package ch06;
public class GernericPrinter<T> {
private T material;
public T getMaterial() {
return material;
}
public void setMaterial(T material) {
this.material = material;
}
public String toString() {
return material.toString();
}
}package ch06;
public class GenericPrinterTest {
public static void main(String[] args) {
Powder powder=new Powder();
GernericPrinter<Powder> powderPrinter=new GernericPrinter<>();
powderPrinter.setMaterial(powder);
Powder p=powderPrinter.getMaterial();
System.out.println(powderPrinter.toString());
}
}9. 제네릭 메서드 활용
자료형 매개변수를 메서드의 매개변수나 반환 값으로 가지는 메서드는 자료형 매개 변수가 하나 이상인 경우도 있음
- 두 점을 기준으로 사각형을 만들 때 사각형의 너비를 구하는 메서드
package ch07;
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 getV() {
return y;
}
}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.getV()).doubleValue();
double bottom=((Number)p2.getV()).doubleValue();
double width=right-left;
double height=bottom-top;
return width*height;
}
public static void main(String[] args) {
Point<Integer, Double> p1 = new Point<>(0,0.0);
Point<Integer, Double> p2 = new Point<>(10,10.0);
double size=GenericMethod.<Integer,Double>makeRectangle(p1, p2);
System.out.println(size);
}
}10. 컬렉션 프레임워크
프로그램 구현에 필요한 자료구조를 구현해놓은 JDK라이브러리로 java.util 패키지에 구현되어 있음
개발에 소요되는 시간 절약, 최적화된 알고리즘 사용
- Collection 인터페이스 : 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스 하위에 List와 Set
- List 인터페이스 : 객체를 순서에 따라 저장하고 관리하는데 필요한 메서드가 선언(ArrayList, Vector, LinkedList, Stack, Queue)
- Set 인터페이스 : 순서와 관계없이 중복을 허용하지 않고 유일한 값을 관리하는데 필요한 메서드가 선언(HashSet, TreeSet)
- Map 인터페이스 : 쌍(pair)로 이루어진 객체를 관리하는데 사용하는 메서드들이 선언(HashTable, HashMap, Properties, TreeMap)
11. HashSet 클래스
중복되지 않게 자료를 관리
12. TreeSet 클래스
객체의 정렬에 사용하는 클래스
Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있음
비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현 해야 TreeSet에 추가 될 수 있음
- Member클래스가 아이디 오름차순으로 정렬되게 하기 위해 Comparable 인터페이스를 구현
package ch13;
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 boolean equals(Object obj) {
if(obj instanceof Member) {
Member member=(Member)obj;
if(this.memberId==member.memberId) {
return true;
}
else return false;
}
return false;
}
@Override
public int hashCode() {
return memberId;
}
@Override
public String toString(){ //toString 메소드 오버로딩
return memberName + " 회원님의 아이디는 " + memberId + "입니다";
}
@Override
public int compareTo(Member member) {
return (this.memberId-member.memberId);
}
}package ch13;
import java.util.Iterator;
import java.util.TreeSet;
public class MemberTreeSet {
private TreeSet<Member> treeSet;
public MemberTreeSet() {
treeSet=new TreeSet<>();
}
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();
}
}package ch13;
import java.util.Comparator;
import java.util.TreeSet;
class MyCompare implements Comparator<String>{
@Override
public int compare(String s1, String s2) {
return s1.compareTo(s2)*(-1);
}
}
public class MemberTreeSetTest {
public static void main(String[] args) {
/*
MemberTreeSet memberTreeSet=new MemberTreeSet();
Member memberHong=new Member(1004,"홍길동");
Member memberLee = new Member(1001, "이순신");
Member memberKim = new Member(1002, "김유신");
Member memberKang = new Member(1003, "강감찬");
memberTreeSet.addMember(memberHong);
memberTreeSet.addMember(memberLee);
memberTreeSet.addMember(memberKim);
memberTreeSet.addMember(memberKang);
memberTreeSet.showAllMember();
*/
TreeSet<String> set = new TreeSet<String>(new MyCompare());
set.add("Park");
set.add("Kim");
set.add("Lee");
System.out.println(set);
}
}반응형