[자료구조] 8. 연결리스트 큐(LinkedList Queue) 구현

Queue (Using LinkedList)

7. 배열 큐(Array Queue) 와는 다르게 LinkedList를 기반으로 구현한다. 기본적으로 LinkedList에 대한 이해가 필요하다.

 

자바에서는 대중적으로 LinkedList로 구현한 큐를 많이 사용한다. 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고 있기 때문에 요소가 들어있는 배열의 용량에 따라 resize()를 해주어야 하고 선형 큐로 구현한 경우 요소들이 뒤로 쏠리는 문제가 있기 때문에 이러한 문제를 효율적으로 극복하고자 원형으로 구현하는데 이 구현이 고려해야 할 점도 많고 복잡하다.

 

배열 대신 연결리스트로 구현할 경우 많은 단점들이 해결된다. 각 데이터들을 노드 객체에 담고 노드 간 서로 연결하기 때문에 배열처럼 요소 개수에 따라 늘리거나 줄일 필요도 없고 삽입, 삭제에도 용이하다.

 

먼저 연결리스트의 기본 구조와 삽입, 삭제에 대한 그림을 다시 보고 큐를 구현해보자.

 

노드 객체 구조

 

offer() 메소드를 통해 데이터를 추가하면 다음과 같다.

 

poll() 메소드를 통해 데이터를 삭제하면 다음과 같다.

 

 

위와 같은 방식으로 큐를 구현한다. 이러한 큐를 보통 Linked Queue, LinkedList - Queue 라고 불린다. 연결형 큐, 연결리스트 큐라고 한다. 

 

---

Node 구현

public class Node<E> {

    E data;
    Node<E> next;

    Node(E data) {
        this.data = data;
        this.next = null;
    }
}

---

LinkedList Queue 구현

<필수 목록>

• 클래스 및 생성자 구성
• offer()
• poll()
• peek()
• size, isEmpty, contains, clear

<부가 목록>

• toArray, clone, sort

---

Queue 클래스 및 생성자 구성

public class LinkedListQueue<E> implements QueueInterface<E> {
    
    private Node<E> head;
    private Node<E> tail;
    private int size;
    
    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

 

head : 큐에서 가장 앞에 있는 노드 객체

tail : 큐에서 가장 뒤에 있는 노드 객체

size : 큐에 담긴 요소 개수

---

offer()

큐는 기본적으로 맨 뒤에 데이터를 추가해야 한다. 리스트로 치면 add(E value)와 같은 역할이다.

 

1. 기본 삽입 : offer(E item)

 

@Override
public boolean offer(E value) {
    Node<E> newNode = new Node<>(value);

    // 비어있을 경우
    if (size == 0) {
        head = newNode;
    } else {
        tail.next = newNode;        // 그 외의 경우 마지막 노드의 다음 노드 변수가 새노드를 가리키도록한다.
    }

    /**
     * tail을 새 노드로 변경
     */
    tail = newNode;
    size++;

    return true;
}

 

size 가 0일때는 새 요소가 head이자 tail이다. 큐가 비어있을 때는 head를 새 노드를 가리키도록 하고 그 외에는 요소가 이미 있다는 의미이므로 tail.next가 가리키는 요소를 새 노드를 가리키도록 하고 tail을 새 노드로 업데이트한다.

 

---

poll()

remove()는 삭제할 요소가 없다면 NoSuchElementException() 예외를 던지지만 poll()은 null을 반환한다.

 

 

1. poll()

 

@Override
public E poll() {

    if (size == 0) {
        return null;
    }

    // 삭제할 요소의 데이터와 다음 노드 정보를 담는다
    E element = head.data;
    Node<E> nextNode = head.next;

    head.data = null;
    head.next = null;

    // head 가 가리키는 노드를 삭제된 head 노드의 다음노드를 가리키도록 변경
    head = nextNode;
    size--;

    return element;
}

 

2. remove()

 

public E remove() {

    E element = poll();

    if (element == null) {
        throw new NoSuchElementException();
    }

    return element;
}

 

---

peek() 

poll()은 데이터를 삭제하고 요소를 반환하지만 peek()은 삭제하지 않고 반환한다. 유일한 차이점은 이것이다.

큐에 데이터가 없는 경우는 null을 반환한다. peek과 유사한 element는 remove와 마찬가지로 NoSuchElementException을 발생시킨다.

 

1. peek()

 

@Override
public E peek() {

    if (size == 0) {
        return null;
    }

    return head.data;
}

 

 

 

2. element()

 

public E element() {

    E element = peek();

    if (element == null) {
        throw new NoSuchElementException();
    }

    return element;
}

---

1. size() 

 

public int size() {
    return size;
}

 

 

2. isEmpty()

 

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

 

 

3. contains()

 

public boolean contains(Object value) {
    for(Node<E> x = head; x != null; x = x.next) {
        if (value.equals(x.data)) {
            return true;
        }
    }
    return false;
}

 

 

4. clear()

 

public void clear() {
    for(Node<E> x = head; x != null; x = x.next) {

        Node<E> next = x.next;
        x.data = null;
        x.next = null;
        x = next;
    }

    size = 0;
    head = tail = null;
}

---

<부가 목록>

 

2. Singly LinkedList 참조

 

 

---

전체 코드

public class LinkedListQueue<E> implements QueueInterface<E>, Cloneable {

