개발자로 살아남기

전체 글

[JAVA] 선택 정렬 (Selection Sort) 2021.11.03
[JAVA] 버블 정렬 (Bubble Sort) 2021.11.02
우선순위 큐(Priority Queue)와 힙 (Heap) 2021.10.27
[Java] 트리 (Tree)와 이진트리 (Binary Tree) 2021.10.23
큐 (Queue) 2021.10.19
스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] 2021.10.18
스택 (Stack) 2021.10.15
양방향 연결 리스트 (이중 연결 리스트) 2021.10.14

선택 정렬 (Selection Sort)

제자리 정렬 (in-place sort)
- 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
비안정 정렬 (unstable sort)
- 정렬 후에 같은 값들의 순서가 변함
- 아래는 같은 값을 A, B로 구분하였음
ex) 3(A), 6, 2, 5, 4, 3(B), 1
1, 2, 3(B), 3(A), 4, 5, 6
정렬할 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

선택 정렬 방법

위 그림은 아래 방법을 그림으로 표현한 것

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다.
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

성능

시간복잡도
최악의 경우 : O(n^2)
최선의 경우 : O(n^2)

최악과 최선 모두 n^2 의 시간복잡도를 가짐
데이터가 삽입될 위치를 정하는 반복문과 최소값을 찾는 반복문이 이중으로 구현되어 있으므로

구현

int형을 기본으로 구현
[SelectionBasic.java]

package Sort.Selection;

public class SelectionBasic {
    public static void sort(int[] arr, boolean isDescending) {
        // 배열 중 최소값의 위치를 저장하기 위한 변수
        int minIndex = 0;
        int n = arr.length;

        // 데이터가 삽입될 위치를 정하는 반복문
        for(int i=0; i<n-1; i++) {
            minIndex = i;

            // 최소값을 찾기위한 반복문
            for(int j=i+1; j<n; j++) {
                // minIndex의 값과 현재 j값을 비교하여 정렬을 해야하는지 확인
                if (!isSortTwoElements(arr[minIndex], arr[j], isDescending)) {
                    // 정렬이 필요할 경우 minIndex 값을 현재 j값으로 변경
                    minIndex = j;
                }
            }

            // 삽입될 위치(i)와 최소값의 위치(minIndex)를 이용해 교환 진행
            swap(arr, minIndex, i);
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    /**
     *
     * @param cmp1 비교할 값
     * @param cmp2 비교할 값
     * @param isDescending 내림차순 및 오름차순 선택
     * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
     *         오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
     */
    private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
        // 내림차순일 경우
        if (isDescending) {
            if (cmp1 < cmp2) {
                return false;
            }
            else {
                return true;
            }
        }
        // 오름차순일 경우
        else {
            if (cmp1 < cmp2) {
                return true;
            }
            else {
                return false;
            }
        }
    }
}

테스트
[SelectionBasicMain.java]

package Sort.Selection;

public class SelectionBasicMain {
    private static final int MAX_COUNT = 30;

    public static void main(String[] args) {
        int[] arr = new int[MAX_COUNT];
        for(int i=0; i<MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int)(Math.random() * MAX_COUNT);
        }

        System.out.println("정렬 전 데이터");
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();

        int[] ascSelectionSortTestArray = arr.clone();
        System.out.println("정렬 후 데이터 (오름차순)");
        SelectionBasic.sort(ascSelectionSortTestArray, false);
        for(int i : ascSelectionSortTestArray) {
            System.out.print(i + " ");
        }
        System.out.println();

        int[] descSelectionSortTestArray = arr.clone();
        System.out.println("정렬 후 데이터 (내림차순)");
        SelectionBasic.sort(descSelectionSortTestArray, true);
        for(int i : descSelectionSortTestArray) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

결과

클래스의 특정 값을 이용한 정렬
[SelectionAdvanced.java]

package Sort.Selection;

import java.util.Comparator;

/**
 * 클래스 내 특정 값을 이용하여 정렬하는 방법
 */
public class SelectionAdvanced {
    public static <T> void sort(T[] arr) {
        Comparable<? super T> comp = null;

        int minIndex = 0;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            minIndex = i;

            comp = (Comparable<? super T>)arr[minIndex];
            for(int j=i+1; j<n; j++) {
                // 오름차순
                if (comp.compareTo(arr[j]) < 0) {
                    minIndex = j;
                }
            }

            swap(arr, minIndex, i);
        }
    }


    public static <T> void sort(T[] arr, Comparator<? super T> comp) {
        int minIndex = 0;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            minIndex = i;

            for(int j=i+1; j<n; j++) {
                if (comp.compare(arr[minIndex], arr[j]) > 0) {
                    minIndex = j;
                }
            }

            swap(arr, minIndex, i);
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static <T> void swap(T[] arr, int idx1, int idx2) {
        T tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}

테스트

package Sort.Selection;

import java.util.Comparator;

public class SelectionAdvancedMain {
    private static final int MAX_COUNT = 30;

    public static void main(String[] args) {
        Integer[] arr = new Integer[MAX_COUNT];
        for(int i=0; i<MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int)(Math.random() * MAX_COUNT);
        }

        System.out.println("정렬 전 데이터");
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println();

        System.out.println("정렬 후 데이터 (오름차순)");
        SelectionAdvanced.sort(arr);
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println();
        System.out.println();

        class Student {
            String name;
            int age;

            public Student(String name, int age) {
                this.name = name;
                this.age = age;
            }

            @Override
            public String toString() {
                return "name='" + name + '\'' +
                        ", age=" + age;
            }
        }

        Student[] students = new Student[5];
        students[0] = new Student("아이언맨", 11);
        students[1] = new Student("헐크", 4);
        students[2] = new Student("토르", 15);
        students[3] = new Student("블랙위도우", 13);
        students[4] = new Student("캡틴", 4);

        System.out.println("클래스 정렬 전 데이터");
        for (int i=0; i<students.length; i ++) {
            System.out.println(students[i]);
        }
        System.out.println();

        System.out.println("클래스 정렬 후 데이터 (나이 내림차순)");
        SelectionAdvanced.sort(students, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age < o2.age) {
                    return 1;
                }
                else if (o1.age == o2.age) {
                    return 0;
                }
                else {
                    return -1;
                }
            }
        });

        for (int i=0; i<students.length; i ++) {
            System.out.println(students[i]);
        }
    }
}

결과

'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글

[JAVA] 합병(병합) 정렬 (Merge Sort) (2)	2021.11.05
[JAVA] 삽입 정렬 (Insertion Sort) (0)	2021.11.04
[JAVA] 버블 정렬 (Bubble Sort) (0)	2021.11.02
깊이 우선 탐색 (DFS, Depth-First Search) (0)	2021.10.08
순열(Permutation) 구하기 (0)	2021.10.06

버블 정렬 (Bubble Sort)

가장 단순한 정렬 알고리즘
인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환
안정 정렬 (stable sort)
: 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미
제자리 정렬 (in-place sort)
: 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

버블 정렬 방법 (오름차순 기준)

첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다.

버블 정렬의 성능

시간복잡도
최악의 경우 : O(n^2)
최선의 경우 : O(n)
최악의 경우 : 모든 데이터가 역순인 경우 (5, 4, 3, 2, 1)
5를 정렬하기 위해서는 n-1번 비교 및 교환해야하고, 4를 정렬하기 위해서는 n-2번 비교 및 교환해야 한다.
즉, 5를 정렬할 때 4번, 4를 정렬할 때 3번, 3을 정렬할 때 2번, 1과 2를 정렬할 때 1번의 비교 및 교환을 거치게 되므로 비교 횟수는 4 + 3 + 2 + 1회가 된다.
따라서, 데이터가 n개일 때 총 비교횟수는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 이 되므로 등차수열의 합에 따라 1/2n(n-1)이 되며 빅-오는 최고차항을 가지기 때문에 O(n^2)이 된다.
최선의 경우 : 모든 데이터가 이미 정렬된 경우 (1, 2, 3, 4, 5)
한 번도 교환이 이루어지지 않았다면 이미 정렬된 상태이므로 n번 비교 후 반환되어 O(n) 이 된다.

기본 구현

기본 int형 배열 정렬 구현
[BubbleBasic.java]

package Sort.Bubble;

/**
 * 단순히 int형 배열만 오름차순 또는 내림차순으로 정렬하는 경우
 */
public class BubbleBasic {
    private boolean isDescending = false;

