[자료구조] Java 리스트(List)

리스트란?

연속적인 자료의 형태를 리스트라고 한다.

선형 리스트, 원형 리스트, 이중 연결 리스트 3가지 종류가 있다.

원형 리스트와 이중 연결 리스트를 합쳐진 형태로 원형 이중 연결리스트도 있다.

 

종류와 별개로 구현방법을 기준으로 배열, 포인터, 커서를 이용하는 방식으로 나눌 수 있다.

배열은 기초적인 내용이니 생략하며, 포인터로 구현한 연결리스트는 다음과 같다.

//연결 리스트 클래스
public class LinkedList<E> {
 
    //노드
    class Node<E> {
        private E data;            //데이터
        private Node<E> next;    //뒤쪽 포인터(다음 노드에 대한 참조)
        
        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }
    
    private Node<E> head;        //머리 노드
    private Node<E> crnt;        //선택 노드
    
    public LinkedList() {
        head = crnt = null;
    }
    
    //노드 검색
    public E search(E obj, Comparator<? super E> c) {
        Node<E> ptr = head;            //현재 스캔 중인 노드
        
        while (ptr != null) {
            if (c.compare(obj, ptr.data) == 0) {
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;            //다음 노드를 선택
        }
        return null;                //검색 실패
    }
    
    //머리에 노드 삽입
    public void addFirst(E obj) {
        Node<E> ptr = head;            //삽입 전의 머리 노드
        head = crnt = new Node<E>(obj, ptr);
    }
    
    //꼬리에 노드 삽입
    public void addLast(E obj) {
        if (head == null) {        //리스트가 비어 있으면
            addFirst(obj);        //머리에 삽입하는 것과 같음
        } else {
            Node<E> ptr = head;
            while (ptr.next != null) { //꼬리 노드가 나올 때까지 반복
                ptr = ptr.next;
            }
            ptr.next = crnt = new Node<E>(obj, null);
        }
    }
    
    //머리 노드 삭제
    public void removeFirst() {
        if (head != null) {        //리스트가 비어 있지 않은 경우에만
            head = crnt = head.next;
        }
    }
    
    //꼬리 노드 삭제
    public void removeLast() {
        if (head != null) {
            if (head.next == null) {    //노드가 하나만 있으면
                removeFirst();          //머리 노드를 삭제하는 것과 같음
            } else {
                Node<E> ptr = head;        //스캔 중인 노드
                Node<E> pre = head;        //스캔 중인 노드의 앞쪽 노드
                
                while (ptr.next != null) {
                    pre = ptr;
                    ptr = ptr.next;
                }
                
                pre.next = null;        //삭제 후의 꼬리 노드
                crnt = pre;
            }
        }
    }
    
    //노드 p를 삭제
    public void remove(Node p) {
        if (head != null) {
            if (p == head) {        //p가 머리 노드면
                removeFirst();        
            } else {
                Node<E> ptr = head;        //p의 앞쪽 노드
                
                while (ptr.next != p) {
                    ptr = ptr.next;
                    if (ptr == null) return;    //p가 리스트에 없음
                }
                ptr.next = p.next;
                crnt = ptr;
            }
        }
    }
    
    //현재 선택한 노드 삭제
    public void removeCurrentNode() {
        remove(crnt);
    }
    
    //모든 노드를 삭제
    public void clear() {
        while (head != null) {        //노드에 아무것도 없을 때까지
            removeFirst();            //머리 노드를 삭제
        }
        crnt = null;
    }
    
    //선택 노드를 하나 뒤쪽으로 이동
    public boolean next() {
        if (crnt == null || crnt.next == null) {
            return false;
        }
        crnt = crnt.next;
        return true;
    }
    
    //선택 노드를 출력
    public void printCurrentNode() {
        if (crnt == null) {
            System.out.println("선택한 노드가 없습니다.");
        } else {
            System.out.println(crnt.data);
        }
    }
    
    //모든 노드를 출력
    public void dump() {
        Node<E> ptr = head;
        
        while (ptr != null) {
            System.out.println(ptr.data);
            ptr = ptr.next;
        }
    }
    
    //comparator c에 의해 서로 같다고 보는 노드를 모두 삭제
    public void purge(Comparator<? super E> c) {
        Node<E> ptr = head;
        
        while (ptr != null) {
            int count = 0;
            Node<E> ptr2 = ptr;
            Node<E> pre = ptr;
            
            while (pre.next != null) {
                ptr2 = pre.next;
                if (c.compare(ptr.data, ptr2.data) == 0) {
                    pre.next = ptr2.next;
                    count++;
                } else {
                    pre = ptr2;
                }
            }
            if (count == 0) {
                pre = ptr.next;
            } else {
                Node<E> temp = ptr;
                remove(ptr);
                ptr = temp.next;
            }
        }
        crnt = head;
    }
    
    //머리부터 n개 뒤 노드의 데이터에 대한 참조를 반환
    public E retrieve(int n) {
        Node<E> ptr = head;
        
        while (n >= 0 && ptr != null) {
            if (n-- == 0) {
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;
        }
        return null;
    }
}

 

 

커서를 이용한 연결 리스트

포인터를 이용한 방법은 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'라는 특징이 있다.

하지만 삽입, 삭제를 할때마다 노드용 객체를 메모리 영역에 만들고 해체하는 과정이 필요하다.

그 과정에서 소모되는 비용을 아끼면 효율적인 연결리스트를 운용할 수 있는데,

그 방법이 커서를 사용하는 방법이다.

커서란 인덱스를 뜻하며,

노드에서 노드를 직접 가르키는게 아닌 다음 노드의 인덱스만을 갖고 있는다.

커서를 이용한 연결리스트는 다음과 같다.

+ 그림자료 : kururu.tistory.com/64?category=801433

//연결 리스트 클래스(배열 커서 버전)
 
public class AryLinkedList<E> {
 
    //노드
    class Node<E> {
        private E data;           //데이터
        private int next;         //뒤쪽 포인터(다음 노드)
        private int dnext;        //프리 리스트의 뒤쪽 포인터(프리 리스트의 다음 노드)
        //프리 리스트 : 삭제된 레코드를 관리하기 위한 연결 리스트
        
        void set(E data, int next) {
            this.data = data;
            this.dnext = next;
        }
    }
    
    private Node<E>[] n;                    //리스트 본체
    private int size;                       //리스트의 용량(가장 큰 데이터 수)
    private int max;                        //배열의 가장 꼬리 쪽에 있는 노드의 레코드 번호(사용 중인 꼬리 레코드)
    private int head;                       //머리 노드
    private int crnt;                       //선택 노드
    private int deleted;                    //프리 리스트의 머리 노드
    private static final int NULL = -1;     //다음 노드 없음 / 리스트가 가득 참
    
    
    public AryLinkedList(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;
        }
    }
    
    //노드를 삽입할 때 사용할 인덱스를 반환
    public int getInsertIndex() {
        if (deleted == NULL) {        //삭제된 레코드가 없어 프리 리스트가 비어 있음
            if (max < size) {
                return ++max;        //max를 증가시켜 아직 사용하지 않은 배열 꼬리 쪽 인덱스를 반환
            } else {
                return NULL;        //용량 넘침
            }
        } else {
            int rec = deleted;            //프리 리스트에서
            deleted = n[rec].dnext;        //머리 레코드를 꺼냄
            return rec;
        }
    }
    
    //삭제한 레코드를 프리 리스트에 등록
    public void deleteIndex(int idx) {
        if (deleted == NULL) {        //프리 리스트가 비어 있음
            deleted = idx;
            n[idx].dnext = NULL;
        } else {
            int rec = deleted;        //idx를 프리 리스트의
            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;
            }
        }
    }
    
