[자료구조] 11. 연결리스트 덱(LinkedList Deque)

연결리스트 덱 (LinkedList Deque)

배열 덱 다음으로 다루려고 했던 내용이었는데 힙을 급하게 정리해봐야 할 필요가 있어서 힙 다음 순서로 연결리스트 덱을 다루게 됐다.

기본적으로 양방향 연결리스트, 더블 링크드리스트의 개념을 그대로 사용한다. 배열 덱에서와 마찬가지로 구조를 다시한번 짚고 넘어가자.

 

 

배열과 다르게 연결리스트를 사용하기 때문에 index로 관리되는 것이 아니라 node 단위로 구성된 객체를 서로 연결하여 구성되어 있다. 양방향 연결리스트를 바탕으로 구현될 것이기 때문에 구조를 다시 한번 보자.

 

노드는 노드의 데이터, 이전 노드, 다음 노드를 가리키는 변수들을 갖고 있다. 또한 구조는 offer는 기본적으로 offerLast 즉, 마지막에 더해지며 첫번째에 삽입할 수 있는 offerFirst 메소드가 있다. poll은 기본적으로 pollFirst 즉, 첫번째에 더해지며 마지막에서 삭제할 수 있는 pollLast가 있다. 

 

이를 바탕으로 LinkedList Deque을 구현해보자.

 

---

Node 구현

public class Node<E> {
    
    E date;
    Node<E> next;
    Node<E> prev;

    public Node(E date, Node<E> next, Node<E> prev) {
        this.date = date;
        this.next = null;
        this.prev = null;
    }
}

 

<필수 목록>

• 클래스 및 생성자 구성
• offer 계열 메소드
• poll 계열 메소드
• peek 계열 메소드
• size, isEmpty, contains, clear 메소드

 

<부가 목록>

• toArray, clone, sort 메소드

 

---

Deque 클래스 및 생성자

LinkedList를 기반으로 구현되므로, 앞선 QueueInterface를 implements 할 것이다.

 

public class LinkedListDeque<E> implements QueueInterface<E> {
    
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public LinkedListDeque(Node<E> head, Node<E> tail, int size) {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

---

offer 메소드 구현

1. 전방 삽입 : offerFirst(E item)

 

 

삽입은 위와 같은 과정으로 이루어진다. 양방향 연결리스트와 동일하다.

 

public boolean offerFirst(E value) {
    Node<E> newNode = new Node<>(value);
    newNode.next = head;

    if (head != null) {
        head.prev = newNode;
    }

    head = newNode;
    size++;

    if (head.next == null) {
        tail = head;
    }

    return true;
}

 

새 노드를 offerFirst 하여 연결할때 주의해야 하는 것은 연결될 head의 null 여부이다. head가 null인데 head.prev를 참조하려 하면 NullPointerException이 발생하기 때문이다. 따라서 head가 null 이 아닐때만 head.prev를 새 노드로 업데이트 한다. 그 이후엔 새로운 head로 newNode를 대입하고 사이즈를 늘린다. 그 다음 head.next가 Null이면 요소가 현재 새 노드, 즉 head 하나만 덱에 있다는 뜻으로 tail을 newNode로 업데이트 한다.

 

 

2. 후방 삽입 : offer(E item), offerLast(E item)

 

 

offerFirst 는 head 변수를 통해 데이터를 추가했다면, 이번엔 tail 변수를 활용하면 된다. 여기서는 데이터가 없을 때의 구현은 offerFirst를 활용하면 된다.

 

@Override
public boolean offer(E item) {
    return offerLast(item);
}

public boolean offerLast(E item) {
    if (size == 0) {
        return offerFirst(item);
    }

    Node<E> newNode = new Node<>(item);

    tail.next = newNode;
    newNode.prev = tail;
    tail = newNode;
    size++;

    return true;
}

 

---

poll 메소드 구현

 

1. 전방 삭제 : poll(), pollFirst(), remove(), removeFirst()

먼저 pollFirst()를 먼저 구현한 뒤 poll 메소드 안에서 pollFirst를 호출하는 방식으로 구현한다. remove, removeFirst는 예외처리가 필요하다. pollFirst의 값을 받아와서 해당 값이 null이면 예외를 던져주는 식으로 구현한다.

 

@Override
public E poll() {
    return pollFirst();
}

public E pollFirst() {
    if (size == 0) {
        return null;
    }

    E element = head.data;

    Node<E> nextNode = head.next;

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

    if (nextNode != null) {
        nextNode.prev = null;
    }
    head = null;
    head = nextNode;
    size--;

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

    return element;
}

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    E element = poll();

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

    return element;
}

 

2. 후방 삭제 : pollLast()

 

후방 삭제 덕에 offer와 pollLast를 잘 사용하면 덱을 스택으로도 사용이 가능하다.

 

offerFirst 처럼 요소가 없을 경우, 즉 사이즈가 0일 경우를 고려해야한다.

 

 

@Override
public E poll() {
    return pollFirst();
}

public E pollFirst() {
    if (size == 0) {
        return null;
    }

    E element = head.data;

    Node<E> nextNode = head.next;

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

    if (nextNode != null) {
        nextNode.prev = null;
    }
    head = null;
    head = nextNode;
    size--;

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

    return element;
}

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    E element = poll();

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