    /**
     * @param arr int형 배열
     * @param isDescending 내림차순 및 오름차순 선택
     */
    public static void sort(int[] arr, boolean isDescending) {
        // 이미 정렬이 되어있는지 확인하기 위한 변수
        boolean isAlreadySorted = true;
        int n = arr.length;

        // 정렬할 값을 선택하는 반복문
        for(int i=0; i<n-1; i++) {
            // 정렬할 값과 나머지 값들을 비교하기 위한 반복문
            // 이미 정렬이 완료된 데이터는 비교대상에서 제외해야 하므로 n-i-1
            for(int j=0; j<n-i-1; j++) {
                // 정렬되지 않았다면
                if (!isSortTwoElements(arr[j], arr[j + 1], isDescending)) {
                    // 데이터를 교환한다.
                    swap(arr, j, j + 1);
                    // 스왑을 했다면 초기 배열 상태가 정렬되지 않았다는 것이므로 false로 변경
                    isAlreadySorted = false;
                }
            }

            // 한 번도 교환이 발생하지 않았다면 이미 정렬된 데이터이므로 반복문을 빠져나온다.
            if (isAlreadySorted) {
                break;
            }
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    /**
     *
     * @param cmp1 비교할 값
     * @param cmp2 비교할 값
     * @param isDescending 내림차순 및 오름차순 선택
     * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
     *         오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
     */
    private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
        // 내림차순일 경우
        if (isDescending) {
            if (cmp1 < cmp2) {
                return false;
            }
            else {
                return true;
            }
        }
        // 오름차순일 경우
        else {
            if (cmp1 < cmp2) {
                return true;
            }
            else {
                return false;
            }
        }
    }
}

BubbleBasic.java 테스트 및 실행시간 측정

package Sort.Bubble;

public class BubbleBasicMain {
    private static final int MAX_COUNT = 10;

    public static void main(String[] args) {
        int[] arr = new int[MAX_COUNT];
        for(int i=0; i<MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int)(Math.random() * MAX_COUNT);
        }

        // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
        int[] ascArrTest = arr.clone();
        System.out.println("정렬 전 데이터");
        for(int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        BubbleBasic.sort(ascArrTest, false);
        System.out.println("오름차순 정렬 후 데이터");
        for(int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        int[] descArrTest = arr.clone();
        BubbleBasic.sort(descArrTest, true);
        System.out.println("내림차순 정렬 후 데이터");
        for(int i : descArrTest) {
            System.out.println(i);
        }

        // 시간복잡도 측정 (오름차순 기준)
        long start = 0;
        long end = 0;

        int[] bestTimeComplexityArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        start = System.nanoTime();
        BubbleBasic.sort(bestTimeComplexityArray, false);
        end = System.nanoTime();
        System.out.println("최선의 경우 오름차순 시간 : " + (end - start) + "ns");

        int[] worstTimeComplexityArray = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        start = System.nanoTime();
        BubbleBasic.sort(worstTimeComplexityArray, false);
        end = System.nanoTime();
        System.out.println("최악의 경우 오름차순 시간 : " + (end - start) + "ns");
    }
}

결과

정렬 전 데이터
2
6
1
7
7
6
0
6
1
0

오름차순 정렬 후 데이터
0
0
1
1
2
6
6
6
7
7

내림차순 정렬 후 데이터
7
7
6
6
6
2
1
1
0
0
최선의 경우 오름차순 시간 : 3805ns
최악의 경우 오름차순 시간 : 18532ns

클래스 비교를 위한 구현

클래스의 특정 값을 이용한 정렬 코드 구현
[BubbleAdvanced.java]

package Sort.Bubble;

import java.util.Comparator;

public class BubbleAdvanced {
    public static <T> void sort(T[] arr) {
        Comparable<? super T> comp;
        boolean isAlreadySorted = true;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-i-1; j++) {
                comp = (Comparable<? super T>)arr[j];
                if (comp.compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isAlreadySorted = false;
                }
            }

            if (isAlreadySorted){
                break;
            }
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static <T> void swap(T[] arr, int idx1, int idx2) {
        T tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    public static <T> void sort(T[] arr, Comparator<? super T> comparator) {
        boolean isAlreadySorted = true;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-i-1; j++) {
                if (comparator.compare(arr[j], arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isAlreadySorted = false;
                }
            }

            if (isAlreadySorted){
                break;
            }
        }
    }
}

BubbleAdvanced 테스트

package Sort.Bubble;

import java.util.Comparator;

public class BubbleAdvancedMain {
    private static final int MAX_COUNT = 10;

    public static void main(String[] args) {
        Integer[] arr = new Integer[MAX_COUNT];
        for (int i = 0; i < MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int) (Math.random() * MAX_COUNT);
        }

        // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
        Integer[] ascArrTest = arr.clone();
        System.out.println("정렬 전 데이터");
        for (int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        BubbleAdvanced.sort(ascArrTest);
        System.out.println("오름차순 정렬 후 데이터");
        for (int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        Integer[] descArrTest = arr.clone();
        System.out.println("내림차순 정렬 후 데이터");
        BubbleAdvanced.sort(descArrTest, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 < o2) {
                    return 1;
                } else if (o1 == o2) {
                    return 0;
                } else {
                    return -1;
                }
            }
        });
        for (int i : descArrTest) {
            System.out.println(i);
        }
        System.out.println();

        // 클래스의 특정값을 이용한 정렬 가능
        class Student {
            String name;
            int age;

            public Student(String name, int age) {
                this.name = name;
                this.age = age;
            }

            @Override
            public String toString() {
                return "name='" + name + '\'' +
                        ", age=" + age;
            }
        }

        System.out.println("클래스 정렬 전 데이터");
        Student[] students = new Student[5];
        students[0] = new Student("아이언맨", 11);
        students[1] = new Student("헐크", 4);
        students[2] = new Student("토르", 15);
        students[3] = new Student("블랙위도우", 13);
        students[4] = new Student("캡틴", 4);
        for(Student student : students) {
            System.out.println(student.toString());
        }
        System.out.println();

        System.out.println("클래스 정렬 후 데이터");
        BubbleAdvanced.sort(students, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age < o2.age) {
                    return -1;
                }
                else if (o1.age == o2.age) {
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        for(Student student : students) {
            System.out.println(student.toString());
        }
    }
}

결과

정렬 전 데이터
7
0
0
9
4
4
6
0
5
0

오름차순 정렬 후 데이터
0
0
0
0
4
4
5
6
7
9

내림차순 정렬 후 데이터
9
7
6
5
4
4
0
0
0
0

클래스 정렬 전 데이터
name='아이언맨', age=11
name='헐크', age=4
name='토르', age=15
name='블랙위도우', age=13
name='캡틴', age=4

클래스 정렬 후 데이터
name='헐크', age=4
name='캡틴', age=4
name='아이언맨', age=11
name='블랙위도우', age=13
name='토르', age=15

'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글

[JAVA] 삽입 정렬 (Insertion Sort) (0)	2021.11.04
[JAVA] 선택 정렬 (Selection Sort) (0)	2021.11.03
깊이 우선 탐색 (DFS, Depth-First Search) (0)	2021.10.08
순열(Permutation) 구하기 (0)	2021.10.06
그리디(Greedy) 알고리즘 (탐욕 알고리즘) (0)	2021.10.05

우선순위 큐(Priority Queue)와 힙 (Heap)

2021. 10. 27. 16:12

우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐 (Priority Queue)

기존의 큐와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옴
데이터간에 순서가 보장되지 않음
ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력
구현방법 및 특징
- 배열 기반으로 구현
1) 인덱스로 데이터에 바로 접근할 수 있음
2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함
3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함
4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1)

- 연결리스트 기반으로 구현
1) 삽입의 위치를 찾기위해 최악의 경우 리스트의 모든 데이터와 우선순위를 비교해야 함
2) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(n)

- 힙(heap)을 이용한 구현
1) 완전 이진트리의 형태
2) 단말노드에서 루트노드로 갈수록 값이 커지는 것을 최대 힙 (max heap) 이라고 하며 그 반대는 최소 힙 (min heap) 이라고 함
3) 저장 시 시간복잡도 O(logN), 삭제 시 시간복잡도 O(logN)
4) 형제노드끼리의 대소관계는 정해지지 않음

힙의 구현 (최대 힙 기준) 방법

힙도 마찬가지로 배열과 연결리스트로 구현 가능
그러나 배열로 구현하는 것이 일반적 (리스트로 구현할 경우 특정노드에 접근하거나 데이터 저장 시 마지막 위치를 알기 어렵기 때문)
데이터 저장
1) 완전 이진 트리르 ㄹ만족하는 마지막 위치에 데이터 저장
2) 부모노드와 대소관계 비교 후 부모노드의 값이 더 클 경우 교환하는 과정을 반복 (최대 힙 기준)
3) 아래는 데이터 10, 5, 7, 1 순으로 저장된 트리에 8을 저장한 그림
데이터 삭제
1) 데이터의 루트노드 삭제
2) 루트노드의 빈 공간은 마지막 노드를 루트노드로 설정
3) 자식노드들과 비교하며 더 큰 자식노드와 교환
노드마다 인덱스 값 부여
구현의 편의 상 인덱스는 1번부터 적용
노드의 인덱스 값 구하기
- 완전 이진 트리의 특성 때문에 아래와 같이 수식화 할 수 있음
- 아래 수식의 결과값들은 모두 정수 형태 (5 / 2 => 2)
1) 왼쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2
2) 오른쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2 + 1
3) 부모노드의 인덱스 값 : 자식노드의 인덱스 값 / 2

