Linked List - 4

Double Linked List 데이터 핸들링

1. 임의의 노드 앞에 데이터 삽입

이전 노드의 next pointer에 추가할 노드의 주소를 넣어주어야 하고,
추가할 노드의 before pointer에 이전 노드의 주소를 넣어주어야 한다.
이후 노드의 before pointer에 추가할 노드의 주소를 넣어주어야 하고,
추가할 노드의 next pointer에 이후 노드의 주소를 넣어주어야 한다.

    public static class DoubleLinkedList<T> {
        public Node<T> head = null;
        public Node<T> tail = null;

        public class Node<T> {
            T data;
            Node <T> prev = null;
            Node <T> next = null;

            public Node(T data) {
                this.data = data;
            }
        }

        public void addNode(T data) {
            if(this.head == null) {
                this.head = new Node<T>(data);
                this.tail = this.head;
            } else {
                Node<T> node = this.head;
                while(node.next != null) {
                    node = node.next;
                }
                node.next = new Node<T>(data);
                node.next.prev = node;
                this.tail = node.next;
            }
        }

        public void printAll() {
            String str = "";

            if(this.head != null) {
                Node<T> node = this.head;
                str = String.valueOf(node.data);

                while(node.next != null) {
                    node = node.next;
                    str += ", " + String.valueOf(node.data);
                }
            }

            System.out.println(str);
        }

        public Node<T> searchFromHead(T isData) {
            if(this.head == null) {
                return null;
            } else {
                Node<T> node = this.head;
                while(node != null) {
                    if(node.data == isData) {
                        return node;
                    } else {
                        node = node.next;
                    }
                }
                return null;
            }
        }

        public Node<T> searchFromTail(T isData) {
            if(this.head == null) {
                return null;
            } else {
                Node<T> node = this.tail;
                while(node != null) {
                    if(node.data == isData) {
                        return node;
                    } else {
                        node = node.prev;
                    }
                }
                return null;
            }
        }

        public void addNodeInside(T data, T isData) {
            // 1. data 노드를 isData 뒤에 놓기
            Node<T> bfNode = searchFromHead(isData);

            Node<T> nextNode = null;
            if(bfNode != null) {
                nextNode = bfNode.next;
            }

            if(bfNode == null) {
                this.addNode(data);
            } else {
                bfNode.next = new Node<T>(data);
                bfNode.next.prev = bfNode;
                bfNode.next.next = nextNode;
            }

            // 2. data 노드를 next의 앞에 놓기
            if(nextNode != null) {
                nextNode.prev = bfNode.next;
            }
        }
        
    public static void main(String[] args) {
        // DoubleLinkedList 중간 노드 삽입
        System.out.println("");
        System.out.println("======================== DoubleLinkedList 중간 노드 삽입 ========================");

        DoubleLinkedList<Integer> doubleLinkedList3 = new DoubleLinkedList<Integer>();

        doubleLinkedList3.addNode(1);
        doubleLinkedList3.addNode(2);
        doubleLinkedList3.addNode(3);
        doubleLinkedList3.printAll();		// 1, 2, 3

        // 2 뒤에 4 삽입
        doubleLinkedList3.addNodeInside(4, 2);
        doubleLinkedList3.printAll();		// 1, 2, 4, 3

        // 3 뒤에 5 삽입
        doubleLinkedList3.addNodeInside(5, 3);
        doubleLinkedList3.printAll();		// 1, 2, 4, 3, 5

        // 없는 데이터를 찾도록 하여 맨 뒤에 6 삽입
        doubleLinkedList3.addNodeInside(6, 20);
        doubleLinkedList3.printAll();		// 1, 2, 4, 3, 5, 6
    }