링크드 리스트(3) - 더블 링크드 리스트

- 기존의 링크드 리스트는 데이터를 무조건 처음부터 찾아나가야 함

- 더블 링크드 리스트는 하나의 노드에 2개의 포인터가 존재함

-> 따라서 100개의 노드가 있다면 99번째 노드는 100번째 노드로부터 찾을 수 있음

 

- 더블 링크드 리스트는 다음과 같이 구현할 수 있음 

-> addNode, printAll, searchFromHead, searchFromTail 메소드를 구현할 수 있음  

public 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(){

        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);
           }
        }
     }

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

 

참고

- 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online