힙 구현

추상자료형 (ADT)

자료형	반환값	내용
Initialize()	void	힙 초기화
initialize(comparator)	void	힙 초기화 (비교함수 외부 등록)
isEmpty()	boolean	힙이 비어있는지 확인
compareHighChild(index)	int	자식노드 중 누가 더 우선순위가 높은지 반환
add(Data)	void	힙에 데이터 추가
remove()	Data	데이터 삭제
getParent(index)	int	부모노드의 위치값 반환
getLChild(index)	int	왼쪽 자식노드의 위치값 반환
getRChild(index)	int	오른쪽 자식노드의 위치값 반환

핵심기능
- 데이터 추가 : 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음
- 데이터 삭제 : 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음

구현

[ArrayHeap.java]

package Heap.ArrayList;

import java.util.Comparator;

public class ArrayHeap<E> {
    private int MAX_CAPACITY = 5;
    // 외부에서 정렬 방법 설정을 위한 변수
    private Comparator<? super E> comparator = null;
    // 내부에서 사용할 정렬을 위한 변수
    private Comparable<? super E> comp = null;
    private Object[] heap = null;
    private int dataCount = 0;

    public void init(int capacity) {
        MAX_CAPACITY = capacity;
        heap = new Object[MAX_CAPACITY + 1];
        dataCount = 0;
    }

    public void init(int capacity, Comparator<? super E> comparator){
        MAX_CAPACITY = capacity;
        heap = new Object[MAX_CAPACITY + 1];
        dataCount = 0;
        this.comparator = comparator;
    }

    // index의 두 개의 자식 중 더 높은 놈 반환
    private int compareHighChild(int index) {
        // 자식이 없을 때
        if (getLChild(index) > dataCount) {
            return 0;
        }
        // 자식이 한 개
        // 이진트리이므로 왼쪽부터 채워지기 때문에 왼쪽 자식노드만 확인
        else if (getLChild(index) == dataCount) {
            return getLChild(index);
        }
        // 자식이 두 개
        else {
            int lChild = getLChild(index);
            int rChild = getRChild(index);

            if (comparator == null) {
                comp = (Comparable<? super E>)heap[lChild];

                if (comp.compareTo((E)heap[rChild]) < 0) {
                    return lChild;
                }
                else {
                    return rChild;
                }
            }
            else {
                if (comparator.compare((E) heap[lChild], (E) heap[rChild]) < 0) {
                    return lChild;
                }
                else {
                    return rChild;
                }
            }
        }
    }

    public boolean isEmpty() {
        if (dataCount == 0){
            return true;
        }

        return false;
    }

    // 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음
    public void add(E data) {
        if (dataCount > MAX_CAPACITY) {
            System.out.println("저장 공간이 부족합니다.");
            return;
        }

        int index = dataCount + 1;
        while (index != 1){
            if (comparator == null) {
                // 부모노드와 우선순위 비교
                comp = (Comparable<? super E>) data;
                // 자식노드의 우선순위가 더 낮은 경우
                if (comp.compareTo((E)heap[getParent(index)]) >= 0){
                    break;
                }
            }
            else {
                // 부모노드와 우선순위 비교
                // 자식노드의 우선순위가 더 낮은 경우
                if (comparator.compare(data, (E)heap[getParent(index)]) >= 0){
                    break;
                }
            }

            // 자식노드가 더 우선순위가 높으므로 부모노드를 자식노드와 swap함
            heap[index] = heap[getParent(index)];
            index = getParent(index);
        }

        dataCount++;
        heap[index] = data;
    }

    // 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음
    public E remove() {
        E removeData = (E)heap[1];
        heap[1] = null;
        int lastIndex = dataCount;

        int childIndex = 0;
        int parentIndex = 1;
        while((childIndex = compareHighChild(parentIndex)) > 0) {
            if (comparator == null) {
                comp = (Comparable<? super E>)heap[lastIndex];
                if (comp.compareTo((E)heap[childIndex]) < 0){
                    break;
                }
            }
            else {
                if (comparator.compare((E)heap[lastIndex], (E)heap[childIndex]) < 0){
                    break;
                }
            }

            heap[parentIndex] = heap[childIndex];
            parentIndex = childIndex;
        }

        heap[parentIndex] = heap[lastIndex];
        heap[lastIndex] = null;
        dataCount--;
        return removeData;
    }

    private int getParent(int index) {
        return index / 2;
    }

    private int getLChild(int index) {
        return index * 2;
    }

    private int getRChild(int index) {
        return index * 2 + 1;
    }

    public void printAll() {
        for(E e : (E[])heap) {
            if (e == null) {
                continue;
            }

            System.out.println(e);
        }
    }
}

[ArrayHeapMain.java]

package Heap.ArrayList;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

public class ArrayHeapMain {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        System.out.println("PriorityQueue 오름차순");
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(1);
        queue.add(1);

        Iterator<Integer> iterator = queue.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        System.out.println();
        System.out.println("PriorityQueue remove");
        queue.remove();
        iterator = queue.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        System.out.println();
        System.out.println("customQueue add");
        ArrayHeap<Integer> customQueue = new ArrayHeap<>();
        customQueue.init(5);

        customQueue.add(2);
        customQueue.add(3);
        customQueue.add(4);
        customQueue.add(1);
        customQueue.add(1);

        customQueue.printAll();

        System.out.println();
        System.out.println("customQueue remove");
        customQueue.remove();

        customQueue.printAll();
        System.out.println();

        System.out.println("PriorityQueue 내림차순");
        queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2){
                    return -1;
                }
                else if (o1 == o2){
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(1);
        queue.add(1);

        iterator = queue.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        System.out.println();
        System.out.println("customQueue 내림차순");
        customQueue.init(5, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2){
                    return -1;
                }
                else if (o1 == o2){
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        customQueue.add(2);
        customQueue.add(3);
        customQueue.add(4);
        customQueue.add(1);
        customQueue.add(1);
        customQueue.printAll();
    }
}

결과

1. 자바 내부의 PriorityQueue 와 직접 만든 Priority Queue 오름차순 비교

2. 자바 내부의 PriorityQueue 와 직접 만든 Priority Queue 내림차순 비교

'0x00. 자료구조' 카테고리의 다른 글

[Java] 트리 (Tree)와 이진트리 (Binary Tree) (0)	2021.10.23
큐 (Queue) (0)	2021.10.19
스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] (0)	2021.10.18
스택 (Stack) (0)	2021.10.15
양방향 연결 리스트 (이중 연결 리스트) (0)	2021.10.14

[Java] 트리 (Tree)와 이진트리 (Binary Tree)

2021. 10. 23. 13:47

트리 (Tree)

비선형 자료구조
계층적 관계를 표현하는 자료구조
(일상생활에서 사용하는 회사의 조직도 등)
여러 노드가 하나의 노드를 가리킬 수 없는 구조 (아래 그림은 트리가 아님)

용어 정리

노드 (node)
- 트리의 구성요소로, 위 그림에서 A, B, C, D, E, F가 이에 해당됨
간선 (edge)
- 노드와 노드를 연결하는 선
루트 노드 (root node)
- 위 그림의 트리구조에서 최상위에 존재하는 A를 의미
단말노드 (terminal node) 또는 잎사귀 노드 (leaf node)
- 다른 노드가 연결되어있지 않은 노드로서 위 그림에서 E, F, C, D가 이에 해당됨
내부노드 (internal node) 또는 비단말 노드 (nonterminal node)
- 단말노드를 제외한 모든 노드로서, A, B가 이에 해당됨
레벨
- 각 층에 숫자를 매기는 것
높이
- 트리의 최고레벨을 가리킴

노드와의 관계

노드 A는 B, C, D의 부모 노드이다. (parent)
B, C, D는 노드 A의 자식 노드이다. (child)
B, C, D는 부모가 같으므로 형제 노드이다. (sibling)

이진트리 (Binary Tree)와 서브트리 (Sub Tree)

서브트리 (Sub Tree)

큰 트리에 속하는 작은 트리
서브트리에 서브트리도 가능

이진트리 (Binary Tree)

루트노드로부터 두 개의 서브트리가 존재해야 함
노드가 있어야 할 곳에 노드가 존재하지 않으면 공집합 노드가 존재하는 것으로 간주함
(노드가 하나여도 두 개의 공노드가 있다고 간주하기 때문에 노드가 하나여도 이진트리가 됨)

