JAVA 자료구조

최신 JAVA 구현 자료구조론

한정란 저자의 최신 JAVA 구현 자료구조론 도서를 읽고 학습한 내용 기록

출처 : 최신 JAVA 구현 자료구조론 - 한정란 

 

 

학습 구성

 

1. 자료(=data)의 특성마다 해당 자료에 맞는 자료 구조들이 존재
   ex) 대기자 명단 자료, 동물 목록 자료, 아이디 비밀번호 자료, 괄호 개수 체크하는 자료(괄호라는 자료를 준다.) 등등
   
   
2. 헤당 자료에 맞는 자료구조를 선택
   ex) list, set, map, stack, queue, deck, linked, ...
   
   
3. 자료를 통해서 원하는 결과 도출
   • 알고리즘 이용 : 명령문을 사용해서 결과를 도출
     ex) for, if, while, 람다식, break문 

 

• 결론
  • 자료구조는 정형화된 틀이 존재. 알맞는 자료 구조를 사용해서 효율적으로 프로그램 성능을 높일 수 있다.
  • 알고리즘은 행당 자료구조를 입맛에 맞게 재 가공 하는 과정으로 큰 정형화된 틀이 없다. - 물론 자주쓰는 것은 있을 수 있다.

 

 

자료 -> 자료구조 -> 명령문으로 되어있는 알고리즘

 

1. 알고리즘과 자료 구조 성능

 

• 자료 구조
  • 처리할 자료들 사이에 관계를 고려하여 컴퓨터 내부에 표현하는 방법들을 총칭하는 말
• 자료
  • 컴퓨터에서 변수를 사용해 자료 값을 저장
• 자료구조
  • '자료형과 관련된 값'과' 저장될 변수'의 관계의 구조를 나타내는 것
  • 여러방법으로 연결된 변수들의 집합
• 알고리즘
  • 자료구조로 표현된 자료를 처리하는 절차들의 모임, 특정한 문제 해결을 위해 기술한 명령문

 

1.1 알고리즘

• 알고리즘을 흐름도라고 표현한다.
• flow chart

 

1.2 알고리즘 성능 분석 5가지

 

1. 시간 복잡도
   • 실행 시간으로 알고리즘을 구현한 프로글매을 컴퓨터에서 실행할 때 소요되는 CPU 시간
2. 공간 복잡도
   • 알고리즘에 사용한 자료를 저장하는 기억공간의 양
3. 정확성
4. 간결성
5. 최적성

 

2. 순차 자료 구조

• 선형 리스트 형태
• 종류
  1. 배열
  2. 행렬 - 희소행렬, 희소배열
  3. 컬렉션 - vector

 

2.1. 행렬

• 희소 행렬
  • 전체 원소 수에 비해 실제로 값을 사용하는 원소 수가 아주 적은 행렬
  • 메모리 절략을 위해 원소 수가 있는 행과 열에 대한 정보를 별도로 구성하는 것이 효과적
• 희소 배열
  • 희소 행렬의 메모리 절략을 위해 별도로 구성한 배열 
  • 한 행에 희소 행렬의 행, 열, 값을 작성 3x3 배열로 생성

 

2.2 배열의 표현

• 일차원 배열 L에서 각 원소를 저장하는데 필요한 셀의 크기를 s bite라 할 때 i 번째 놓인 원소의 물리적인 주소를 계산
• array L의 시작주소가 a일 때 L[i]의 주소는 a+ i*s 가 된다.

 

2.3 컬렉션

• java에선 vector, ArrayList, Stack Queue Map 등 자료구조 제공 -> 선형리스트를 벡터를 사용해 표현하면 편리
• 클래스 타입의 자료 저장

 

 

 

3. 연결 리스트

• 선형 리스트의 단점을 개선
• 종류
  1. 원형 연결 리스트
  2. 이중 연결 리스트
  3. 원형 이중 연결 리스트 

이전에 만들었던 MyLinkedList와 동일: 2023.03.27 - [java/java 심화] - LinkedList 구현하기

 

 

4. 스택

• top: 삭제가 일어나는 곳
• push: 삽입 연산
• pop : 삭제 연산

 

• 순차 스택 생성 구조
  1. 스택 생성
  2. 공백 스택인지 확인하는 연산 isEmpty()
  3. 스택에 우너소를 삽입하는 연산
  4. 스택에서 원소를 삭제하는 연산
  5. 스택의 원소를 반환하는 연산

 

