Double Ended Linked List

Double Ended Linked List

- "Double Linked" 와는 다름~ 더블 링크드는 각 노드가 preNode, nextNode의 링크를 모두 가지고 있는 것이고, 지금 여기서의 Double Ended는 리스트 전체에서 head 포인터 뿐 아니라 tail 포인터도 가지고 있는 것이다.

- 배열로 구현할 때와 다르게, 최대 공간의 제약 없이 사용 가능

- 원소가 하나도 없을 때 뿐 아니라 디큐시에 원소가 하나만 있을 때도 고려 필요

- enqueue를 맨 앞, 맨 뒤, 원하는 위치에서 할 수 있도록 구현 (가장 첫 위치는 1으로 가정)

- dequeue를 맨 앞, 맨 뒤에 할 수 있도록 구현

- 큐 순회하며 데이터 출력하는 printQueue 메소드도 구현

허허.. 복잡하다 제대로 한건지 모르겠넹

 

 

public class LinkedListQueue {
 
    private Node head = null;
    private Node tail = null;
    
    public void enqueueAtTail(int data) {
        
        Node newNode = new Node(data, null);
        
        if(head == null)  // 큐가 비어있다면
            head = newNode;
        else 
            tail.setNextNode(newNode);
 
        tail = newNode;
        
        System.out.println("< EnQueueAtTail: " + newNode.getData());
        printQueue();
    }
    
    public void enqueueAtHead(int data) {
        Node newNode = new Node(data, null);
        
        newNode.setNextNode(head);
        head = newNode;
        if(tail == null)  // 빈 큐였었다면
            tail = newNode;        
 
        System.out.println("< EnQueueAtHead: " + newNode.getData());
        printQueue();
    }
    
    public void enqueueAtIndex(int data, int index) {
        
        if(index <= 1) {
            enqueueAtHead(data);
        }
        else {
            Node prevNode = head;
            
            int i = 2;
            while(i < index && prevNode != null) {
                prevNode = prevNode.getNextNode();
                i++;
            }
            
            if(prevNode == null) {
                System.out.println("Index Error");
                return;
            }
            
            Node nextNode = prevNode.getNextNode();
            Node newNode = new Node(data, null);
            prevNode.setNextNode(newNode);
            
            if(nextNode == null)
                tail = newNode;
            else
                newNode.setNextNode(nextNode);
            
            System.out.println("< EnQueueAtIndex: " + newNode.getData());
            printQueue();
        }
        
    }
    
    public int dequeueAtHead() {
        if(head == null) // 큐가 비어있다면
            return -1;
        
        Node newNode = head;
        head = head.getNextNode();
        
        if(head == null) // 큐에 원소가 하나밖에 없었다면, 이제 빈 큐가 됨
            tail = null;
        
        System.out.println("> DeQueueAtHead: " + newNode.getData());
        printQueue();
        
        return newNode.getData();
    }
    
    public int dequeueAtTail() {
        if(head == tail) {
            dequeueAtHead();
        }
        
        if(head == null) // 큐가 비어있다면
            return -1;
        
        Node prevNode = head;
 
        while(prevNode.getNextNode().getNextNode() != null) {
            prevNode = prevNode.getNextNode();
        }
        
        prevNode.setNextNode(null);
        
        Node newNode = tail;  // prevNode.getNextNode(); 와 동일
        tail = prevNode;
        
        System.out.println("> DeQueueAtTail: " + newNode.getData());
        printQueue();
        
        return newNode.getData();
    }    
    
    public void printQueue() {
        Node node = head;
        while(node != null) {
            System.out.print(node.getData() + ", ");
            node = node.getNextNode();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        queue.enqueueAtHead(3);
        queue.enqueueAtHead(2);
 
        queue.enqueueAtHead(1);
        queue.dequeueAtTail();
        queue.dequeueAtTail();
        queue.dequeueAtTail();
    }
}
 
class Node {
    private int data;
    private Node nextNode;
    
    public Node(int data, Node nextNode) {
        this.data = data;
        this.nextNode = nextNode;
    }
 
    public int getData() {
        return data;
    }
 
    public void setData(int data) {
        this.data = data;
    }
 
    public Node getNextNode() {
        return nextNode;
    }
 
    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }
}