포화 이진트리 (Full Binary Tree)와 완전 이진트리 (Complete Binary Tree)

포화 이진트리
- 모든 레벨에 노드가 가득 찬 상태이며 노드를 더 추가하기 위해서는 레벨을 늘려야 함
완전 이진트리
- 노드가 트리의 왼쪽부터 순서대로 채워진 것
아래 사진처럼 왼쪽부터 채워지지 않은 경우 이진트리이지만, 완전 이진트리가 아님

연결리스트 기반 이진트리

추상자료형 (ADT)

자료형	반환값	내용
createBTreeNode()	BTreeNode	이진트리 노드 생성
getData(BTreeNode)	Data	이진트리 노드의 데이터 반환
setData(BTreeNode, Data)	void	노드에 데이터 저장
getLeftSubTree(BTreeNode)	BTreeNode	왼쪽 서브트리를 반환
getRightSubTree(BTreeNode)	BTreeNode	오른쪽 서브트리를 반환
createLeftSubTree(BTreeNode, BTreeNode)	void	왼쪽에 서브트리를 연결
createRightSubStree(BTreeNode, BTreeNode)	void	오른쪽에 서브트리를 연결

연결리스트 기반 이진트리 구현

디렉토리 구조

BTreeNode.java

package BinaryTree.LinkedList;

public class BTreeNode {
    Object data;
    BTreeNode leftNode;
    BTreeNode rightNode;
}

BinaryTree.java

package BinaryTree.LinkedList;

public class BinaryTree {
    BTreeNode createBTreeNode() {
        BTreeNode newNode = new BTreeNode();
        newNode.leftNode = null;
        newNode.rightNode = null;

        return newNode;
    }

    Object getData(BTreeNode node) {
        return node.data;
    }

    void setData(BTreeNode node, Object data) {
        node.data = data;
    }

    BTreeNode getLeftSubTree(BTreeNode node) {
        return node.leftNode;
    }

    BTreeNode getRightSubTree(BTreeNode node) {
        return node.rightNode;
    }

    void createLeftSubTree(BTreeNode parent, BTreeNode child) {
        if (parent.leftNode != null){
            parent.leftNode = null;
        }

        parent.leftNode = child;
    }

    void createRightSubTree(BTreeNode parent, BTreeNode child) {
        if (parent.rightNode != null) {
            parent.rightNode = null;
        }

        parent.rightNode = child;
    }
}

BinaryTreeMain.java

package BinaryTree.LinkedList;

public class BinaryTreeMain {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();

        BTreeNode node1 = binaryTree.createBTreeNode();
        BTreeNode node2 = binaryTree.createBTreeNode();
        BTreeNode node3 = binaryTree.createBTreeNode();
        BTreeNode node4 = binaryTree.createBTreeNode();
        BTreeNode node5 = binaryTree.createBTreeNode();

        binaryTree.setData(node1, 'A');
        binaryTree.setData(node2, 'B');
        binaryTree.setData(node3, 'C');
        binaryTree.setData(node4, 'D');
        binaryTree.setData(node5, 'E');

        binaryTree.createLeftSubTree(node1, node2); // B를 A의 왼쪽 서브트리로 등록
        binaryTree.createRightSubTree(node1, node3); // C를 A의 오른쪽 서브트리로 등록
        binaryTree.createLeftSubTree(node2, node4); // D를 B의 왼쪽 서브트리로 등록
        binaryTree.createRightSubTree(node2, node5); // E를 B의 오른쪽 서브트리로 등록

        BTreeNode tmpNode = null;
        System.out.println(binaryTree.getData(node1)); // 루트 노드 데이터 반환

        tmpNode = binaryTree.getLeftSubTree(node1);
        System.out.println(binaryTree.getData(tmpNode)); // A의 왼쪽 서브트리 데이터 반환

        tmpNode = binaryTree.getRightSubTree(node1);
        System.out.println(binaryTree.getData(tmpNode)); // A의 오른쪽 서브트리 데이터 반환

        tmpNode = binaryTree.getLeftSubTree(node2);
        System.out.println(binaryTree.getData(tmpNode)); // B의 왼쪽 서브트리 데이터 반환

        tmpNode = binaryTree.getRightSubTree(node2);
        System.out.println(binaryTree.getData(tmpNode)); // B의 오른쪽 서브트리 데이터 반환
    }
}

결과

이진트리의 순회

전위순회 (Preorder Traversal) : 루트 노드를 먼저 순회
중위순회 (Inorder Traversal) : 루트 노드를 중간에 순회
후위순회 (Postorder Traversal) : 루트 노드를 마지막에 순회
중위순회 방법
- 재귀적으로 순회 가능
1) 왼쪽 서브트리 순회
2) 루트 노드 방문
3) 오른쪽 서브트리 순회

중위순회 구현

// 중위 순회
void InorderTraverse(BTreeNode node) {
    if (node == null){
        return;
    }

    InorderTraverse(node.leftNode);
    System.out.println(node.data);
    InorderTraverse(node.rightNode);
}

전위순회 및 후위순회
- 중위순회의 방법 1, 2, 3의 순서를 변경
- 중위순회

// 전위 순회
void PreorderTraverse(BTreeNode node) {
    if (node == null) {
        return;
    }

    System.out.println(node.data);
    PreorderTraverse(node.leftNode);
    PreorderTraverse(node.rightNode);
}

- 후위순회

// 후위 순회
void PostorderTraverse(BTreeNode node) {
    if (node == null) {
        return;
    }

    PostorderTraverse(node.leftNode);
    PostorderTraverse(node.rightNode);
    System.out.println(node.data);
}

순회결과

이진트리를 이용한 수식 표현 (수식트리)

부모노드의 자식노드 두 개를 피연산자로 한 후 연산
ex) 7+4*2-1

이진트리를 이용한 수식 구현

중위표기법을 후위표기법으로 변환
중위 표기법을 바로 트리로 구현하기 어려움 (괄호 또는 연산자 우선순위 때문에)

후위표기법을 수식트리로 변환
스택을 이용하여 구현
1) 후위표기법의 앞에서부터 스캔
2) 스캔한 문자가 숫자인 경우 스택에 저장
3) 스캔한 문자가 연산자인 경우 스택에서 두 개를 꺼내 연결한 후 다시 스택에 저장

public BTreeNode createExpTree(String exp){
    String postfixExp = PostfixNotation.convPostfix(exp);
    Stack<BTreeNode> stack = new Stack<>();

    char c = ' ';
    for(int i=0; i<postfixExp.length(); i++){
        node = createBTreeNode();
        c = postfixExp.charAt(i);

        // 숫자면
        if (Character.isDigit(c)){
            setData(node, Character.getNumericValue(c));
        }
        // 숫자가 아니면 (연산자면) 연결
        else {
            setData(node, c);
            createRightSubTree(node, stack.pop());
            createLeftSubTree(node, stack.pop());
        }
        stack.push(node);
    }

    return stack.pop();
}

ex) 중위표기법 1+2+3

후위표기법	스택	결과
12+3+
+3+	2 1
3+
3+
+	3

수식트리 계산
- 재귀로 구현
1) 단말노드까지 왼쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환
2) 단말노드까지 오른쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환
3) 부모노드 값(연산자) 반환
4) 연산자에 맞게 계산 진행
5) 1) ~ 4) 항목 반복

public double calculate(BTreeNode node){
    double op1 = 0;
    double op2 = 0;

    // 단말노드인지 확인
    if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
        // 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
        return Double.valueOf(getData(node).toString());
    }

    // 노드의 왼쪽 피연산자 값 반환
    op1 = calculate(getLeftSubTree(node));
    // 노드의 오른쪽 피연산자 값 반환
    op2 = calculate(getRightSubTree(node));

    // 연산자 확인 후 계산
    switch (String.valueOf(getData(node))){
        case "+":
            return op1+op2;

        case "-":
            return op1-op2;

        case "*":
            return op1*op2;

        case "/":
            return op1/op2;
    }

    return 0;
}

구현

후위표기법으로 변환을 위한 클래스 생성

package Stack;

import Stack.Stack;
import Stack.LinkedList.LinkedListStack;