4.1. array stack

package study;

public class MyArrayStack {
    private int top; //top 원소 가리키는 변수
    private int size; // 배열의 크기
    private int increment; // 배열 확장 단위
    private Object[] itemStack; // 원소 저장하는 배열
    private Object itemEmpty = "empty";


    // 스택 멤버변수들 초기화
    public MyArrayStack() {
        top = -1;
        size = 50;
        increment = 10;
        itemStack = new Object[size];
    }

    public boolean isEmpty() {
        return top == -1; // 공백 스택
    }

    public void push(Object x){
        if (top == size - 1) {
            size += increment;
            Object[] tempArray = new Object[size];
            for (int i = 0; i < top; i++) tempArray[i] = itemStack[i];
            itemStack = tempArray;
        }
        itemStack[++top] = x; // 원소 삽입
    }

    public Object pop() {
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return itemEmpty;
        }
        return itemStack[top--];
    }

    public Object peek() {
        if (isEmpty()) {
            System.out.println("Stack Empty");
            return itemEmpty;
        } else {
            return itemStack[top];
        }
    }

    public void print() {
        for (int i = 0; i < top; i++) System.out.print(itemStack[i] + ",");
        System.out.println(itemStack[top]);
        System.out.println();
    }
}

 

 

4.2. 연결 리스트를 사용해서 스택 구현

• 스택이 가득 차는 것을 의식할 필요가 없다.

package study;

public class MyLinkedStack {
    StackNode top;
    String itemEmpty = "StackEmpty";

    // 추가
    void push(String x) {
        StackNode temp;
        // stack이 공백인 경우
        if (top == null) {
            top = new StackNode();
            top.data = x;
            top.link = null;
        } else {
            temp = new StackNode();
            temp.data = x;
            temp.link = top;
            top = temp;
        }
    }

    void print() {
        StackNode temp;
        temp = top;
        while (temp != null) {
            System.out.println(temp.data + ",");
            temp = temp.link;
        }
        System.out.println("null");
    }

    // 제일 top stackNode 출력
    Object peek() {
        if (top == null) {
            System.out.println("null");
            return itemEmpty;
        }
        return top.data;
    }

    
    // 제거
    void pop() {
        if (top == null) System.out.println("null");
        else top = top.link;
    }
}

class StackNode {
    Object data;
    StackNode link;
}

 

 

 

5. 큐

• FIFO 구조 : 삽입과 삭제가 서로 다른 곳에서 이뤄지는 리스트
• 작동 구조
  • rear: 삽입
  • front: 삭제
• 제일 먼저 들어온 값이 front로 고정
• 값이 들어올 때마다 rear위치가 뒤로 넘어간다.

 

• 생성 원리
  1. 핵심 연산
     
     • (front +1 ) % size
     • (rear +1 ) % size
  2. 공백 검사
  3. 큐에 원소 삽입 연산
     • 배열 공간 늘리기
     • front는 유지
     • rear 늘리기
  4. 큐에 원소 삭제
     • front를 늘린다.
     • rear 유지

 

5.1 arrayQueue

package study;

public class ArrayQueue {
    private int front;
    private int rear;
    private int count;
     int size;
    private final int increment;
    private Object[] itemQueue;
    private final Object itemEmpty = "empty";

    public ArrayQueue() {
        front = 0; // 처음 큐
        rear = 0; // 큐 저장 위치
        count = 0; // 큐 개수
        size = 5; // 큐 처음 크기
        increment = 10; // 배열 확장 단위
        itemQueue = new Object[size]; // 큐원소 저장 배열
    }

    public boolean isEmpty() {
        return (count == 0);
    }

    public void insert(Object x) {
        if (count == size) {
            int oldSize = size;
            size += increment;
            Object[] tempArray = new Object[size];
            System.out.println("front = " + front);
            for (int i = 0; i < count; i++, front = (front + 1) % oldSize) { // i++과 front 계산은 제일 마지막에 수행
//                System.out.println("f: " + front); // 0부터 채워 넣음
                tempArray[i] = itemQueue[front];
            }
            itemQueue = tempArray;
            front = 0;
            rear = count;
        }
        itemQueue[rear] = x;
        rear = (rear + 1) % size;
        count++;
    }

