자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기
자료구조 관련 목록 링크 펼치기
- Deque (using LinkedList)
만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글과 큐 인터페이스 (Queue Interface)을 먼저 보고 오셨으면 한다. (필자가 앞서 언급했지만, Queue 인터페이스를 만들어 두고 이를 implements 하여 구체적으로 구현하고자 한다고 했다. 그러니 꼭 Queue 인터페이스 글도 읽어오시길 바란다.)
또한 추가로 단순히 int형식에 한정한 구현이 아닌 제네릭을 사용하여 구현을 할 것이라 최소한의 제네릭에 대한 이해를 필요로 하니 필요하다면 다음 글도 읽어오는 것을 추천드린다.
제네릭에 대한 이해
그리고 '반드시' Doubly LinkedList 구현 글을 읽고 오시길 바란다.
오늘 구현할 연결리스트를 사용하는 덱는 기본적으로 양방향(이중) 연결리스트에 대한 개념을 그대로 갖고오기 때문에 꼭 읽어보시길 바란다.
특히, 연결리스트 삽입, 삭제는 사용자마다 동작 방식이 조금씩 다르기 때문에 그냥 덱 구현 부분을 글로 보면 이해가 어려울 수도 있다. 필자가 구현한 방식을 먼저 이해하고 보는 것이 읽는데 훨씬 이해하기 편할 것이다.
그럼 본격적으로 Deque(덱)에 대해 알아보고 구현하고자 한다. (배열로 덱을 구현했을 때도 설명했지만 다시 한 번 짚고 넘어가볼 것이다.)
왜 Deque(덱)일까? Deque는 Double-ended queue의 줄임말이다.
여기서 오해가 있을 수도 있는데 카드게임에서 말하는 덱은 Deck이다. 다만 발음은 같다. 여튼 Queue(큐)를 구현해봤으면 알겠지만, 큐는 단방향 자료구조다. 단방향 연결리스트(Singly LinkedList)와 유사한 메커니즘이다.
반대로 Deque는 양방향 연결리스트(Doubly LinkedList)와 유사한 메커니즘이다. 앞서 말한 double-ended, 두 개의 종료 지점이 있다는 것. 한 마디로 단 방향으로 삽입 삭제가 이루어 진 것에서 양 쪽 방향으로 삽입 삭제가 이루어 질 수 있도록 구현 한 것이 Deque다.
양방향 큐. 즉 덱의 장점이라 하면 스택처럼 사용할 수도 있고 큐 처럼 사용할 수도 있는 자료구조다.
아무래도 Deque의 경우 양 방향이다보니 메소드들이 헷갈릴 수 있는데 다음 큐와 비교한 그림을 보면서 덱의 구조와 기본적인 메소드의 매칭을 잘 알아두도록 하자. 그리고 다시 한 번 말하지만 필자가 포스팅한 Doubly LinkedList(이중 연결리스트) 글을 보고 오시길 바란다.
보다시피 Deque는 삽입, 삭제가 총 12개가 있다.
offer 계열과 poll 계열의 경우 삽입과 삭제 과정에서 저장공간이 넘치거나 삭제 할 원소가 없을 때 특정 값(null, false 등..)을 반환하지만, add 계열과 remove 계열의 경우 예외를 던진다.
또한 offer(add)은 offerLast(addLast)와 같고, poll(remove)은 pollFirst(removeFirst)와 같다.
정리하자면 우리가 삽입 삭제에서 구현해야 할 것은 크게 4가지다. (add계열은 이 번 구현에서 최대 용적을 제한하지 않을 것이기 때문에 빼고 offer 계열만 구현한다.)
offerLast, offerFirst, pollFirst, pollLast 만 정확하게 구현하면 된다.
그 외에 peek(element) 의 경우도 peek(element)은 peekFirst와 같으며, peekLast은 따로 존재한다. 아래 표를 참고하시면 된다.
그럼 배열로 구현한 Deque와는 어떤 차이점이 있을까?
일단 연결리스트는 index로 관리하는 것이 아닌 node 단위로 구성 된 객체를 서로 연결하여 구성되어있다. 그리고 여기서 큐는 단방향이었기에 단일(단방향) 연결리스트를 썼지만, 이중 연결리스트는 양방향으로 접근 가능한 큐인 만큼 구현의 토대가 되는 연결리스트 또한 양방향(이중) 연결리스트가 토대가 된다.
먼저 단일 연결리스트의 노드와 이중 연결리스트의 노드의 차이를 그림으로 보자면 아래와 같다.
덱은 양방향으로 접근이 가능해야 하기에 당연 이중 연결리스트의 노드를 써야한다.
이 노드들을 연결한 형태를 덱 형태로 보자면 이럴 것이다.
위와같이 양 각 노드들은 양 옆의 노드를 서로 참조를 하고 있다. 즉 이중 연결리스트랑 구조가 같다. (사실 당연한 것이 리스트를 활용하여 특정 기능의 활용을 크게 분류하여 만들어 진 것중 하나기 때문에..)
그렇다보니 기본적으로 ArrayDeque와 메소드가 구현해야 하는 메소드는 같기 때문에 전반적인 내용 자체는 ArrayDeque의 내용과 거의 일치하며, 다만 구현에 따른 방식은 연결리스트와 거의 같기 때문에 구현에서는 Doubly LinkedList와 내용이 거의 일치 할 것이다. (혹시나 무성의해 보일까봐..)
- Node 구현
가장 먼저 구현해놓아야 할 것은 바로 연결리스트에 필요한 노드다. 이 때 Node 클래스는 앞으로 구현 할 LinkedListDeque와 같은 패키지에 생성할 것이다. 만약 다른 패키지에 생성하면 LinkedListDeque 구현 할 때 'import Node클래스가 있는 패키지 경로.Node;' 를 해주면 된다.
class Node<E> { E data; // 데이터를 담을 변수 Node<E> next; // 다음 노드를 가리키는 변수 Node<E> prev; // 이전 노드를 가리키는 변수 Node(E data) { this.data = data; this.prev = null; this.next = null; } }- LinkedList Deque 구현
- 사전 준비
[Queue Interface 소스]
더보기
[Queue.java]
package Interface_form; /** * * 자바 Queue Interface입니다. <br> * Queue는 ArrayQueue, LinkedListQueue, * ArrayDeque, LinkedListDeque, PriorityQueue 에 의해 구현됩니다. * * @author st_lab * @param <E> the type of elements in this Que * * @version 1.0 * */ public interface Queue<E> { /** * 큐의 가장 마지막에 요소를 추가합니다. * * @param e 큐에 추가할 요소 * @return 큐에 요소가 정상적으로 추가되었을 경우 true를 반환 */ boolean offer(E e); /** * 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환합니다. * * @return 큐의 삭제 된 요소 반환 */ E poll(); /** * 큐의 첫 번째 요소를 반환합니다. * * @return 큐의 첫 번째 요소 반환 */ E peek(); }[구현 바로가기]
<필수 목록>
◦ 클래스 및 생성자 구성
◦ offer 계열 메소드 구현
◦ poll 계열 메소드 구현
◦ peek 계열 메소드 구현
◦ size, isEmpty, contains ,clear 메소드 구현
<부가 목록>
◦ toArray, clone, sort 구현
◦ 전체 코드
[Deque 클래스 및 생성자 구성하기]
이 번에 구현 할 덱은 LinkedList를 기반으로 구현되므로, LinkedListDeque 라는 이름으로 생성한다. 그리고 앞선 Queue Interface 포스팅에서 작성했던 Queue 인터페이스를 implements 해준다. (필자의 경우 인터페이스는 Interface_form 이라는 패키지에 생성해두었다.)
implements 를 하면 class 옆에 경고표시가 뜰 텐데 인터페이스에 있는 메소드들을 구현하라는 것이다. 어차피 모두 구현해나갈 것이기 때문에 일단은 무시한다.
[LinkedListDeque.java]
import Interface_form.Queue; public class LinkedListDeque<E> implements Queue<E> { private Node<E> head; // 가장 앞에 있는 노드를 가리키는 변수 private Node<E> tail; // 가장 뒤에 있는 노드를 가리키는 변수 private int size; // 요소(노드)의 개수 public LinkedListDeque() { head = null; tail = null; size = 0; } }변수부터 먼저 차례대로 설명해주도록 하겠다.
head : 가장 앞에 있는 요소(노드)를 가리키는 변수다. 큐에서의 front와 같은 의미다.
tail : 가장 뒤에 있는 요소(노드)를 가리키는 변수다. 큐에서의 rear와 같은 의미다.
size : 배열에 담긴 요소(원소)의 개수 변수
참고로 head와 tail은 '큐(Queue)' 관점에서 을 기준으로 쓴다.
[offer 계열 메소드 구현]
이제 본격적으로 Deque에 데이터를 추가할 수 있도록 해보자.
Deque의 삽입은 크게 두 가지로 나뉜다.
기본 메소드 offer() 및 offerLast()는 후방(맨 뒤)에 데이터를 추가한다. 리스트로 치면 add(E value) 및 addLast(E value)와 같은 역할이다. 두 번째는 전방(맨 앞)에 데이터를 추가하는 경우다. 이는 offerFirst()가 담당하며 리스트로 치면 addFirst()와 같은 역할이다.
다만 두 메소드 모두 고려해야 할 부분이라면 데이터가 비어있을 때다. 이 부분은 구현하면서 보도록 하자.
- 가장 마지막 부분에 추가 : offer(E item), offerLast(E item)
- 가장 앞의 부분에 추가 : offerFirst(E item)
1. 전방 삽입 : offerFirst(E item)
원래는 기본 메소드인 offer() 즉, 가장 뒷 부분에 추가하는 것 부터 구현할 수도 있지만, 이후에 구현해보면 알겠지만, 양방향 연결리스트의 경우는 전방 삽입부터 구현하는 것이 편리하다.
이유는 데이터가 한 개도 없을 때 결국 첫 번째 원소는 head이자 tail이 되는데 이 때는 전방 삽입 알고리즘으로 구현 되는 것이 좀 더 직관성이 있기 때문이다. 이는 구현 소스를 보면 이해가 갈 것이다.
일단 전방 삽입의 메커니즘을 그림으로 보도록 하자.
이를 토대로 순서대로 구현하면 된다. (요소가 한 개도 없을 때의 처리는 소스코드를 먼저 보고 설명하겠다.)
public boolean offerFirst(E value) { Node<E> newNode = new Node<E>(value); // 새 노드 생성 newNode.next = head; // 새 노드의 다음 노드로 head 노드를 연결 /** * head가 null이 아닐 경우에만 기존 head노드의 prev 변수가 * 새 노드를 가리키도록 한다. * 이유는 기존 head노드가 없는 경우(null)는 데이터가 * 아무 것도 없던 상태였으므로 head.prev를 하면 잘못된 참조가 된다. */ if (head != null) { head.prev = newNode; } head = newNode; // head가 가리키는 노드가 새 노드를 가리키도록 한다. size++; /** * 다음에 가리킬 노드가 없는 경우(=데이터가 새 노드밖에 없는 경우 = 이전의 head가 null인경우) * 데이터가 한 개(새 노드)밖에 없으므로 새 노드는 처음 시작노드이자 * 마지막 노드다. 즉 tail = head 다. */ if (head.next == null) { tail = head; } return true; }주석으로 설명을 해 놓았지만, 다시 한 번 글로 설명을 하자면 이렇다.
데이터가 없는 경우. 즉, 덱에 아무런 요소가 없는 경우는 head = null 인 상태다.
만약 head = null 인 상태일 경우 newNode.next = head 는 결국 newNode.next = null 이 된다.
그리고 원래는 앞 부분에 추가하려면 기존 head 노드의 prev가 가리키는 노드를 새 노드로 연결해주어야 한다.
근데 head = null 상태라면 null.prev 즉, null상태에서 어떠한 변수를 참조할 수 없는데, 참조하려고 하면 NullPointerException 예외가 던져져버린다. 이러한 것을 방지하기 위해 head가 null 이 아닐 때만 head.prev를 새로운 노드를 가리키도록 해주어야 한다.
그 다음 마지막 그림처럼 head가 가리키는 노드를 새 노드를 가리키도록 변경해주고 size를 1 증가시킨다.
마지막으로 head.next 즉, 구(이전) head가 null 이라면 새로 들어온 노드가 결국 첫 노드였다는 말로 head와 tail이 가리키는 노드 모두 새 노드를 가리키게 된다.
2. 후방 삽입 : offer(E item), offerLast(E item)
덱의 마지막 부분에 삽입하는 메소드다. 조금만 생각해본다면 offerFirst와 크게 다를 것은 없으니 한 번 그림을 보면 쉽게 구현 할 수 있을 것이다.
offerFirst는 head 변수를 통해 데이터를 추가하였다면, 이 번에는 반대로 tail 변수를 이용하여 반대로만 구현 하면 된다.
그리고 여기서는 데이터가 없을 때의 구현은 따로 하지 않고, 만약 데이터가 없다면 앞에서 구현했던 offerFirst() 메소드로 넘겨주면 된다.
@Override public boolean offer(E value) { return offerLast(value); } public boolean offerLast(E value) { // 데이터가 없을 경우 offerFirst()로 인자를 넘겨줌 if (size == 0) { return offerFirst(value); } Node<E> newNode = new Node<E>(value); tail.next = newNode; // tail이 가리키는 노드의 다음 노드를 새 노드를 가리키도록 연결 newNode.prev = tail; // 새 노드가 가리키는 이전노드 또한 tail이 가리키는 노드로 연결 tail = newNode; // tail이 가리키는 노드를 새 노드로 가리키도록 변경 size++; return true; }offer()과 offerLast()는 똑같은 메소드이기 때문에 offerLast를 구현해주고, offer()는 offerLast()를 호출해서 쓰도록 한다.
[offer 메소드 묶어보기]
더보기
public boolean offerFirst(E value) { Node<E> newNode = new Node<E>(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 value) { return offerLast(value); } public boolean offerLast(E value) { if (size == 0) { return offerFirst(value); } Node<E> newNode = new Node<E>(value); tail.next = newNode; newNode.prev = tail; tail = newNode; size++; return true; }
[poll 계열 메소드 구현]
poll 메소드 또한 앞부분에서 offer와 마찬가지로 크게 두 가지 경우로 나뉜다.
poll 및 pollFirst 메소드는 맨 앞의 요소를 삭제하는 메소드로 리스트에서의 removeFirst()와 같은 역할이며 front + 1 위치에 있는 요소를 삭제하면 된다.
반대로 pollLast 메소드는 맨 뒤의 요소를 삭제하는 메소드로 리스트에서의 removeLast()와 같은 역할이며 rear 위치에 있는 요소를 삭제하면 된다.
다만 두 가지 모두 중요한 점은 '삭제할 요소가 없는 경우' 다.
자바의 Deque에 관한 API 문서를 보면 알겠지만 삭제하려는 요소가 없을 경우 poll 계열의 경우 예외가 발생하는 것이 아닌 null을 반환한다. 하지만, remove 계열은 null이 아닌 NoSuchElementException 예외를 던진다.
다시 한 번 표를 보면 이렇다.
참고 문서 링크 : docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html
1. 전방 삭제 : poll(), pollFrist(), remove(), removeFirst()
일단 poll() 및 pollFirst() 메소드를 구현하고 이를 remove() 메소드에 응용하여 적용할 것이다.
poll의 구조 또한 매우 쉬우니 그림을 다시 한 번 보고 구현해보도록 하자.
이번 메소드 또한 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의 다음노드 // head가 가리키는 모든 데이터들 삭제 head.data = null; head.next = null; // 삭제하기전 데이터가 두 개 이상 있을 경우(head와 tail이 같지 않은 경우) if (nextNode != null) { nextNode.prev = null; } head = null; head = nextNode; // head가 가리키는 노드를 삭제한 노드의 다음 노드로 갱신 size--; /** * 삭제된 요소가 덱의 유일한 요소였을 경우 * 그 요소는 head 이자 tail이었으므로 * 삭제되면서 tail도 가리킬 요소가 없기 때문에 * size가 0일경우 tail도 null로 변환 */ 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; }삭제 과정은 그림과 동일하다. 특히 head의 데이터들을 삭제하기 전에 head의 다음노드를 미리 임시 변수로 갖고온 뒤 삭제해야 한다.
그런 다음 다음 노드가 null인지 아닌지에 따라 다음 노드의 prev변수(삭제했던 노드를 가리킴)을 null로 링크를 끊어준 뒤, 다음 노드를 head가 가리키도록 하는 것이다.
remove() 는 removeFirst() 메소드를 호출하고, removeFirst()는 pollFirst() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.
2. 후방 삭제 : pollLast()
pollFirst와는 달리 마지막에 있는 요소를 삭제하는 메소드다. 리스트에서는 removeLast()와 같은 역할인 것이다.
조금 생각해보자면 offer() 와 pollLast() 을 조합하여 응용하면 스택으로도 사용할 수 있는 것이다.
일단 그림을 먼저 보고 가자.
여기서 중요한 점은 offerFirst 때 했던 것처럼 요소가 없을 경우, 즉 사이즈가 0일 경우와 요소가 하나만 있었을 경우를 고려하면서 구현하면 된다.
public E pollLast() { if (size == 0) { return null; } E element = tail.data; // 반환하기 위한 데이터 Node<E> prevNode = tail.prev; // tail이 가리키는 노드의 데이터와 링크 삭제 tail.data = null; tail.prev = null; // 삭제하기전 데이터가 두 개 이상 있을 경우(head와 tail이 같지 않을 경우) if (prevNode != null) { prevNode.next = null; } tail = null; tail = prevNode; size--; /** * 삭제된 요소가 덱의 유일한 요소였을 경우 * 그 요소는 head 이자 tail이었으므로 * 삭제되면서 head도 가리킬 요소가 없기 때문에 * size가 0일경우 head도 null로 변환 */ if(size == 0) { head = null; } return element; } public E removeLast() { E element = pollLast(); if(element == null) { throw new NoSuchElementException(); } return element; }removeLast() 메소드는 pollLast() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.
[poll / remove 메소드 묶어보기]
더보기
@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; }
[peek 계열 메소드 구현]
보통 가장 앞 또는 뒤에 있는 데이터를 삭제하지 않고 확인만 하고싶을 때가 있다. 그럴 때 쓰는 것이 peek() 계열의 메소드다. 한마디로 poll() 메소드에서 삭제과정만 없는 것이 peek() 이다.
peek()은 가장 앞에 있는 데이터를 반환하는 것이고, 이는 peekFirst() 메소드와 같다.
또한 가장 뒤에 있는 데이터를 반환하는 것이 peekLast() 다.
그래서 pollFirst(), pollLast()에서 삭제과정만 빼고 그대로 반환하면 되기 때문에 설명 할 것이 없다.
그리고 참고로 덱에 데이터가 없는 경우는 null을 던진다. 반대로 이와 유사한 element() 메소드는 큐에 요소가 없을 경우 remove() 메소드와 마찬가지로 NoSuchElementException 예외를 던진다.
이 때 보통은 elementLast()와 elementFirst()로 나뉠 것으로 예상했겠지만, 자바에서는 getLast()와 getFirst() 로 나뉜다.
즉, getFirst()가 elementFIrst() 의미라고 생각하고, getLast()가 elementLast() 의미라고 생각하면 된다.
1. peek, peekFirst 메소드
@Override public E peek() { return peekFirst(); } public E peekFirst() { // 요소가 없을 경우 null 반환 if(size == 0) { return null; } return head.data; }peek, peekFirst 메소드는 기본적으로 가장 앞에 있는 데이터를 갖고오는 것이기 때문에 head의 데이터를 반환시키면 된다.
2. peekLast() 메소드
public E peekLast() { // 요소가 없을 경우 null 반환 if(size == 0) { return null; } return tail.data; }removeLast() 에서 삭제 과정이 없는 것과 같다.
3. element, getFirst 메소드
public E element() { return getFirst(); } public E getFirst() { E item = peek(); // 앞의 원소 null 이라면(size = 0) 예외를 던진다. if(item == null) { throw new NoSuchElementException(); } return item; }앞서 말했듯 element() 메소드와 getFirst() 는 같은 메소드다. 또한 우리가 구현한 peek 메소드를 호출하여 맨 앞의 원소를 얻고, 만약 null이라면 그 때 예외를 던져주면 된다.
4. getLast() 메소드
public E getLast() { E item = peekLast(); // 앞의 원소 null 이라면(size = 0) 예외를 던진다. if(item == null) { throw new NoSuchElementException(); } return item; }마찬가지로 마지막 원소를 반환하되 null이면 예외를 던지면 된다.
[peek / 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; }
[size, isEmpty, contains, clear 메소드 구현]
이제 나머지는 그나마 자주 사용되는, 거의 필수적인 메소드를 구현해보고자 한다.
1. size() 메소드
size는 매우 간단하게 현재 덱에 있는 요소의 개수를 알려준다.
public int size() { return size; }2. isEmpty() 메소드
isEmpty() 메소드는 현재 덱에 비어있는지를 확인 할 때 쓰인다. 요소의 개수가 0개라면 비어있다는 뜻이므로, 비어있다면 true를, 비어있지 않다면 false를 반환한다.
public boolean isEmpty() { return size == 0; }3. contains() 메소드
contains() 는 현재 찾고자하는 요소가 덱에 들어가있는지를 알려주는 메소드다.
public boolean contains(Object value) { /** * head 데이터부터 x가 null이 될 때까지 value랑 x의 데이터(x.data)랑 * 같은지를 비교하고 같을 경우 true를 반환한다. */ for(Node<E> x = head; x != null; x = x.next) { if(value.equals(x.data)) { return true; } } return false; }현재 덱에 있는 요소들 중 value랑 데이터가 일치하는 것이 있는지를 검사하면 된다.
4. clear() 메소드
clear() 메소드는 단어 그대로 Deque의 모든 요소를 비워버린다.
public void clear() { for (Node<E> x = head; x != null;) { Node<E> next = x.next; x.data = null; x.next = null; x.prev = null; x = next; } size = 0; head = tail = null; }이 때는 혹시 모를 경우까지 대비해 모든 공간을 명시적으로 null 처리를 해주는 것이 좋다.
그리고 빈 공간은 초기 상태와 마찬가지로 front 와 rear와 size 모두 0으로 초기화 해준다.
이렇게 size, isEmpty, contains, clear 메소드들을 만들어보았다. 해당 메소드들을 묶어서 한 눈에 보고싶다면 아래 더보기를 누르면 된다.
[ 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.next = null; x.prev = null; x = next; } size = 0; head = tail = null; }
<부가 목록>
[toArray, clone, sort 메소드 구현]
이 부분은 굳이 구현하는데 중요한 부분은 아니라 넘어가도 된다. 다만 조금 더 많은 기능을 원할 경우 추가해주면 좋은 메소드들이긴 하다. toArray는 사용자가 main 함수에서 특정 배열로 반환받고싶다거나 복사하고 싶을 때 Queue에 저장된 데이터들을 배열로 반환해주는 역할을 하기 위해 만들었다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 만드는 것이다.
마지막으로 sort()메소드는 말 그대로 정렬해주는 메소드다.
1. toArray() 메소드
toArray()는 크게 두 가지가 있다.
하나는 아무런 인자 없이 현재 있는 덱의 요소들을 객체배열(Object[]) 로 반환해주는 Object[] toArray() 메소드가 있고,
다른 하나는 덱를 이미 생성 된 다른 배열에 복사해주고자 할 때 쓰는 T[] toArray(T[] a) 메소드가 있다.
즉 차이는 이런 것이다.
LinkedListDeque<Integer> linkedlistdeque = new LinkedListDeque<>(); // get LinkedListDeque to array (using toArray()) Object[] dq1 = linkedlistdeque.toArray(); // get LinkedListDeque to array (using toArray(T[] a) Integer[] dq2 = new Integer[10]; dq2 = linkedlistdeque.toArray(dq2);1번의 장점이라면 덱에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점이다.
2번의 장점이라면 객체 클래스로 상속관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다. 또한 덱의 원소 5개가 있고, dq2 배열에 10개의 원소가 있다면 dq2에 0~4 index에 원소가 복사되고, 그 외의 원소는 기존 dq2배열에 초기화 되어있던 원소가 그대로 남는다.
두 메소드 모두 구현해보자면 다음과 같다.
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) { // Array.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; }첫 번째 toArray()는 쉽게 구현 할 수 있다.
각 노드를 방문하면서 노드의 데이터들을 array 배열에 담고 반환하면 된다.
문제는 toArray(T[] a) 메소드다. ArrayDeque에서는 내부에서 데이터를 Object[] 배열에 담았기 때문에 데이터 복사가 쉬웠으나, LinkedListQueue는 '노드'라는 객체에 데이터를 담고있는 연결리스트이기 때문에 노드 자체가 Integer, String 처럼 래퍼클래스나, 사용자가 만든 클래스 같은 데이터를 갖을 수가 없다. 한 마디로 노드의 data 변수가 객체 타입 변수인 것이지 노드 자체가 변환하고자 하는 제네릭 타입을 갖지 못한다. 그래서 이전처럼 Arrays.copyOf() 메소드나 System.arraycopy를 쓰기 어렵다.
이럴 때 바로 쓸 수 있는 것이 lang.reflect 패키지에 있는 Array 클래스의 도움을 받을 수 있다. 이에 대한 API는 아래 링크로 남겨둘 것이니 참고해보시길 바란다.
docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/reflect/Array.html
Array (Java SE 11 & JDK 11 )
docs.oracle.com
여기서 우리가 사용 할 메소드는 이 것이다.
두 번째 T[] toArray(T[] a) 메소드를 보자.
이 부분은 제네릭 메소드로, 우리가 만들었던 LinkedListDeque의 E타입하고는 다른 제네릭이다. 예로들어 E Type이 Integer라고 가정하고, T타입은 Object 라고 해보자.
Object는 Integer보다 상위 타입으로, Object 안에 Integer 타입의 데이터를 담을 수도 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.
즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성하는 것이다. 하위 타입, 즉 축소할 경우 Array 클래스에서 예외를 던지기 때문에 이에 대한 별다른 예외를 처리해줄 필요 없다.
그리고 크게 두 가지 경우의 수가 있다.
첫 번째는 파라미터로 주어지는 배열 a가 현재 덱의 요소보다 작은 경우와, 그 반대의 경우 이렇게 있다.
먼저 들어오는 배열(a)가 현재 덱의 요소 개수(size)보다 작으면 size에 맞게 a의 공간을 재할당 하면서 덱에 있던 모든 요소를 복사한다.
쉽게 이해해보면 LinkedListDeque의 요소(데이터)가 4개 {1, 2, 3, 4} 있다고 치자. 그리고 Object[] copy = new Object[1]라는 배열을 하나 만들었는데, 공간이 한 개 밖에 없다.
그러면 덱의 요소 1개만 복사하는 것이 아니라 copy 배열의 사이즈가 1에서 4로 증가하여 copy배열에 {1, 2, 3, 4}가 모두 담기게 되는 것이다.
또한 a에 대한 타입을 알기 위해 먼저 getClass().getComponentType() 을 통해 객체가 어떤 유형의 배열인지를 파라미터를 넣고, 배열의 크기를 설정해준다.
그런 다음 a를 얕은 복사을 통한 Object[] 배열을 하나 만들어 해당 배열을 통해 데이터를 넣어준다음 a를 반환한다. 얕은 복사이기 때문에 s 배열에 담으면 자동으로 a배열에도 영향을 미치는 것을 활용한 방법이다.
조금 복잡해보일 수는 있으나, 최대한 이해할 수 있도록 주석을 달아놓았으니 참고해보고 이해가 안된다면 댓글은 남겨주시면 답변드리도록 하겠다.
2. clone() 메소드
만약 사용자가 사용하고 있던 Deque를 새로 하나 복제하고 싶을 때 쓰는 메소드다. 즉, 얕은 복사가 아닌 깊은 복사로 아예 다른 하나의 클론을 만드는 것이다.
단순히 = 연산자로 객체를 복사하게 되면 '주소'를 복사하는 것이기 때문에 복사한 객체에서 데이터를 조작할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(shallow copy)가 된다는 것이다.
LinkedListDeque<Integer> original = new LinkedListDeque<>(); original.offer(10); // original에 10추가 LinkedListDeque<Integer> copy = original; copy.offer(20); // copy에 20추가 System.out.println("original LinkedListDeque"); int i = 0; for(Object a : original.toArray()) { System.out.println(i + "번 째 data = " + a); i++; } System.out.println("\ncopy LinkedListDeque"); i = 0; for(Object a : copy.toArray()) { System.out.println(i + "번 째 data = " + a); i++; } System.out.println("\noriginal LinkedListDeque reference : " + original); System.out.println("copy LinkedListDeque reference : " + copy);[결과]
보다시피 객체의 주소가 복사되는 것이기 때문에 주소와 데이터 모두 같아져버리는 문제가 발생한다.
이러한 것을 방지하기 위해서 깊은 복사를 하는데, 이 때 필요한 것이 바로 clone()이다. Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 구현해야 할 경우 반드시 Clonable 인터페이스를 implement 해야한다.
즉, public class LinkedListDeque<E> implements Queue<E> 에 Cloneable도 추가해주어야 한다.
그리고나서 clone()을 구현하면 되는데, 다음과 같이 재정의를 하면 된다.
@Override public Object clone() { // super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다. try { @SuppressWarnings("unchecked") LinkedListDeque<E> clone = (LinkedListDeque<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; } catch (CloneNotSupportedException e) { throw new Error(e); // 예외처리는 여러분들이 자유롭게 구성하면 된다. } }조금 어려워 보일 수 있는데, 이해하지 못해도 된다. 자료구조에서 중요한 부분은 아니니...
설명을 덧붙이자면, super.clone() 자체가 생성자 비슷한 역할이고 shallow copy를 통해 사실상 new LinkedListDeque<>() 를 호출하는 격이라 제대로 완벽하게 복제하려면 clone한 큐의 array 또한 새로 생성해서 해당 배열에 copy를 해주어야 한다.
위와같이 만들고 나서 clone()한 것 까지 포함해서 테스트를 해보자.
LinkedListDeque<Integer> original = new LinkedListDeque<>(); original.offer(10); // original에 10추가 LinkedListDeque<Integer> copy = original; LinkedListDeque<Integer> clone = (LinkedListDeque<Integer>) original.clone(); copy.offer(20); // copy에 20추가 clone.offer(30); // clone에 30추가 System.out.println("original LinkedListDeque"); int i = 0; for (Object a : original.toArray()) { System.out.println(i + "번 째 data = " + a); i++; } System.out.println("\ncopy LinkedListDeque"); i = 0; for (Object a : copy.toArray()) { System.out.println(i + "번 째 data = " + a); i++; } System.out.println("\nclone LinkedListDeque"); i = 0; for (Object a : clone.toArray()) { System.out.println(i + "번 째 data = " + a); i++; } System.out.println("\noriginal LinkedListDeque reference : " + original); System.out.println("copy LinkedListDeque reference : " + copy); System.out.println("clone LinkedListDeque reference : " + clone);[결과]
결과적으로 clone으로 복사한 LinkedListDeque는 원본 LinkedListDeque에 영향을 주지 않는다.
3. sort() 메소드
일단 sort()를 구현하기 전에 자바의 비교기에 대해 알아야 한다.
자바의 데이터 정렬을 위한 비교기는 크게 두 가지가 있다. 하나는 Comparable, 다른 하나는 Comparator다. 정말정말 쉽게 말하자면 Comparable을 쓰는 경우는 해당 객체의 기본 정렬 방법을 설정할 때이고, Comparator의 경우는 특정한 경우에 임시적으로 쓸 수 있게 정렬을 정의할 때 쓰인다.
우리가 흔히 쓰는 int[] 배열, String[] 배열 등 수많은 클래스들은 기본적으로 자체 정렬 방식을 지원하기 때문에 Comparator을 쓰지 않아도 정렬 할 수 있었다.
만약 래퍼(Wrapper) 클래스 타입(ex. Integer, String, Double ...)이라면 따로 Comparator 을 구현해주지 않아도 되지만, 사용자 클래스, 예로들어 Student 클래스를 만든다거나.. 이러한 경우는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 또는 Comparator를 구현해주어 파라미터로 넘겨주어야 한다.
Arrays.sort() 메소드를 뜯어본 분들은 알겠지만 Arrays.sort()의 종류중에서는 인자를 두 개 받는 경우가 있다. 정렬을 해보신 분은 알겠지만 가끔 2차원 배열을 정렬하고 싶을 때 다음과 같이 쓰지 않았는가?
int[][] arr = new int[10][10]; Arrays.sort(arr, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { // 구현부 } });이러한 메소드가 바로 아래 사진의 메소드로 간다.
위 사진을 보면 크게 if(c == null) 일 경우와 아닌 경우로 나뉜다.
즉, Comparator 인자가 있는지, 또는 없는지를 말해주는데, Comparator 인자(c)가 없는 경우 해당 객체의 Comparable 구현이 있는지를 확인하고 있으면 정렬하며, 구현되지 않았을 경우 에러를 뱉는다.
결과적으로 sort() 메소드를 만들 때, 기본적으로 두 가지 경우를 생각해야 한다는 것이다. 첫 번째는 객체에 Comparable이 구현되어 있어 따로 파라미터로 Comparator를 넘겨주지 않는 경우고, 다른 하나는 Comparator을 넘겨주어 정의 된 정렬 방식을 사용하는 경우다.
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]; } }위 코드에서 보듯이 어떠한 형태로든 결국 sort((Comparator<? super E> c) 로 간다. (참고로 상속관계이면서 부모 클래스에서 정렬 방식을 따르는 경우도 생각하여 <? super E>로 하였다. 이러한 경우를 고려하지 않는다면 Comparator<E>로 해주어도 종속관계 영향을 안받는 객체의 경우는 괜찮다.)
그런다음 Object[] 배열로 우리가 만들었던 toArray()를 통해 만들어 주어 Arrays.sort() 메소드를 통해 정렬해준다.
실제로도 Collections.sort() 또한 Arrays.sort()로 보낸다. 잠깐 내부 구현을 들여다보면 이렇다.
[Collections.sort()] - Comparator() 파라미터가 없는 경우
[Collections.sort()] - Comparator() 파라미터가 주어지는 경우
그리고 두 메소드 모두 List 인터페이스의 default 메소드인 sort() 메소드로 보낸다. 해당 내부 구현은 이렇다.
[List.sort()]
다만 필자가 올린 코드와 차이가 있다면, Iterator을 구현하지 않았기 때문에 대신 반복문을 통해 현재 클래스의 노드 데이터를 직접 바꾼다는 것 뿐이다.
그럼 한 번 테스트를 해보자.
Student 클래스를 통해 이름과 성적을 입력받고, 이를 정렬하는 테스트를 해보도록 한다.
<Student 클래스가 Comparable을 구현하지 않았을 경우>
[test.java]
public class test { public static void main(String[] args) { LinkedListDeque<Student> dq = new LinkedListDeque<>(); dq.offer(new Student("Chen" , 89)); dq.offer(new Student("Malli" , 65)); dq.offer(new Student("Tomas" , 53)); dq.offer(new Student("Cris" , 79)); dq.offer(new Student("Julia" , 93)); dq.sort(); for(Object a : dq.toArray()) { System.out.println(a); } } } class Student { String name; int score; Student(String name, int score){ this.name = name; this.score = score; } public String toString() { return "이름 : " + name + "\t성적 : " + score; } }[결과]
이렇게 Comparable을 구현하지 않아 해당 객체의 정렬 방법을 몰라 빨갛게 에러를 뱉어준다. 즉, 명시적으로 Arrays.sort()에 정렬 방법을 알려주던가, Student 클래스에 정렬 방법을 구현하던가 해야한다.
<Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법>
[test.java]
import java.util.Comparator; public class test { public static void main(String[] args) { LinkedListDeque<Student> dq = new LinkedListDeque<>(); dq.offer(new Student("Chen", 89)); dq.offer(new Student("Malli", 65)); dq.offer(new Student("Tomas", 53)); dq.offer(new Student("Cris", 79)); dq.offer(new Student("Julia", 93)); dq.sort(customComp); for(Object a : dq.toArray()) { System.out.println(a); } } // 사용자 설정 comparator(비교기) static Comparator<Student> customComp = new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { return o2.score - o1.score; // 성적 내림차순 } }; } class Student { String name; int score; Student(String name, int score) { this.name = name; this.score = score; } public String toString() { return "이름 : " + name + "\t성적 : " + score; } }이렇게 하면 정렬이 될까? 당연하겠지만 된다.
[결과]
<Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법>
객체 기본 정렬방식을 설정해주는 방법. 즉 Comparable 구현 방법으로도 가능하다.
public class test { public static void main(String[] args) { LinkedListDeque<Student> dq = new LinkedListDeque<>(); dq.offer(new Student("Chen", 89)); dq.offer(new Student("Malli", 65)); dq.offer(new Student("Tomas", 53)); dq.offer(new Student("Cris", 79)); dq.offer(new Student("Julia", 93)); dq.sort(); // Comparator 인자가 필요하지 않음 for(Object a : dq.toArray()) { System.out.println(a); } } } class Student implements Comparable<Student>{ String name; int score; Student(String name, int score){ this.name = name; this.score = score; } public String toString() { return "이름 : " + name + "\t성적 : " + score; } @Override public int compareTo(Student o) { return o.score - this.score; } }이러면 sort() 내부에서 Comparator가 없으니 해당 클래스의 Comparable에서 compareTo() 을 구현한 내용을 찾아 작성한대로 정렬을 해준다.
[결과]
[toArray, clone, sort 메소드 묶어보기]
더보기
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) { 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; } @Override public Object clone() { try { @SuppressWarnings("unchecked") LinkedListDeque<E> clone = (LinkedListDeque<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; } catch (CloneNotSupportedException e) { throw new Error(e); } } public void sort() { 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]; } }
- 전체 코드
위 코드는 아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.
[소스코드 모아보기]
github 자료구조 모음
kdgyun/Data_Structure
Contribute to kdgyun/Data_Structure development by creating an account on GitHub.
github.com
- 정리
연결리스트로 구현한 Deque에 대한 기본적인 메소드와 더불어 추가적인 메소드들을 구현해보았다.
기본적으로 Deque은 앞 뒤로 접근이 모두 가능해서 필요에 따라 큐처럼, 또는 스택처럼 사용 할 수 있는 것이 장점이다. 덱을 구현하는 방법도 매우 다양하지만, 기본적으로 배열로 구현할 경우는 배열 큐를 골자로 하고, 연결리스트로 구현할 경우 LinkedList 구조를 그대로 상속하여 써도 된다.
혹여 어렵거나 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.