public class PostfixNotation {
    public static String convPostfix(String infix){
        char c = ' ';
        Stack opStack = new LinkedListStack();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<infix.length(); i++){
            c = infix.charAt(i);

            // 숫자이면 표현
            if (Character.isDigit(c)){
                sb.append(c);
            }
            // 연산자 스택이 비어있을 경우 값 push
            else if (opStack.isEmpty()){
                opStack.push(c);
            }
            // 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
            else {
                // 여는 괄호가 나오면 스택에 저장 후 다음 문자로
                if (c == '('){
                    opStack.push(c);
                    continue;
                }
                // 닫는 괄호가 나올 경우
                // 스택에 저장된 모든 연산자를 반환
                else if (c == ')'){
                    char check = ' ';
                    while(true) {
                        check = (char) opStack.pop();
                        if (check == '(') {
                            break;
                        }
                        else {
                            sb.append(check);
                        }
                    }
                    continue;
                }

                // 현재 연산자의 우선순위가 더 높은 경우
                // 스택에 연산자 저장
                if (compareOp((char)opStack.peek(), c) > 0){
                    opStack.push(c);
                }
                // 현재 연산자의 우선순위가 더 낮거나 같은 경우
                // 스택에 있는 우선순위가 높은 연산자를 빼서 표현
                else {
                    while(!opStack.isEmpty()){
                        if (compareOp((char)opStack.peek(), c) <= 0){
                            sb.append(opStack.pop());
                        }
                        else {
                            break;
                        }
                    }
                    opStack.push(c);
                }
            }
        }

        char check = ' ';
        while(!opStack.isEmpty()) {
            check = (char) opStack.pop();
            if (check != '(') {
                sb.append(check);
            }
        }

        return sb.toString();
    }

    // 연산자 우선순위 반환
    public static int getOpPriority(char c){
        switch (c) {
            case '*':
            case '/':
                return 3;

            case '+':
            case '-':
                return 2;

            case '(':
                return 1;

            default:
                return -1;
        }
    }

    // 연산자 우선순위 비교
    public static int compareOp(char stackOp, char curOp){
        int stackOpPriority = getOpPriority(stackOp);
        int curOpPriority = getOpPriority(curOp);

        // 현재 우선순위가 더 높은 경우
        if (stackOpPriority < curOpPriority){
            return 1;
        }
        // 우선순위가 같은 경우
        else if (stackOpPriority == curOpPriority){
            return 0;
        }
        // 스택의 우선순위가 더 높은 경우
        else {
            return -1;
        }
    }
}

수식트리 구현을 위한 클래스 (BinaryTree 상속)

package BinaryTree.LinkedList;

import java.util.Stack;
import Stack.PostfixNotation;

public class ExpressionTree extends BinaryTree {
    BTreeNode node;

    public BTreeNode createExpTree(String exp){
        String postfixExp = PostfixNotation.convPostfix(exp);
        Stack<BTreeNode> stack = new Stack<>();

        char c = ' ';
        for(int i=0; i<postfixExp.length(); i++){
            node = createBTreeNode();
            c = postfixExp.charAt(i);

            // 숫자면
            if (Character.isDigit(c)){
                setData(node, Character.getNumericValue(c));
            }
            // 숫자가 아니면 (연산자면) 연결
            else {
                setData(node, c);
                createRightSubTree(node, stack.pop());
                createLeftSubTree(node, stack.pop());
            }
            stack.push(node);
        }

        return stack.pop();
    }

    public double calculate(BTreeNode node){
        double op1 = 0;
        double op2 = 0;

        // 단말노드인지 확인
        if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
            // 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
            return Double.valueOf(getData(node).toString());
        }

        // 노드의 왼쪽 피연산자 값 반환
        op1 = calculate(getLeftSubTree(node));
        // 노드의 오른쪽 피연산자 값 반환
        op2 = calculate(getRightSubTree(node));

        // 연산자 확인 후 계산
        switch (String.valueOf(getData(node))){
            case "+":
                return op1+op2;

            case "-":
                return op1-op2;

            case "*":
                return op1*op2;

            case "/":
                return op1/op2;
        }

        return 0;
    }
}

수식트리 테스트 구현

package BinaryTree.LinkedList;

public class ExpressionTreeMain {
    public static void main(String[] args) {
        ExpressionTree expTree = new ExpressionTree();

        BTreeNode expNode = expTree.createExpTree("(1+2)*3");
        System.out.println(expTree.calculate(expNode));
    }
}

결과

[참고] 열혈 자료구조

[전체코드]

'0x00. 자료구조' 카테고리의 다른 글

우선순위 큐(Priority Queue)와 힙 (Heap) (0)	2021.10.27
큐 (Queue) (0)	2021.10.19
스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] (0)	2021.10.18
스택 (Stack) (0)	2021.10.15
양방향 연결 리스트 (이중 연결 리스트) (0)	2021.10.14

큐 (Queue)

2021. 10. 19. 14:49

큐 (Queue)

먼저 들어간 데이터가 먼저 나오는 구조 (선입선출)
(FIFO, First-In, First-Out)
마트에서 계산 대기할 때, 영화관 입장 시 등등
데이터 삽입 시 위치를 알기 위한 Rear 변수 필요
데이터 반환 시 위치를 알기 위한 Front 변수 필요
데이터 삽입과 반환이 이루어지는 위치가 다름
(스택은 동일한 위치에서 pop과 push가 이루어지지만, 큐는 Rear, Front를 통해 위치를 알아내야 함)

추상자료형 (ADT)

자료형	반환값	설명
initialize()	void	큐(Queue) 초기화
isEmpty()	boolean	큐가 비어있는지 확인
enqueue(Data)	void	큐에 데이터 삽입
dequeue()	Data	맨 앞에 있는 데이터 반환 및 삭제
peek()	Data	맨 앞에 있는 데이터 반환 후 삭제하지 않음

배열기반 큐 구현

삽입
삭제
삭제 과정의 문제점
- 아래와 같이 Rear가 배열의 끝까지 이동했지만, 삭제된 공간에는 데이터가 저장되지 않음
- dequeue 시 삭제된 빈 공간을 뒤에 데이터들이 채워줘야하는데, 잦은 데이터의 이동이 발생할 경우 성능에 문제가 생길 수 있어 이를 해결하기 위해 front와 rear의 위치만 변경하도록 해야함
해결방법
- rear와 front가 가리키는 인덱스가 배열의 크기보다 클 경우 front또는 rear값을 0으로 설정하여 배열의 첫번째를 가리킬 수 있도록 함 (원형 큐)

구현
Queue 인터페이스 구현

package Queue;

public interface Queue {
    // 큐(Queue) 초기화
    void initialize();
    // 비어있는지 확인
    boolean isEmpty();
    // 큐에 데이터 삽입
    void enqueue(Object data);
    // 큐의 맨 앞에있는 데이터 반환 후 삭제
    Object dequeue();
    // 큐의 맨 앞에있는 데이터 반환 후 삭제하지 않음
    Object peek();
}

Queue 구현

package Queue.Array;

import Queue.Queue;

public class ArrayQueue implements Queue {
    private final static int QUEUE_SIZE = 5;
    int frontIndex = 0;
    int rearIndex = 0;
    int countOfData = 0;
    Object[] queue = null;

    @Override
    public void initialize() {
        queue = new Object[QUEUE_SIZE];
        frontIndex = 0;
        rearIndex = 0;
        countOfData = 0;
    }

    @Override
    public boolean isEmpty() {
        if (countOfData == 0){
            return true;
        }

        return false;
    }

    @Override
    public void enqueue(Object data) {
        if (countOfData == QUEUE_SIZE){
            System.out.println("더이상 데이터를 추가할 수 없습니다.");
            return;
        }

        // 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 rear를 0으로 초기화
        if (rearIndex == QUEUE_SIZE){
            rearIndex = 0;
        }

        countOfData++;
        queue[rearIndex++] = data;
    }