    public Object delete() {
        if (isEmpty()) {
            System.out.println("empty");
        }
        Object tempItem = itemQueue[front];
        front = (front + 1) % size;
        count--;
        return tempItem;
    }

    public Object peek() {
        if (isEmpty()) {
            System.out.println("empty");
            return itemEmpty;
        } else {
            return itemQueue[front];
        }
    }

    public void print() {
        for (int i = front; i < rear; i++) {
            System.out.println(itemQueue[i]);
        }
        System.out.println();
    }
}

package study;

import static org.junit.jupiter.api.Assertions.*;

class ArrayQueueTest {


    public static void main(String[] args) {
        ArrayQueue q = new ArrayQueue();
        q.insert(1);
        q.insert(2);
        q.insert(3);
        q.print();
        q.insert(4);
        q.insert(5);
        q.insert(6);
        q.insert(7);
        q.print();

        q.delete();
        q.delete();
        q.delete();
        q.delete();
        q.delete();
        q.print();


        System.out.println("size: " + q.size);
    }

}

 

5.2. LInkedlist queue

• 배열일 때 크기제한으로 인해서 확장 하는 단점 존재
• linkedList의 node를 이용해서 q를 연결

package study;

public class LinkedQueue {
    QueueNode front, rear;

    void insert(Object x) {
        QueueNode temp;
        if (rear == null) {
            rear = new QueueNode();
            rear.data = x;
            front = rear;
        } else {
            temp = new QueueNode();
            temp.data = x;
            rear.link = temp;
            rear = temp;
            rear.link = null;
        }
    }

    void delete() {
        if (front == null) {
            System.out.println("null");
        } else {
            front = front.link; // 삭제 전 front 참조변수를 변경
            if (front == null) {
                rear = null;
            }
        }
    }

    void print() {
        QueueNode temp;
        temp = front;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.link;
        }
        System.out.println("null");
    }
}

class QueueNode {
    Object data;
    QueueNode link;
}

 

package study;

import static org.junit.jupiter.api.Assertions.*;

class LinkedQueueTest {
    public static void main(String[] args) {
        LinkedQueue q = new LinkedQueue();
        QueueNode temp;

        q.front = q.rear = null;

        q.insert(1);
        q.insert(2);
        q.insert(3);
        q.insert(4);
        q.print();
        q.delete();
        q.print();
    }

}

 

 

6. 덱

• 스택과 큐의 성질을 합한 선형 리스트
• 스택과 큐를 확장하여 삽입과 삭제를 리스트의 양끝에서 수행하는 자료 구조
• arrayDeque라고 Deque 인터페이스를 구현한 구현 클래스 존재

 

package study;

public class MyDeque {
    private int front;
    private int rear;
    private int count;
    int size;
    private int increment;
    private Object[] itemDeque;
    private final Object itemEmpty = "empty";

    public MyDeque() {
        front = 0; // 처음 큐
        rear = 0; // 큐 저장 위치
        count = 0; // 큐 개수
        size = 5; // 큐 처음 크기
        increment = 10; // 배열 확장 단위
        itemDeque = new Object[size]; // 큐원소 저장 배열
    }

    public boolean isEmpty() {
        return (count == 0);
    }

    public void increaseArray() {
        size += increment;
        Object[] tempArray = new Object[size];
        for (int i = 0; i < rear; i++) {
            tempArray[i] = itemDeque[i];
        }
        itemDeque = tempArray;
    }

    public void insertLast(Object x) {
        itemDeque[rear] = x; // 값 넣기
        rear++;             // rear 값 증가
        if (rear == size) { // size 초과시 array 확장
            increaseArray();
            count++;
        }
    }

    public void insertFirst(Object x) {
        if (count != 0) {
            for (int i = count; i > 0; i--) {
                itemDeque[i] = itemDeque[i - 1];
                itemDeque[0] = x;
                count++;
                rear = count;
                if (rear == size) {
                    increaseArray();
                }
            }
        }
    }

    public Object deleteFirst() {
        if (isEmpty()) {
            System.out.println("null");
            return itemEmpty;
        }
        Object tempItem = itemDeque[0];
        for (int i = 0; i < count; i++) {
            itemDeque[i] = itemDeque[i + 1];
        }
        count--;
        rear--;
        return tempItem;
    }

