양방향 연결리스트 구현하기

양방향 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고 있는 연결 리스트의 한 종류입니다. 

각 노드는 데이터와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 구성되어 있습니다. 

이러한 구조로 인해 양방향 연결 리스트는 단방향 연결 리스트와 달리 노드의 이전 노드를 쉽게 접근할 수 있습니다.

양방향 연결 리스트의 특징:

노드 구성: 각 노드는 데이터 필드와 두 개의 포인터(다음 노드를 가리키는 next 포인터와 이전 노드를 가리키는 prev 포인터)로 이루어져 있습니다.

양방향 이동: 단방향 연결 리스트와 달리, 양방향 연결 리스트는 노드의 이전 노드를 가리키는 prev 포인터를 통해 역방향으로 이동할 수 있습니다. 이로 인해 리스트를 앞뒤로 모두 순회할 수 있습니다.

삽입/삭제: 양방향 연결 리스트는 단방향 연결 리스트와 마찬가지로 삽입과 삭제가 O(1) 시간에 가능합니다. 즉, 특정 노드를 찾지 않고도 바로 앞이나 뒤에 노드를 삽입하거나 삭제할 수 있습니다.

추가적인 메모리: 단방향 연결 리스트와 달리 prev 포인터 때문에 각 노드가 더 많은 메모리를 사용합니다. 하지만 역방향 순회와 삽입/삭제가 더 효율적으로 이루어지는 장점이 있습니다.

양방향 연결 리스트의 구조는 다음과 같습니다:

   Node 1               Node 2                 Node 3                 Node 4
[ data | prev | next ] [ data | prev | next ] [ data | prev | next ] [ data | prev | next ]

양방향 연결 리스트 구현 

• 양방향 연결 리스트는 어떤 상황에서는 단방향 연결 리스트보다 유용하게 사용될 수 있습니다.
• 예를 들어 양방향으로 순회해야 하는 상황이나 양방향으로 삽입/삭제가 빈번하게 발생하는 경우에 유용하게 활용할 수 있습니다.
• 하지만 메모리 사용 측면에서는 단방향 연결 리스트보다 더 많은 공간을 사용한다는 점을 고려해야 합니다.
• 따라서 각 상황에 맞게 적절하게 연결 리스트를 선택하여 사용하는 것이 중요합니다.

package LinkedList;


public class DoublyLinkedListLearn {
    // 양방향 연결 리스트의 노드 클래스를 정의
    private static class Node {
        int data; // 저장할 데이터
        Node prev; // 이전 데이터
        Node next; // 다음 데이터

        // 생성자
        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }

    }

    // 양방향 연결 리스트 클래스를 정의
    private static class DoublyLinkedList {
        Node head;
        Node tail;

        // 리스트의 맨 뒤에 노드를 추가하는 메서드
        public void append(int data) {
            // 새로운 노드를 생성하고 데이터를 설정한다.
            Node newNode = new Node(data);

            // 리스트가 비어있는 경우
            if (head == null) {
                // head와 tail이 모두 새로운 노드를 가리키게 한다.
                head = newNode;
                tail = newNode;
            } else {
                // 리스트가 비어있지 않은 경우
                // 현재 tail의 다음 노드로 새로운 노드를 연결한다.
                tail.next = newNode;
                // 새로운 노드의 이전 노드를 현재 tail로 설정한다.
                newNode.prev = tail;
                // tail을 새로운 노드로 갱신한다.
                tail = newNode;
            }
        }

        public void prepend(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
            }
        }

        public void delete(int data) {
            Node current = head;
            while (current != null) {
                if (current.data == data) {
                    if (current == head) {
                        head = current.next;
                        if (head != null) {
                            head.prev = null;
                        }
                    } else if (current == tail) {
                        tail = current.prev;
                        if (tail != null) {
                            tail.next = null;
                        }
                    } else {
                        current.prev.next = current.next;
                        current.next.prev = current.prev;
                    }
                    break;
                }
                current = current.next;
            }

        }

        // 리스트의 모든 노드를 출력하는 메서드
        public void printList() {
            Node current = head;
            while (current != null) {
                System.out.print(current.data + " ");
                current = current.next;
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(1);
        dll.append(2);
        dll.append(3);

        dll.printList(); // 출력: 1 2 3

        dll.prepend(0);

        dll.printList(); // 출력: 0 1 2 3

        dll.delete(2);

        dll.printList(); // 출력: 0 1 3

    }

}