    @Override
    public Object dequeue() {
        if (countOfData == 0){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        // 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 front를 0으로 초기화
        if (frontIndex == QUEUE_SIZE){
            frontIndex = 0;
        }

        countOfData--;
        return queue[frontIndex++];
    }

    @Override
    public Object peek() {
        if (countOfData == 0){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        return queue[frontIndex];
    }
}

테스트 구현

package Queue.Array;

import Queue.Queue;

public class ArrayQueueMain {
    public static void main(String[] args) {
        Queue queue = new ArrayQueue();
        queue.initialize();

        queue.enqueue(1);queue.enqueue(2);
        queue.enqueue(3);queue.enqueue(4);
        queue.enqueue(5);

        // 데이터 삽입 후 출력
        System.out.println("데이터 삽입 후 출력");
        while(!queue.isEmpty()){
            System.out.println(queue.dequeue());
        }

        System.out.println("데이터 삭제 후 하나 추가 출력 ");
        queue.enqueue(1);queue.enqueue(2);
        queue.enqueue(3);queue.enqueue(4);
        queue.enqueue(5);

        queue.dequeue();
        queue.enqueue(6);

        while(!queue.isEmpty()){
            System.out.println(queue.dequeue());
        }
    }
}

연결 리스트 기반 큐 구현

배열 기반의 큐와 동일하게 front와 rear 변수 필요
삽입 시 첫 번째 노드와 두 번째 이후의 노드 추가 과정이 다름
삽입
삭제
- front로 큐가 비어있는지 판별할 수 있기 때문에 삭제 시 rear는 신경쓰지 않아도 됨

구현

- 인터페이스는 동일하게 구현

LinkedList 큐 구현

package Queue.LinkedList;

import Queue.Queue;

public class LinkedListQueue implements Queue {
    class Node {
        Object data;
        Node nextNode;
    }

    Node front = null;
    Node rear = null;
    int countOfData = 0;

    @Override
    public void initialize() {
        front = null;
        rear = null;
        countOfData = 0;
    }

    @Override
    public boolean isEmpty() {
        if (front == null){
            return true;
        }

        return false;
    }

    @Override
    public void enqueue(Object data) {
        Node newNode = new Node();
        newNode.data = data;

        // 큐가 비어있는 경우 첫 번째 노드 추가
        if (isEmpty()){
            front = newNode;
            rear = newNode;
        }
        // 두 번째 이후의 노드 추가일 경우 rear의 다음 node 주소를 설정 후 rear값 변경
        else {
            rear.nextNode = newNode;
            rear = newNode;
        }

        countOfData++;
    }

    @Override
    public Object dequeue() {
        if (isEmpty()){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        // 제일 앞 쪽 데이터 반환
        Object data = front.data;
        // front의 다음 노드를 front로 변경
        front = front.nextNode;
        return data;
    }

    @Override
    public Object peek() {
        if (isEmpty()){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        return front.data;
    }
}

테스트 구현

package Queue.LinkedList;

import Queue.Queue;

public class LinkedListQueueMain {
    public static void main(String[] args) {
        Queue queue = new LinkedListQueue();
        queue.initialize();

        queue.enqueue(1);queue.enqueue(2);
        queue.enqueue(3);queue.enqueue(4);
        queue.enqueue(5);

        // 데이터 삽입 후 출력
        System.out.println("데이터 삽입 후 출력");
        while(!queue.isEmpty()){
            System.out.println(queue.dequeue());
        }

        System.out.println("데이터 삭제 후 하나 추가 출력 ");
        queue.enqueue(1);queue.enqueue(2);
        queue.enqueue(3);queue.enqueue(4);
        queue.enqueue(5);

        queue.dequeue();
        queue.enqueue(6);

        while(!queue.isEmpty()){
            System.out.println(queue.dequeue());
        }
    }
}

'0x00. 자료구조' 카테고리의 다른 글

우선순위 큐(Priority Queue)와 힙 (Heap) (0)	2021.10.27
[Java] 트리 (Tree)와 이진트리 (Binary Tree) (0)	2021.10.23
스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] (0)	2021.10.18
스택 (Stack) (0)	2021.10.15
양방향 연결 리스트 (이중 연결 리스트) (0)	2021.10.14

스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA]

2021. 10. 18. 20:51

스택을 이용한 후위 표기법 (postfix)

후위 표기법

연산 순서의 정보가 담겨있음
예) 중위 표기법 : 5+2/7
전위 표기법 : +5/27
후위 표기법 : 527/+
위 예시에서 후위 표기법에서 나누기(/) 연산자가 더하기(+) 연산자보다 앞에 있으므로 나누기 연산부터 진행 후 더하기 연산을 한다는 것을 알 수 있음
연산자의 우선순위에 대해 알 필요가 없음
- 연산자의 배치 순서에 따라 연산 순서가 결정됨
- 위 같은 특성 때문에 소괄호에 대한 처리도 불필요함

소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법

예시) 중위표현식 : 5+2/7

숫자는 그대로 표현한다.
연산자는 스택에 저장한다.
스택에 연산자가 있을 경우 우선순위를 비교한다.
3-1. 새로 추가할 연산자의 우선순위가 더 높을 경우 스택에 저장한다.
3-2. 새로 추가할 연산자의 우선순위가 더 낮거나 같을경우 스택에 있는 우선순위가 높은 연산자를 빼서 표현하고,
새로운 연산자는 스택에 저장한다.
위 방법을 반복하며 더 이상 남은 중위 표현식이 없을 경우 스택에 저장된 연산자들을 모두 빼서 표현한다.

중위 표현식	후위 표현식	스택	번호
5+2/7
+2/7	5		방법 1
2/7	5	+	방법 2
/7	52	+	방법 1
7	52	/ +	방법 3-1
	527	/ +	방법 1
	527/+		방법 4

소괄호가 있는 중위 표현식을 후위 표현식으로 변경하는 방법

( ) 연산자는 우선순위가 다른 연산자들 보다 낮다고 가정
- 어디까지 괄호로 묶여 있는 것인지 판단하기 위해 필요
( 연산자 내부의 수직은 ) 연산자를 만날때까지 기존 후위 표기법과 방식이 동일
) 연산자가 나오면 스택에 저장된 모든 연산자를 표현
- ( ) 연산자는 표현하지 않음
1번부터 반복

예시) 중위 표현식 : (1+2*3)/4

중위 표현식	후위 표현식	스택
(1+2*3)/4
1+2*3)/4		(
+2*3)/4	1	(
2*3)/4	1	+ (
*3)/4	12	+ (
3)/4	12	* + (
)/4	123	* + (
/4	123	) * + (
/4	123*+
4	123*+	/
	123*+4	/
	123*+4/

소괄호가 있는 중위표기법을 후위 표기법으로 변경하는 기능 구현

기존에 직접 구현한 LinkedListStack을 이용 (java 내부에서 사용하는 Stack 사용해도 무방)

연산자 우선순위를 반환하는 메소드 작성

// 연산자 우선순위 반환
public static int getOpPriority(char c){
    switch (c) {
        case '*':
        case '/':
            return 3;

        case '+':
        case '-':
            return 2;

        case '(':
            return 1;

        default:
            return -1;
    }
}

연산자 우선순위를 비교하는 메소드 작성

// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
    int stackOpPriority = getOpPriority(stackOp);
    int curOpPriority = getOpPriority(curOp);

    // 현재 우선순위가 더 높은 경우
    if (stackOpPriority < curOpPriority){
        return 1;
    }
    // 우선순위가 같은 경우
    else if (stackOpPriority == curOpPriority){
        return 0;
    }
    // 스택의 우선순위가 더 높은 경우
    else {
        return -1;
    }
}

후위 표기법으로 변경하는 메소드 작성

public static String convPostfix(String infix){
    char c = ' ';
    Stack opStack = new LinkedListStack();
    StringBuilder sb = new StringBuilder();

    for(int i=0; i<infix.length(); i++){
        c = infix.charAt(i);

        // 숫자이면 표현
        if (Character.isDigit(c)){
            sb.append(c);
        }
        // 연산자 스택이 비어있을 경우 값 push
        else if (opStack.isEmpty()){
            opStack.push(c);
        }
        // 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
        else {
            // 여는 괄호가 나오면 스택에 저장 후 다음 문자로
            if (c == '('){
                opStack.push(c);
                continue;
            }
            // 닫는 괄호가 나올 경우
            // 스택에 저장된 모든 연산자를 반환
            else if (c == ')'){
                char check = ' ';
                while(true) {
                    check = (char) opStack.pop();
                    if (check == '(') {
                        break;
                    }
                    else {
                        sb.append(check);
                    }
                }
                continue;
            }

            // 현재 연산자의 우선순위가 더 높은 경우
            // 스택에 연산자 저장
            if (compareOp((char)opStack.peek(), c) > 0){
                opStack.push(c);
            }
            // 현재 연산자의 우선순위가 더 낮거나 같은 경우
            // 스택에 있는 우선순위가 높은 연산자를 빼서 표현
            else {
                while(!opStack.isEmpty()){
                    if (compareOp((char)opStack.peek(), c) <= 0){
                        sb.append(opStack.pop());
                    }
                    else {
                        break;
                    }
                }
                opStack.push(c);
            }
        }
    }

    char check = ' ';
    while(!opStack.isEmpty()) {
        check = (char) opStack.pop();
        if (check != '(') {
            sb.append(check);
        }
    }

    return sb.toString();
}

후위 표기법 계산

public static double postfixCalculate(String postfix){
    Stack stack = new LinkedListStack();
    char c = ' ';
    double op1 = 0;
    double op2 = 0;
    
    for(int i=0; i<postfix.length(); i++){
        c = postfix.charAt(i);

        // 숫자인 경우 스택에 저장
        if (Character.isDigit(c)){
            stack.push(c);
        }
        // 연산자인 경우 계산 후 스택에 저장
        else {
            op2 = Double.valueOf(stack.pop().toString());
            op1 = Double.valueOf(stack.pop().toString());

            switch (c){
                // op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
                // ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
                // 데이터가 가장 위에 있으므로
                case '+':
                    stack.push(op1 + op2);
                    break;

                case '-':
                    stack.push(op1 - op2);
                    break;

                case '*':
                    stack.push(op1 * op2);
                    break;

                case '/':
                    stack.push(op1 / op2);
                    break;
            }
        }
    }

    return Double.valueOf(stack.pop().toString());
}