    public Object deleteLast() {
        if (isEmpty()) {
            System.out.println("null");
            return itemEmpty;
        }
        Object tempItem = itemDeque[rear - 1];
        rear--;
        count--;
        return tempItem;
    }

    public Object First() {
        if (isEmpty()) {
            return itemEmpty;
        } else return itemDeque[front];
    }

    public Object Last() {
        if (isEmpty()) {
            return itemEmpty;
        } else return itemDeque[rear - 1];
    }

    public void print() {
        if (isEmpty()) {
            System.out.println("null");
        } else
            for (int i = 0; i < rear; i++)
                System.out.println(itemDeque[i]);
    }

}

 

 

7. 정렬과 탐색

• 버블 정렬이란 것이 존재하지만 성능이 너무 떨어지므로 생략

 

7.1. 선택정렬

• 가장 작은 값부터 차례대로 리스트의 앞으로 옮겨서 앞에서부터 뒤로 || 뒤에서부터 앞으로 정렬하는 직관적이고 가장 간단한 방법
• 알고리즘
  • 최솟값을 찾아서 배열 맨 앞의 수와 교환
  • 정렬된 첫번째 수 제외하고 최솟값 찾아서 교환
  • 반복
• 핵심 로직

int temp = data[i];
data[i] = data[min];
data[min] = temp;

 

7.2. 삽입 정렬

• 정렬된 부분과 정렬되지 않은 부분을 나눈다.
• 정렬되지 않은 부분 중 첫 요소를 정렬된 부분의 적절한 위치에 삽입
• 정렬이 다 될때 까지 반복
• 양극화의 시간 복잡도를 가진다.
  1. 정렬이 된 경우 : 최상의 시간 복잡도
  2. 역순 정렬이 된 경우 : 최악의 시간 복잡도

 

• 핵심 로직

for (int i = 1; i < size; i++) {
    int temp = data[i];
    int j = i;
    while ((j > 0) && (data[j - 1] > temp)) {
        data[j] = data[j - 1];
        j--;
    }
    data[j] = temp;
}

 

 

7.3. 쉘 정렬

• 삽입 정렬에 전처리과정을 추가한 것.
• 대충 작은 값을 앞으로 큰 값을 뒤로 보내는 전처리 과정을 진행

코드 생략

 

 

7.4. 큌 정렬

• 정렬 알고리즘 표준이 되고 가장 유명한 정렬 방법 이다.
• 기준이 되는  pivot을 선정하여 pivot을 기준으로 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 재배치하고 다시 분할하여 정렬하는 알고리즘
• 보통의 경우 데이터의 맨 왼쪽 원소나 중간에 위치한 값을 피벗으로 정해 수행

 

• 되게 복잡하다. 이해 필요....

public class QuickSort {
    public static void quickSort(final int[] data, int start, int end) {
        if (start < end) {
            int low = start;
            int high = end;
            int pivot = data[(low + high) / 2];
            while (low < high) {
                while (data[low] < pivot) low++;
                while (data[high] > pivot) high--;
                if (low < high) {
                    int tmp = data[low];
                    data[low] = data[high];
                    data[high] = tmp;
                }
            }
            System.out.println(Arrays.toString(data));
            quickSort(data, start, low - 1);
            quickSort(data, low + 1, end);
        }
    }
}

 

 

7.5. 합병 정렬

• 정렬할 리스트를 반으로 분할, 좌측과 우측 리스트를 계속하여 분할 하면서 합병하면서 정렬하는 방법
• 정렬 알고림즘 중에 비교적 간단해서 많이 쓰이고 있는 알고리즘 중하나이며 시간 복잡도는 최소를 보장
• 데이터 전체 크기만큼의 기억 공간이 더 필요

 

7.6. 힙 정렬

• 이진트리의 한 종류인 최ㅣ대 힙을 이용해 정렬하는 방법, 최대 힙의 각 노드는 자식 노드들보다 큰 값을 갖는 구조로 최대 힙의 루트가 최댓값이라는 점을 활용해 정렬 수행

7.7.탐색

• 종류
  1. 순차 탐색
  2. 이진 탐색
  3. 해시 탐색

 

 

 

나~~~~~중에 시간 있을 때 추가 필요!!!

---

 

 

 

 

https://bnzn2426.tistory.com/115

자료 구조(Data Structure) 개념 및 종류 정리