10_연결 리스트(Linked List)

- 선형 리스트: 데이터를 순서대로 나열해 놓은 자료구조 

- 스택과 큐도 리스트 구조로 되어 있다.

- 연결 리스트를 구현하기 위한 노드의 구조

class Node<E> {
    E data;		// 데이터
    Node<E> next;	// 다음 노드를 가리키는 포인터
}

└→ 필드 data형인 E는 참조형이다. 

       클래스형 변수인 data는 데이터 그 자체가 아니라 데이터에 대한 '참조' !

 

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

public class LinkedList<E> {
    // 노드
    class Node<E> {
        private E data;         // 데이터
        private Node<E> next;   // 다음 노드를 가리키는 포인터

        // 생성자
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<E> head = null;    // 머리 노드 (머리 노드에 대한 참조! 머리 노드 그 자체 아님!)
    private Node<E> crnt = null;    // 현재 선택한 노드 (검색/삭제 등의 용도로 사용)

    // 생성자
    public LinkedList() {
        head = crnt = null;
    }

    // 노드 검색
    public E search(E obj, Comparator<? super E> c) {
        Node<E> node = head;

        while (node != null) {
            // 검색 성공
            if (c.compare(obj, node.data) == 0) {
                crnt = node;
                return node.data;
            }
            // 다음 노드 대입
            node = node.next;
        }
        // 검색 실패
        return null;
    }

    // 머리에 노드 삽입
    public void addFirst(E obj) {
        Node<E> node = head;
        // head에 새로운 노드 넣어주고, next에 기존 head 넣어줌
        head = crnt = new Node<E>(obj, node);
    }

    // 꼬리에 노드 삽입
    public void addLast(E obj) {
        if (head == null)
            addFirst(obj);
        else {
            Node<E> node = head;
            while (node.next != null)
                node = node.next;
            //-- while문 종료 시, node는 꼬리 노드를 가리킴
            node.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> node = head;
                Node<E> nodePrev = head;
                while (node.next != null) {
                    nodePrev = node;
                    node = node.next;
                }
                //-- while문 종료 시, node는 꼬리 노드를, nodePrev는 꼬리 노드의 앞 노드를 가리킴
                nodePrev.next = null;
                crnt = nodePrev;
            }
        }
    }
    
    // 노드 p를 삭제
    public void remove(Node p) {
        if (head != null) {
            if (p == head)
                removeFirst();
            else {
                Node<E> node = head;
                while (node.next != p) {
                    node = node.next;
                    if (node == null)   return;     // p가 리스트에 없음
                }
                node.next = p.next;
                crnt = node;
            }
        }
    }
    
    // 선택 노드(crnt)를 삭제
    public void removeCurrentNode() {
        remove(crnt);
    }
    
    // 모든 노드를 삭제
    public void clear() {
        // 노드에 아무것도 없을 때까지 머리노드를 삭제
        while (head != null)
            removeFirst();
        crnt = null;
    }
    
    // 선택 노드(crnt)를 하나 뒤의 노드로 이동
    public boolean next() {
        if (crnt == null || crnt.next == null)
            return false;
        crnt = crnt.next;
        return true;
    }
    
    // 선택 노드(crnt)를 출력
    public void printCurrentNode() {
        if (crnt == null)
            System.out.println("선택 노드 없음");
        else
            System.out.println(crnt.data);
    }
    
    // 모든 노드를 출력
    public void dump() {
        Node<E> node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
}

 

• 커서로 연결 리스트 만들기

- 커서(cursor): pointer 역할하는 배열의 index

- 노드 삽입/삭제 시 요소 옮길 필요 없음

- 데이터 수가 크게 바뀌지 않고, 데이터 수의 최댓값 미리 알 수 있을 때 사용

 

• 원형 리스트(circular list)

- 리스트의 꼬리 노드의 next가 머리 노드를 가리켜 고리 모양으로 나열

 

• 원형 이중 연결 리스트 (=양방향 리스트, doubly linked list)

-  다음 노드를 가리키는 next와 이전 노드를 가리키는 prev가 있음

- head의 이전 노드 → tail