전체 소스코드

package Stack;

import Stack.Stack;
import Stack.LinkedList.LinkedListStack;

public class PostfixNotation {
    public static void main(String[] args) {
        String infix = "(1+2*3)/4";
        String postfix = convPostfix(infix);
        System.out.println(postfix);
        System.out.println(postfixCalculate(postfix));
    }

    public static double postfixCalculate(String postfix){
        Stack stack = new LinkedListStack();
        char c = ' ';
        double op1 = 0;
        double op2 = 0;

        for(int i=0; i<postfix.length(); i++){
            c = postfix.charAt(i);

            // 숫자인 경우 스택에 저장
            if (Character.isDigit(c)){
                stack.push(c);
            }
            // 연산자인 경우 계산 후 스택에 저장
            else {
                op2 = Double.valueOf(stack.pop().toString());
                op1 = Double.valueOf(stack.pop().toString());

                switch (c){
                    // op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
                    // ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
                    // 데이터가 가장 위에 있으므로
                    case '+':
                        stack.push(op1 + op2);
                        break;

                    case '-':
                        stack.push(op1 - op2);
                        break;

                    case '*':
                        stack.push(op1 * op2);
                        break;

                    case '/':
                        stack.push(op1 / op2);
                        break;
                }
            }
        }

        return Double.valueOf(stack.pop().toString());
    }

    public static String convPostfix(String infix){
        char c = ' ';
        Stack opStack = new LinkedListStack();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<infix.length(); i++){
            c = infix.charAt(i);

            // 숫자이면 표현
            if (Character.isDigit(c)){
                sb.append(c);
            }
            // 연산자 스택이 비어있을 경우 값 push
            else if (opStack.isEmpty()){
                opStack.push(c);
            }
            // 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
            else {
                // 여는 괄호가 나오면 스택에 저장 후 다음 문자로
                if (c == '('){
                    opStack.push(c);
                    continue;
                }
                // 닫는 괄호가 나올 경우
                // 스택에 저장된 모든 연산자를 반환
                else if (c == ')'){
                    char check = ' ';
                    while(true) {
                        check = (char) opStack.pop();
                        if (check == '(') {
                            break;
                        }
                        else {
                            sb.append(check);
                        }
                    }
                    continue;
                }

                // 현재 연산자의 우선순위가 더 높은 경우
                // 스택에 연산자 저장
                if (compareOp((char)opStack.peek(), c) > 0){
                    opStack.push(c);
                }
                // 현재 연산자의 우선순위가 더 낮거나 같은 경우
                // 스택에 있는 우선순위가 높은 연산자를 빼서 표현
                else {
                    while(!opStack.isEmpty()){
                        if (compareOp((char)opStack.peek(), c) <= 0){
                            sb.append(opStack.pop());
                        }
                        else {
                            break;
                        }
                    }
                    opStack.push(c);
                }
            }
        }

        char check = ' ';
        while(!opStack.isEmpty()) {
            check = (char) opStack.pop();
            if (check != '(') {
                sb.append(check);
            }
        }

        return sb.toString();
    }

    // 연산자 우선순위 반환
    public static int getOpPriority(char c){
        switch (c) {
            case '*':
            case '/':
                return 3;

            case '+':
            case '-':
                return 2;

            case '(':
                return 1;

            default:
                return -1;
        }
    }

    // 연산자 우선순위 비교
    public static int compareOp(char stackOp, char curOp){
        int stackOpPriority = getOpPriority(stackOp);
        int curOpPriority = getOpPriority(curOp);

        // 현재 우선순위가 더 높은 경우
        if (stackOpPriority < curOpPriority){
            return 1;
        }
        // 우선순위가 같은 경우
        else if (stackOpPriority == curOpPriority){
            return 0;
        }
        // 스택의 우선순위가 더 높은 경우
        else {
            return -1;
        }
    }
}

결과
전위 표기법 : (1+2*3)/4
전위 표기법 : ((4+2)/4)-(3+2/(7*5))
2자리 이상의 숫자를 연산하려면 List와 StringBuilder로 구현 가능
StringBuilder를 이용해 문자가 나올 때까지 반복하고, 연산자가 나올 경우 숫자를 리스트에 저장하는 방식으로 구현 가능

'0x00. 자료구조' 카테고리의 다른 글

[Java] 트리 (Tree)와 이진트리 (Binary Tree) (0)	2021.10.23
큐 (Queue) (0)	2021.10.19
스택 (Stack) (0)	2021.10.15
양방향 연결 리스트 (이중 연결 리스트) (0)	2021.10.14
단순 연결 리스트 (0)	2021.10.11

스택 (Stack)

2021. 10. 15. 11:08

스택 (Stack)

선형 자료구조
프링글스처럼 한 쪽은 막혀있고 다른 한 쪽으로 과자를 꺼내거나 넣는 것
후입선출 (Last-In, First-Out, LIFO) 구조
마지막에 삽입한 것이 먼저 나오는 구조
배열 또는 리스트로 구현 가능

추상 자료형 (ADT)

자료형	반환값	내용
initialize()	void	스택 초기화
push(Data)	void	스택에 데이터 삽입
pop()	Data	데이터 반환 후 삭제
peek()	Data	데이터 반환 후 삭제하지 않음
isEmpty()	boolean	스택이 비어있는지 확인

배열로 스택 구현

배열의 크기를 고정해야 함
스택에서 가장 마지막에 삽입된 위치를 저장하는 변수가 필요 (topIndex)

구현

디렉토리 구조

ArrayStack.java

package Stack.Array;

import Stack.Stack;

public class ArrayStack implements Stack {
    // 스택 배열의 최대 크기
    final private int MAX_SIZE = 10;
    // 가장 마지막에 삽입된 데이터의 위치
    int topIndex = -1;
    // 스택 설정
    Object[] stack = new Object[MAX_SIZE];

    @Override
    public void initialize() {
        // 배열을 null로 초기화
        for(int i=0; i<MAX_SIZE; i++) {
            stack[i] = null;
        }
        // -1 => 아무것도 삽입되지 않음
        topIndex = -1;
    }

    @Override
    public void push(Object data) {
        if (topIndex == MAX_SIZE - 1){
            System.out.println("더이상 공간이 없습니다.");
            return;
        }

        // 데이터 삽입
        stack[++topIndex] = data;
    }