    private Node<E> head;
    private Node<E> tail;
    private int size;

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    @Override
    public boolean offer(E value) {
        Node<E> newNode = new Node<>(value);

        // 비어있을 경우
        if (size == 0) {
            head = newNode;
        } else {
            tail.next = newNode;        // 그 외의 경우 마지막 노드의 다음 노드 변수가 새노드를 가리키도록한다.
        }

        /**
         * tail을 새 노드로 변경
         */
        tail = newNode;
        size++;

        return true;
    }

    @Override
    public E poll() {

        if (size == 0) {
            return null;
        }

        // 삭제할 요소의 데이터와 다음 노드 정보를 담는다
        E element = head.data;
        Node<E> nextNode = head.next;

        head.data = null;
        head.next = null;

        // head 가 가리키는 노드를 삭제된 head 노드의 다음노드를 가리키도록 변경
        head = nextNode;
        size--;

        return element;
    }

    public E remove() {

        E element = poll();

        if (element == null) {
            throw new NoSuchElementException();
        }

        return element;
    }

    @Override
    public E peek() {

        if (size == 0) {
            return null;
        }

        return head.data;
    }

    public E element() {

        E element = peek();

        if (element == null) {
            throw new NoSuchElementException();
        }

        return element;
    }

    public int size() {
        return size;
    }

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

    public boolean contains(Object value) {
        for(Node<E> x = head; x != null; x = x.next) {
            if (value.equals(x.data)) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        for(Node<E> x = head; x != null; x = x.next) {

            Node<E> next = x.next;
            x.data = null;
            x.next = null;
            x = next;
        }

        size = 0;
        head = tail = null;
    }

    @Override
    public Object clone() throws CloneNotSupportedException {

        @SuppressWarnings("unchecked")
        LinkedListQueue<? super E> clone = (LinkedListQueue<? super E>) super.clone();

        clone.head = null;
        clone.tail = null;
        clone.size = 0;

        for (Node<E> x = head; x != null; x = x.next) {
            clone.offer(x.data);
        }

        return clone;
    }

    public Object[] toArray() {
        Object[] array = new Object[size];
        int idx = 0;
        for (Node<E> x = head; x != null; x = x.next){
            array[idx++] = (E) x.data;
        }

        return array;
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            // Arrays.newInstance(컴포넌트 타입, 생성할 크기)
            a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
        }
        int i = 0;
        Object[] result = a;
        for (Node<E> x = head; x != null; x = x.next) {
            result[i++] = x.data;
        }

        return a;
    }

    public void sort() {
        /**
         * Comparator 를 넘겨주지 않는 경우 해당 객체의 Comparable 에 구현된 정렬 방식을 사용한다.
         * 만약 구현되어 있지 않다면 cannot be cast to class java.lang.Comparable 에러가 발생.
         * 만약 구현되어 있다면 null 로 파라미터를 넘기면
         * Arrays.sort() 가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
         */
        sort(null);
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    public void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);

        int i = 0;
        for (Node<E> x = head; x != null; x = x.next, i++) {
            x.data = (E) a[i];
        }

    }
}

 

 

LinkedListQueue에 대한 기본적인 메소드와 추가 메소드를 구현했다. 다음에 구현할 것은 Deque이다. 흔히 '덱'이라고 부르는데 Double Ended Queue의 줄임말이다. 단일 연결리스트와 이중 연결리스트가 있듯, 큐도 단방향 큐와 양방향 큐가 있는데 양방향 큐를 덱이라고 부른다.