    return element;
}

 

 

---

peek 계열 메소드

 

1. peek, peekFirst 메소드

 

@Override
public E peek() {
    return peekFirst();
}

public E peekFirst() {
    if (size == 0) {
        return null;
    }

    return head.data;
}

 

2. peekLast 메소드

 

public E peekLast() {
    if (size == 0) {
        return null;
    } 

    return tail.data;
}

 

3. element, getFirst 메소드

 

public E element() {
    return getFirst();
}

public E getFirst() {
    E item = peek();

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

    return item;
}

 

4. getLast 메소드

 

public E getLast() {
    E item = peekLast();

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

    return item;
}

 

---

size, isEmpty, contains, clear 메소드

 

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;) {
        Node<E> next = x.next;

        x.data = null;
        x.prev = null;
        x.next = null;
        x = next;
    }

    size = 0;
    head = tail = null;
}

 

<부가 목록> 

toArray, sort, clone 메소드 는 Doubly LinkedList 와 동일하다. 이 포스트의 전체 코드에서도 확인할 수 있다.

 

---

전체 코드

 

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

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

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

    public boolean offerFirst(E value) {
        Node<E> newNode = new Node<>(value);
        newNode.next = head;

        if (head != null) {
            head.prev = newNode;
        }

        head = newNode;
        size++;

        if (head.next == null) {
            tail = head;
        }

        return true;
    }

    @Override
    public boolean offer(E item) {
        return offerLast(item);
    }

    public boolean offerLast(E item) {
        if (size == 0) {
            return offerFirst(item);
        }

        Node<E> newNode = new Node<>(item);

        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
        size++;

        return true;
    }

    @Override
    public E poll() {
        return pollFirst();
    }

    public E pollFirst() {
        if (size == 0) {
            return null;
        }

        E element = head.data;

        Node<E> nextNode = head.next;

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

        if (nextNode != null) {
            nextNode.prev = null;
        }
        head = null;
        head = nextNode;
        size--;

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

        return element;
    }

    public E remove() {
        return removeFirst();
    }

    public E removeFirst() {
        E element = poll();

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

        return element;
    }

    public E pollLast() {
        if (size == 0) {
            return null;
        }

        E element = tail.data;

        Node<E> prevNode = tail.prev;

        tail.data = null;
        tail.prev = null;

        if (prevNode != null) {
            prevNode.next = null;
        }

        tail = null;
        tail = prevNode;
        size--;

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

        return element;
    }

    public E removeLast() {
        E element = pollLast();

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

        return element;
    }

    @Override
    public E peek() {
        return peekFirst();
    }

    public E peekFirst() {
        if (size == 0) {
            return null;
        }

        return head.data;
    }

    public E peekLast() {
        if (size == 0) {
            return null;
        }

        return tail.data;
    }

    public E element() {
        return getFirst();
    }

    public E getFirst() {
        E item = peek();

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

        return item;
    }

    public E getLast() {
        E item = peekLast();

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

        return item;
    }

    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;) {
            Node<E> next = x.next;

            x.data = null;
            x.prev = null;
            x.next = null;
            x = next;
        }

        size = 0;
        head = tail = null;
    }

    @Override
    public Object clone() throws CloneNotSupportedException {

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

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

        for (Node<E> x = head; x != null; x = x.next) {
            clone.offerLast(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];
        }

    }
}

 

 

덱은 앞뒤로 모두 접근이 가능하여 필요에 따라 큐, 스택처럼 사용할 수 있다는 것이 장점이다. 기본적으로 배열로 구현하는 경우는 배열 큐를, 연결리스트로 구현할 경우는 LinkedList 구조를 그대로 상속하여 사용한다.