[자료구조] 양방향 연결 리스트(Doubly Linked List) 구현

1. 코드

Class NodeBi {
    int data;
    NodeBi next;
    NodeBi prev;
    
    NodeBi(int data, NodeBi next, NodeBi prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList {
    NodeBi head;
    NodeBi tail;
    
    DoublyLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
    }
    
    // 연결 리스트가 비어있는지 확인
    public boolean isEmpty() {
        if(this.head == null) {
            return true;
        }
        return false;
    }
    
    // 데이터 추가
    public void addData(int data, Integer beforeData) {
        if(this.head == null) {
            this.head = new NodeBi(data, null, null);
            this.tail = this.head;
        } else if (beforeData == null) { // 가장 끝에 데이터 추가
            this.tail.next = new NodeBi(data, null, this.tail);
            this.tail = this.tail.next;
        } else {
            NodeBi cur = this.head;
            NodeBi prev = cur;
            while(cur != null) {
                if(cur.data == beforeData) {
                    if(cur == this.head) {
                        this.head = new NodeBi(data, this.head, null);
                        this.head.next.prev = this.head;
                    } else {
                        prev.next = new NodeBi(data, cur, prev);
                        cur.prev = prev.next;
                    }
                    break;
                }
                prev = cur;
                cur = cur.next;
            }
        }
    }
    
    // 데이터 삭제
    public void removeData(int data) {
        if(this.isEmpty()) {
            System.out.println("List is Empty");
            return;
        }
        
        NodeBi cur = this.head;
        NodeBi prev = cur;
        
        while(cur != null) {
            if(cur.data == data) {
                if(cur == this.head && cur == this.tail) { // 데이터가 한 개인 경우
                    this.head == null;
                    this.tail == null;
                } else if(cur == this.head) { // 데이터가 가장 앞에 있는 경우
                    this.head = cur.next;
                    this.head.prev = null;
                } else if(cur == this.tail) { // 데이터가 가장 끝에 있는 경우
                    this.tail = this.tail.prev;
                    this.tail.next = null;
                } else { // 데이터가 중간에 있는 경우
                    prev.next = cur.next;
                    cur.next.prev = prev;
                }
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }
    
    // 출력
    public void showData() {
        if(this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        
        NodeBi cur = this.head;
        while(cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    
    // 역순으로 출력
    public void showDataFromTail() {
        if(this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        
        NodeBi cur = this.tail;
        while(cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.prev;
        }
        System.out.println();
    }
}