    //레코드 p를 삭제
    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;    //리스트에 p가 없음
                }
                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;
        }
    }
    
    //comparator c에 의해 서로 같다고 보는 노드를 모두 삭제
    public void purge(Comparator<? super E> c) {
        int ptr = head;
 
        while (ptr != NULL) {
            int count = 0;
            int ptr2 = ptr;
            int pre = ptr;
 
            while (n[pre].next != NULL) {
                ptr2 = n[pre].next;
                if (c.compare(n[ptr].data, n[ptr2].data) == 0) {
                    remove(ptr2);
                    count++;
                } else {
                    pre = ptr2;
                }
            }
            if (count == 0) {
                ptr = n[ptr].next;
            } else {
                int temp = n[ptr].next;
                remove(ptr);
                ptr = temp;
            }
        }
        crnt = head;
    }
    
    //머리부터 n개 뒤 노드의 데이터에 대한 참조를 반환
    public E retrieve(int n) {
        int ptr = head;
 
        while (n >= 0 && ptr != NULL) {
            if (n-- == 0) {
                crnt = ptr;
                return this.n[ptr].data; // 검색성공
            }
            ptr = this.n[ptr].next; // 뒤쪽노드에 주목
        }
        return null;
    }
}

 

 

++ 코드 출처 : higugu.tistory.com/entry/%ED%8F%AC%EC%9D%B8%ED%84%B0%EB%A1%9C-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EB%A7%8C%EB%93%A4%EA%B8%B0?category=706109

포인터로 연결 리스트 만들기

프리 리스트란?

커서로 구현한 연결리스트에서 삭제한 여러 레코드들을 관리하기 위해

사용하는 또 하나의 연결리스트이다.

삭제한 요소를 스택처럼 쌓아놓고 데이터를 삽입할 때, 

마지막에 삭제된 인덱스에 요소를 삽입한다.

 

원형 리스트

선형 리스트의 마지막 노드가 첫번째의 노드를 가르키고 있는 리스트를 뜻한다.

선형리스트보다 삽입, 삭제가 편리하며 

헤드가 마지막 노드를 가르키고 있는것이 특징이다.

 

이중 연결 리스트

이중 연결 리스트는 노드가 양방향으로 선행 노드와 다음 노드를 동시에 가르킨다.

위의 리스트보다 탐색이 용이하며, 

삽입, 삭제가 조금 더 복잡한 편이다.

 

원형 이중 연결 리스트

마지막 노드가 첫번째의 노드를 가르키며 서로가 서로를 가르키는 리스트이다.