알고리즘 (배열 커서 연결 리스트)

이번 알고리즘은 저번 리스트에 이어서 각 노드를 배열 안의 요소에 저장하고 그 요소를 이용해 연결 리스트를 구현하는 방식으로 해보자.

 

이전 알고리즘 리스트 구현에서 장점은 노드의 삽입, 삭제를 데이터 이동 없이 수행한다라는 장점이 있지만 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 확보하고 해제하는 과정이 필요하다. 메모리 영역을 확보하고 해제하는데 필요한 비용은 사용할수록 점점 커져갈 것이다. 데이터 수가 크게 바뀌지 않거나 데이터의 최대 개수를 미리 알 수 있다면 배열을 통해 연결 리스트를 구성하는 것이 효율적인 운용이 가능하다.

다음 예제를 통해서 어떻게 효율적인지 알아보자.

 

위는 논리적인 구조를 이미지로 나타낸 것이다.

아래는 물리적인 구조를 나타내는 이미지이다.

 

다음 노드가 가리키는 뒤쪽 포인터는 다음 노드에 대한 포인터가 아닌 다음 노드가 들어 있는 배열 요소의 인덱스이다. 이 인덱스 포인트를 커서라 한다. 노드 B의 커서 3은 B의 다음 노드 C가 인덱스 3인 위치에 저장되어 있음을 의미한다. 

 

 

위처럼 꼬리 노드의 커서는 배열의 인덱스가 될 수 없는 값인 -1로 한다. 머리 노드를 나타내는 head도 커서이기 때문에 머리 노드 A가 들어있는 곳인 인덱스 1이 head 값이 된다. 

 

package list;

import java.util.Comparator;

public class ArrayLinkedList<E> {

    class Node<E> {
        private E data;
        private int next; //리스트의 뒤쪽 포인터
        private int dnext; //프리 리스트의 뒤쪽 포인터
    void set(E data, int next) {
        this.data = data;
        this.next = next;
        } 
    }
    
    private Node<E>[] n; //리스트 본체
    private int size; //리스트의 용량(가장 큰 데이터 수)
    private int max; //사용 중인 꼬리 record
    private int head; //머리 노드
    private int crnt; //선택 노드
    private int deleted; //프리 리스트의 머리 노드
    private static final int NULL = -1; //다음 노드 없음 / 리스트가 가득 참
    
    public ArrayLinkedList(int capacity) {
        head = crnt = max = deleted = NULL;
        try {
            n = new Node[capacity];
            for (int i = 0; i < capacity; i++) {
                n[i] = new Node<E>();
            }
            size = capacity;
        } catch (OutOfMemoryError e) {
            size = 0;
        }
    }
    
    private int getInsertIndex() {
        if (deleted == NULL) {
            if (max < size) {
                return ++max;
            } else {
                return NULL;
            }
        } else {
            int rec = deleted;
            deleted = n[rec].dnext;
            return rec;
        } 
    }
    
    private void deleteIndex(int idx) {
        if (deleted == NULL) {
            deleted = idx;
            n[idx].dnext = NULL;
        } else {
            int rec = deleted;
            deleted = idx;
            n[idx].dnext = rec;
        } 
    }
    
    public E search(E obj, Comparator<? super E> c) {
        int ptr = head;

        while (ptr != NULL) {
            if (c.compare(obj, n[ptr].data) == 0) {
                crnt = ptr;
                return n[ptr].data;
            }
            ptr = n[ptr].next;
        }
        return null;
    }
    
    
    public void addFirst(E obj) {
        int ptr = head;
        int rec = getInsertIndex();
        if (rec != NULL) {
            head = crnt = rec;
            n[head].set(obj, ptr);
        }
    }
    
    public void addLast(E obj) {
        if (head == NULL) {
            addFirst(obj);
        } else {
            int ptr = head;
            while (n[ptr].next != NULL) {
                ptr = n[ptr].next;
            }
            int rec = getInsertIndex();
            if (rec != NULL) {
                n[ptr].next = crnt = rec;
                n[rec].set(obj, NULL);
            }
        } 
    }
    
    public void removeFirst() {
        if (head != NULL) {
            int ptr = n[head].next;
            deleteIndex(head);
            head = crnt = ptr;
        }
    }
    
    public void removeLast() {
        if (head != NULL) {
            if (n[head].next == NULL) {
                removeFirst();
            } else {
                int ptr = head;
                int pre = head;

                while (n[ptr].next != NULL) {
                    pre = ptr;
                    ptr = n[ptr].next;
                }
                n[pre].next = NULL;
                deleteIndex(ptr);
                crnt = pre;
            } 
        }
    }
    
    
    public void remove(int p) {
        if (head != NULL) {
            if (p == head) {
                removeFirst();
            } else {
                int ptr = head;

                while (n[ptr].next != p) {
                    ptr = n[ptr].next;
                    if (ptr == NULL) return;
                }
                n[ptr].next = NULL;
                deleteIndex(p);
                n[ptr].next = n[p].next;
                crnt = ptr;
            }
        }
    }
    
    public void removeCurrentNode() {
        remove(crnt);
    }
    
    public void clear() {
        while (head != NULL) {
            removeFirst();
        }
        crnt = NULL;
    }
    
    public boolean next() {
        if (crnt == NULL || n[crnt].next == NULL) {
            return false;
        }
        crnt = n[crnt].next;
        return true;
    }
    
