Java

DoubleLinkedList

DoubleLinkedList?

• 기존에 SingleLinkedList는 헤드에서 출발해야지 Search를 할수가 있었다.
• 만약 100개의 데이터가 있다고 가정한다면 100번째 데이터를 조회하고 싶을때는 100번 노드를 옮기면서 값이 맞는지 판별해야 한다.
• 따라서 이러한 조회를 한쪽에서만 하는것이 아닌 양쪽으로 해서 좀더 효율적인 LinkedList가 DoubleLinkedList이다.
• DoubleLinkedList는 기존에 데이터를 포함한 상태에서 앞에 노드를 가리키는 포인터(prev) + 뒤에 노드를 가리키는 포인터(next)이 존재를 한다.
• 기존에 Head로 시작하여 뒤로 가는 노드와 + 끝에서 앞으로가는 Tail구조로 작동한다.

Node

• SingleLinkedList는 기존에 시작을 가리키는 head 노드와 노드의 구조를 나타내는 data + 다음 노드를 가리키는 next 포인터가 존재 했다.
• DoubleLinkedList는 head노드와 더불어 뒤에서 시작할 수 있는 tail노드와 데이터를 가지고 있는 노드에는 이전 노드를 가리키는 prev 노드를 만들면 된다.

package linkedlist;

public class DoubleLinkedList<T> { // 어떤 자료형의 데이터로 LinkedList를 만들지 모르기 때문에 항상 제네릭 문법을 사용한다.
    public Node<T> head = null;
    public Node<T> tail = null;

    public class Node<T>{
        T data;
        Node<T> prev = null;    // 이전 노드를 가리키는 prev
        Node<T> next = null;    // 다음 노드를 가리키는 next
    }
}

addNode

• DoubleLinkedList에서 데이터를 추가할때 SingleLinkedList와 똑같이 head 노드가 null / null이 아닐때로 구분하여 노드 삽입을 각각 구현하면 된다.
• 이때 tail과 prev가 추가된 만큼 tail은 LinkedList의 마지막을 가리키게 prev는 이전 노드를 가리키게 구현해야 한다.

    public void addNode(T data){
        if(this.head == null){  // 링크드리스트에 데이터가 없는 경우
            this.head = new Node<T>(data); // head가 가리키는 새로운 노드를 만든다.
            this.tail = this.head; // 맨 처음 노드는 head가 가리키는 노드 = tail이 가리키는 노드가 같다.
        }else{
            Node<T> node = this.head;   // 추가할 마지막 노드를 찾기 위해 head를 가리키는 노드를
            while(node.next!=null){
                node = node.next;
            }
            node.next = new Node<T>(data);  //현재 마지막으로 가리키는 노드의 다음을 새로운 노드를 추가하고.
            node.next.prev = node;  // 다음 노드에 이전에는 기존에 마지막으로 지정했던 노드를 가리키게 한다.
            this.tail = node.next;  // 새로 생긴 노드는 tail이 가리켜야 하기 때문에 다음 노드로 설정 
        }
    }

printNode

• printNode는 SingleLinkedList와 동일하게 head가 null이 아닐 경우만
  정상적인 출력을 실행하면 된다.

    public void printNode(){
        if(this.head != null){
            Node<T> node = this.head;
            System.out.println(node.data);
            while(node.next!= null){
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

reverstPrintNode

• tail부터 시작하는 역순 출력은 tail null이 아닐경우 부터 head노드까지의 데이터를 정상적으로 출력하면 된다.

    public void reversePrintNode(){
        if(this.tail != null){
            Node<T> node = this.tail;
            System.out.println(node.data);
            while(node.prev != null){
                node = node.prev;
                System.out.println(node.data);
            }
        }
    }

searchFromHead

• LinkedList가 비어있을때와 비어있지않을때로 나누어서 구현하면 된다.
• Head에서 시작할때는 head노드를 가리키는 노드를 선언하고 마지막 노드까지 노드를 옮기면서 데이터를 조회하면 된다.
• 모든 노드를 조회해도 같은 데이터가 없다면 null을 리턴하면 된다.

    public T searchFromHead(T isData){
        if(this.head == null){  // 데이터가 존재하지 않기 때문에
            return null;
        }else{
            Node<T> node = this.head;
            while (node!=null){ //node가 null이 될때까지 모든 노드를 다 조회하여 같은 데이터를 찾는다.
                if(node.data == isData){
                    return node.data;
                }else{
                    node = node.next;
                }
            }
            return null;
        }
    }

searchFromTail

• 뒤에서부터 시작하는 tail도 head가 null이 아니면 tail도 null이 아니게 addNode를 구현 했기 때문에 head와 똑같은 조건식으로 구현하면 된다.
• 차이점은 tail를 가리키는 노드를 선언하여 뒤에서부터 앞으로 가면 데이터 조회후 같은 데이터를 찾는 구조이고 만약 모든 노드를 전부 순회해도 같은 데이터가 없다면 null을 리턴한다.

    public 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.data;
                }else{
                    node = node.prev;
                }
            }
            return null;
        }
    }

insertToFront

• 기존에 있는 노드 데이터 이전에 데이터를 추가하는 함수
• node : existedData가 존재하는 노드의 위치
• nodePrev : 기존 노드에 이전에 있는 데이터
• nodePrev.next : 삽입 시킬 새로운 데이터

    public boolean insertFront(T existedData , T addData){
        if(this.head == null){
            this.head = new Node<T>(addData);
            this.tail = this.head;
        } else if (this.head.data == existedData) {  // head 노드의 데이터가 existeddata면 head 앞에 addData를 넣고 head가 완전히 바뀐다.
            Node<T> newHead = new Node<T>(addData);
            newHead.next = this.head;
            this.head = newHead;    // head가 바뀌었기 때문에 새로만든 노드를 head가 가리키게 만든다.
            return true;    // 정상적으로 처리 되었기 때문에 true를 리턴
        } else{ // head가 아닌 다른 노드에서 existedData랑 같은 경우
            Node<T> node = this.head;
            while (node!=null){
                if(node.data == existedData){
                    Node<T> nodePrev = node.prev;   //기존에 노드가 가리키는 이전 노드
                    nodePrev.next = new Node<T>(addData);   // 기존에 prev에 next는 새로 만들 노드를 가리키게 한다.
                    nodePrev.next.next = node; // 새로 생긴 노드의 다음을 기존에 exitedData가 존재하는 노드를 가리키게 한다.

                    nodePrev.next.prev = nodePrev; // 새로 생긴 노드에 이전을  기존에 가리키는 이전 노드로 설정한다.
                    node.prev = nodePrev.next;  // 기존 노드에 이전은 새로 생긴 노드로
                    return true;
                }
            }

        }
        return false;
    }