  tail의 다음 노드 → head

public class DblLinkedList<E> {
    class Node<E> {
        private E data;
        private Node<E> prev;
        private Node<E> next;

        Node() {
            data = null;
            prev = next = null;
        }

        Node(E obj, Node<E> prev, Node<E> next) {
            data = obj;
            this.prev = prev;
            this.next = next;
        }
    }

    private Node<E> head;    // 머리 노드(더미 노드)
    //--> 노드의 삽입/삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 더미 노드
    private Node<E> crnt;

    public DblLinkedList() {
        head = crnt = new Node<E>();    // 더미 노드를 생성
    }

    // 리스트가 비어 있는가?
    public boolean isEmpty() {
        return head.next == head;
    }

    // 노드를 검색
    public E search(E obj, Comparator<? super E> c) {
        Node<E> ptr = head.next;    // 현재 스캔 중인 노드
        //-- 실질적은 머리노드는 더미 노드의 다음 노드이므로 검색 시작 → head.next 부터!

        while (ptr != head) {
            if (c.compare(obj, ptr.data) == 0) {
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;
        }
        return null;
    }

    // 선택 노드를 출력
    public void printCurrentNode() {
        if (isEmpty())
            System.out.println("선택 노드 없음");
        else
            System.out.println(crnt.data);
    }

    // 모든 노드 출력
    public void dump() {
        Node<E> ptr = head.next;    // 더미 노드의 다음 노드 (실질적 머리노드)

        // ptr이 더미노드가 아닐 때 까지 반복
        while (ptr != head) {
            System.out.print(ptr.data + " ");
            ptr = ptr.next;
        }
        System.out.println();
    }

    // 모든 노드를 거꾸로 출력
    public void dumpReverse() {
        Node<E> ptr = head.prev;    // 더미 노드의 앞쪽 노드

        while (ptr != head) {
            System.out.print(ptr.data + " ");
            ptr = ptr.prev;
        }
        System.out.println();
    }

    // 선택 노드를 하나 뒤로 이동
    public boolean next() {
        if (isEmpty() || crnt.next == head)
            return false;
        crnt = crnt.next;
        return true;
    }

    // 선택 노드를 하나 앞으로 이동
    public boolean prev() {
        if (isEmpty() || crnt.prev == head)
            return false;
        crnt = crnt.prev;
        return true;
    }
    
    // 선택 노드의 바로 뒤에 노드 삽입
    public void add(E obj) {
        Node<E> node = new Node<E>(obj, crnt, crnt.next);
        crnt.next = crnt.next.prev = node;
        crnt = node;
    }
    
    // 머리에 노드 삽입
    public void addFirst(E obj) {
        crnt = head;
        add(obj);
    }
    
    // 꼬리에 노드 삽입
    public void addLast(E obj) {
        crnt = head.prev;
        add(obj);
    }
    
    // 선택 노드 삭제
    public void removeCurrentNode() {
        if (!isEmpty()) {
            crnt.prev.next = crnt.next;
            crnt.next.prev = crnt.prev;
            crnt = crnt.prev;
            if (crnt == head) crnt = head.next;
        }
    }
    
    // 노드 p를 삭제
    public void remove(Node p) {
        Node<E> ptr = head.next;
        
        while (ptr != head) {
            if (ptr == p) {
                crnt = p;
                removeCurrentNode();
                break;
            }
            ptr = ptr.next;
        }
    }
    
    // 머리 노드 삭제
    public void removeFirst() {
        crnt = head.next;
        removeCurrentNode();
    }
    
    // 꼬리 노드 삭제
    public void removeLast() {
        crnt = head.prev;
        removeCurrentNode();
    }
    
    // 모든 노드 삭제
    public void clear() {
        while (!isEmpty())
            removeFirst();
    }
}