    public void printCurrentNode() {
        if (crnt == NULL) {
            System.out.println("선택한 노드가 없습니다.");
        } else {
            System.out.println(n[crnt].data);
        } 
    }
    public void dump() {
        int ptr = head;

        while (ptr != NULL) {
            System.out.println(n[ptr].data);
            ptr = n[ptr].next;
        }
    }
}

 

이 클래스를 활용해 배열 커서로 연결 리스트를 사용하는 프로그램을 만들어 보도록 하겠다.

package list;

import java.util.Comparator;
import java.util.Scanner;

public class ArrayLinkedListTester {
    static Scanner sc = new Scanner(System.in);

    //--- 데이터(회원번호＋이름) ---//
    static class Data {
        static final int NO   = 1;        // 번호를 읽어 들일까요?
        static final int NAME = 2;        // 이름을 읽어 들일까요?

        private Integer no;                // 회원번호
        private String  name;              // 이름


        public String toString() {
            return "(" + no + ") " + name;
        }


        void scanData(String guide, int sw) {
            System.out.println(guide + "할 데이터를 입력하세요.");

            if ((sw & NO) == NO) {
                System.out.print("번호: ");
                no = sc.nextInt();
            }
            if ((sw & NAME) == NAME) {
                System.out.print("이름: ");
                name = sc.next();
            }
        }


        public static final Comparator<Data> NO_ORDER =
                new NoOrderComparator();

        private static class NoOrderComparator implements Comparator<Data> {
            public int compare(Data d1, Data d2) {
                return (d1.no > d2.no) ? 1 : (d1.no < d2.no) ? -1 : 0;
            }
        }


        public static final Comparator<Data> NAME_ORDER =
                new NameOrderComparator();

        private static class NameOrderComparator implements Comparator<Data> {
            public int compare(Data d1, Data d2) {
                return d1.name.compareTo(d2.name);
            }
        }
    }


    enum Menu {
        ADD_FIRST(  "머리 노드 삽입"),
        ADD_LAST(   "꼬리 노드 삽입"),
        RMV_FIRST(  "머리 노드 삭제"),
        RMV_LAST(   "꼬리 노드 삭제"),
        RMV_CRNT(   "선택 노드 삭제"),
        CLEAR(      "전체 노드 삭제"),
        SEARCH_NO(  "번호 검색"),
        SEARCH_NAME("이름 검색"),
        NEXT(       "선택 노드 진행"),
        PRINT_CRNT( "선택 노드 표시"),
        DUMP(       "전체 노드 표시"),
        TERMINATE(  "종료");

        private final String message;

        static Menu MenuAt(int idx) {
            for (Menu m : Menu.values())
                if (m.ordinal() == idx)
                    return m;
            return null;
        }

        Menu(String string) {                        // 생성자(constructor)
            message = string;
        }

        String getMessage() {                        // 표시할 문자열을 반환
            return message;
        }
    }


    static Menu SelectMenu() {
        int key;
        do {
            for (Menu m : Menu.values()) {
                System.out.printf("(%d) %s  ", m.ordinal(), m.getMessage());
                if ((m.ordinal() % 3) == 2 &&
                        m.ordinal() != Menu.TERMINATE.ordinal())
                    System.out.println();
            }
            System.out.print(" : ");
            key = sc.nextInt();
        } while (key < Menu.ADD_FIRST.ordinal() ||
                key > Menu.TERMINATE.ordinal());
        return Menu.MenuAt(key);
    }

    public static void main(String[] args) {
        Menu menu;
        Data data;
        Data ptr;
        Data temp = new Data();

        ArrayLinkedList<Data> list = new ArrayLinkedList<Data>(100);

        do {
            switch (menu = SelectMenu()) {

                case ADD_FIRST :
                    data = new Data();
                    data.scanData("머리에 삽입", Data.NO | Data.NAME);
                    list.addFirst(data);
                    break;

                case ADD_LAST :
                    data = new Data();
                    data.scanData("꼬리에 삽입", Data.NO | Data.NAME);
                    list.addLast(data);
                    break;

                case RMV_FIRST :
                    list.removeFirst();
                    break;

                case RMV_LAST :
                    list.removeLast();
                    break;

                case RMV_CRNT :
                    list.removeCurrentNode();
                    break;

                case SEARCH_NO :
                    temp.scanData("검색", Data.NO);
                    ptr = list.search(temp, Data.NO_ORDER);
                    if (ptr == null)
                        System.out.println("그 번호의 데이터가 없습니다.");
                    else
                        System.out.println("검색 성공 : " + ptr);
                    break;

                case SEARCH_NAME :
                    temp.scanData("검색", Data.NAME);
                    ptr = list.search(temp, Data.NAME_ORDER);
                    if (ptr == null)
                        System.out.println("그 이름의 데이터가 없습니다.");
                    else
                        System.out.println("검색 성공 : " + ptr);
                    break;

                case NEXT :
                    list.next();
                    break;

                case PRINT_CRNT :
                    list.printCurrentNode();
                    break;

                case DUMP :
                    list.dump();
                    break;

                case CLEAR :                                 
                    list.clear();
                    break;
            }
        } while (menu != Menu.TERMINATE);
    }
}

 

이전 리스트 알고리즘과 같이 테스트 해도 결과는 잘 나온다.

이와 같이 배열 커서를 활용해서 리스트를 만들어 보았다.