    @Override
    public Object pop() {
        if (isEmpty()){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        // 데이터 반환 후 삭제
        return stack[topIndex--];
    }

    @Override
    public Object peek() {
        if (isEmpty()){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        return stack[topIndex];
    }

    @Override
    public boolean isEmpty() {
        if (topIndex == -1){
            return true;
        }

        return false;
    }
}

ArrayStackMain.java

package Stack.Array;
import Stack.Stack;

public class ArrayStackMain {
    public static void main(String[] args) {
        Stack stack = new ArrayStack();
        stack.initialize();

        stack.push(1); stack.push(2);
        stack.push(3); stack.push(4);
        stack.push(5); stack.push(6);

        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

리스트로 스택 구현

머리에 데이터를 삽입하는 연결 리스트와 동일

구현

디렉토리 구조

LinkedListStack.java

package Stack.LinkedList;
import Stack.Stack;

public class LinkedListStack implements Stack {

    public class Node {
        Object data;
        Node nextNode;
    }

    Node head = null;

    @Override
    public void initialize() {
        head = null;
    }

    @Override
    public void push(Object data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = head;
        head = newNode;
    }

    @Override
    public Object pop() {
        if (isEmpty()){
            System.out.println("데이터가 없습니다.");
            return null;
        }

        Object rData = head.data;
        head = head.nextNode;

        return rData;
    }

    @Override
    public Object peek() {
        if (isEmpty()) {
            System.out.println("데이터가 없습니다.");
            return null;
        }

        return head.data;
    }

    @Override
    public boolean isEmpty() {
        if (head == null){
            return true;
        }

        return false;
    }
}

LinkedListStackMain.java

package Stack.LinkedList;

import Stack.Array.ArrayStack;
import Stack.Stack;

public class LinkedListStackMain {
    public static void main(String[] args) {
        Stack stack = new LinkedListStack();
        stack.initialize();

        stack.push(1); stack.push(2);
        stack.push(3); stack.push(4);
        stack.push(5); stack.push(6);

        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

'0x00. 자료구조' 카테고리의 다른 글

큐 (Queue) (0)	2021.10.19
스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] (0)	2021.10.18
양방향 연결 리스트 (이중 연결 리스트) (0)	2021.10.14
단순 연결 리스트 (0)	2021.10.11
순차 리스트 (0)	2021.10.06

양방향 연결 리스트 (이중 연결 리스트)

2021. 10. 14. 13:01

양방향 연결 리스트 (이중 연결 리스트)

양방향 연결 리스트

이중 연결 리스트라고도 함
노드가 양쪽 방향으로 연결된 구조
구조
기본 연결 리스트에서 이전 노드를 가리키는 prev 변수 필요
- 기존에 구현한 연결 리스트에서는 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 사로 연결해주기 위해 앞에서부터 탐색하여 이전 노드를 찾음 (첫번째부터 탐색을 진행하기 때문에 데이터가 많아질수록 부하가 발생)
- 양방향 연결 리스트의 경우 이전 노드를 바로 알 수 있기 때문에 성능상 이점이 있음

추상 자료형

자료형	반환값	내용
initialize()	void	리스트 초기화
insert(Data)	boolean	리스트에 데이터 삽입
first()	Data	첫번째 데이터를 가리키도록 함 (Dummy 노드를 추가한 경우 반환값을 받을 필요 없으나, 기본 연결 리스트 구현 시에는 필요하기 때문에 반환값을 Data로 주었음)
next()	Data	현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 해당 값을 반환
remove()	Data	현재 참조하고 있는 데이터를 삭제
count()	int	리스트에 있는 데이터의 총 개수

리스트 초기화
- 헤드가 더미를 가리키게 함

    public void initialize() {
        head = new Node();
        cur = head;
        countOfData = 0;
    }

데이터 추가
- 2와 4를 추가했을 때의 상태

    public boolean insert(Object data) {
        try {
            Node newNode = new Node();
            newNode.data = data;

            // 헤드의 nextNode가 null이 아닐 경우
            // 즉, 데이터가 하나라도 추가된 경우를 뜻함
            if (head.nextNode != null) {
                head.nextNode.prevNode = newNode;
            }

            // 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
            newNode.nextNode = head.nextNode;
            // 새로운 노드의 이전 노드는 머리를 가리켜야 함
            newNode.prevNode = head;
            // 헤드의 다음 노드는 새로운 노드를 가리킴
            head.nextNode = newNode;

            countOfData++;
            return true;
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            return false;
        }
    }

데이터 삭제
- 4를 삭제했을 경우
- 삭제할 노드의 이전 노드의 다음 노드가 가리키는 값을 삭제할 노드의 다음 노드 값으로 변경
- 삭제할 노드의 다음 노드의 이전 노드가 가리키는 값을 삭제할 노드의 이전 노드 값으로 변경

    public Object remove() {
        if (countOfData == 0){
            System.out.println("삭제할 노드가 없습니다.");
            return null;
        }

        Node rNode = cur;

        // 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
        cur.prevNode.nextNode = cur.nextNode;
        if (cur.nextNode != null) {
            cur.nextNode.prevNode = cur.prevNode;
        }

        countOfData--;
        return rNode;
    }

데이터 조회
- first 호출 시

- next 호출 시

구현

디렉토리 구조

인터페이스 구현
- 기존 순차 리스트 인터페이스와 동일

package List;

// 다형성을 위해 List를 인터페이스로 생성
public interface List {
    // 리스트 초기화
    void initialize();
    // 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
    boolean insert(Object data);
    // 첫 번째 데이터를 가리키도록 하며 값을 반환
    Object first();
    // 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
    Object next();
    // 현재 참조하고 있는 데이터를 지움
    Object remove();
    // 리스트에 저장된 데이터의 개수를 반환
    int count();
}

양방향 연결 리스트 구현

package List.LinkedList.Double;

import List.List;

public class DoublyLinkedList implements List {
    public class Node {
        public Object data;
        public Node prevNode;
        public Node nextNode;
    }

    Node head = null;
    Node cur = null;
    int countOfData = 0;

    @Override
    public void initialize() {
        head = new Node();
        cur = head;
        countOfData = 0;
    }

    @Override
    public boolean insert(Object data) {
        try {
            Node newNode = new Node();
            newNode.data = data;

            // 헤드의 nextNode가 null이 아닐 경우
            // 즉, 데이터가 하나라도 추가된 경우를 뜻함
            if (head.nextNode != null) {
                head.nextNode.prevNode = newNode;
            }

            // 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
            newNode.nextNode = head.nextNode;
            // 새로운 노드의 이전 노드는 머리를 가리켜야 함
            newNode.prevNode = head;
            // 헤드의 다음 노드는 새로운 노드를 가리킴
            head.nextNode = newNode;

            countOfData++;
            return true;
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            return false;
        }
    }

    @Override
    public Object first() {
        // 현재 위치를 가지고 있는 cur 변수를 head로 설정 (맨 처음 위치로)
        cur = head;
        return cur;
    }

    @Override
    public Object next() {
        // 현재 가리키고 있는 노드의 다음 노드가 null인 경우 마지막 노드로 판단
        if (cur.nextNode == null){
            System.out.println("마지막 노드입니다.");
            return null;
        }

        // 현재 가리키고 있는 노드의 다음 노드로 설정
        cur = cur.nextNode;
        return cur.data;
    }

    @Override
    public Object remove() {
        if (countOfData == 0){
            System.out.println("삭제할 노드가 없습니다.");
            return null;
        }

        Node rNode = cur;

        // 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
        cur.prevNode.nextNode = cur.nextNode;
        if (cur.nextNode != null) {
            cur.nextNode.prevNode = cur.prevNode;
        }

        countOfData--;
        return rNode;
    }

    @Override
    public int count() {
        return countOfData;
    }
}

메인 구현
- 데이터 추가/삭제/조회 기능 테스트

package List.LinkedList.Double;

public class DoublyLinkedListMain {
    public static void main(String[] args) {
        DoublyLinkedList linkedList = new DoublyLinkedList();

        // 리스트 초기화
        linkedList.initialize();

        // 리스트에 데이터 삽입
        linkedList.insert(1); linkedList.insert(2);
        linkedList.insert(3); linkedList.insert(4);
        linkedList.insert(5); linkedList.insert(6);

        // 첫번째 노드로 설정
        Object data = null;
        linkedList.first();
        // data가 null이 될 때까지 반복
        while((data = linkedList.next()) != null) {
            System.out.println(data);
        }

        // 데이터 삭제
        Object remove = null;
        linkedList.first();
        while((data = linkedList.next()) != null){
            if ((int)data == 1){
                remove = linkedList.remove();
                System.out.println((int)data + "가 삭제되었습니다.");
                remove = null;
            }
        }

        // 첫번째 노드로 설정
        linkedList.first();
        // data가 null이 될 때까지 반복
        while((data = linkedList.next()) != null) {
            System.out.println(data);
        }
    }
}

결과

'0x00. 자료구조' 카테고리의 다른 글

스택을 이용한 후위 표기법 및 계산기 (postfix) [JAVA] (0)	2021.10.18
스택 (Stack) (0)	2021.10.15
단순 연결 리스트 (0)	2021.10.11
순차 리스트 (0)	2021.10.06
재귀(Recursion)란? (1)	2021.05.08

PREV 이전 1 2 3 4 5 NEXT 다음

전체 글

선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택 정렬 방법

성능

구현

'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글

버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

버블 정렬 방법 (오름차순 기준)

버블 정렬의 성능

기본 구현

클래스 비교를 위한 구현

'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글

우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐 (Priority Queue)

힙의 구현 (최대 힙 기준) 방법

힙 구현

결과

'0x00. 자료구조' 카테고리의 다른 글

트리 (Tree)

트리 (Tree)

용어 정리

노드와의 관계

이진트리 (Binary Tree)와 서브트리 (Sub Tree)

서브트리 (Sub Tree)

이진트리 (Binary Tree)

포화 이진트리 (Full Binary Tree)와 완전 이진트리 (Complete Binary Tree)

연결리스트 기반 이진트리

연결리스트 기반 이진트리 구현

이진트리의 순회

이진트리를 이용한 수식 표현 (수식트리)

이진트리를 이용한 수식 표현 (수식트리)

이진트리를 이용한 수식 구현

구현

'0x00. 자료구조' 카테고리의 다른 글

큐 (Queue)

큐 (Queue)

추상자료형 (ADT)

배열기반 큐 구현

연결 리스트 기반 큐 구현

구현

'0x00. 자료구조' 카테고리의 다른 글

스택을 이용한 후위 표기법 (postfix)

후위 표기법

소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법

소괄호가 있는 중위 표현식을 후위 표현식으로 변경하는 방법

소괄호가 있는 중위표기법을 후위 표기법으로 변경하는 기능 구현

'0x00. 자료구조' 카테고리의 다른 글

스택 (Stack)

스택 (Stack)

추상 자료형 (ADT)

배열로 스택 구현

리스트로 스택 구현

'0x00. 자료구조' 카테고리의 다른 글

양방향 연결 리스트 (이중 연결 리스트)

양방향 연결 리스트

구현

결과

'0x00. 자료구조' 카테고리의 다른 글

티스토리툴바