Double Linked List

Double Linked List

---

Double Linked List(이중 연결 리스트)란 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키며 다음 Node의 주소를 가리키는 next 포인터를 가지는 Single Linked List(단일 연결 리스트)에서 이전 Node의 주소인 prev 포인터가 Node에 추가된 Linked List이다. 

 

-head : 리스트의 가장 첫 Node 

-tail : 리스트의 가장 마지막 Node

 

Double Linked List의 특징

---

• 양쪽 방향으로 연결이 되어있어 앞에서부터의 검색 및 맨 뒤부터의 검색도 가능하다. (Single Linked List의 경우에는 뒷 쪽에 연결되어 있는 Node를 탐색 시 head를 시작으로 탐색해야 하지만 이중 Linked List는 tail부터 탐색을 할 수 있다.)
• next 포인터와 prev 포인터가 존재하기 때문에 리스트 중간에 노드 삽입 및 삭제 시 각 포인터들의 재조합으로 인해 복잡성이 높아진다.
• 이전 노드를 가리키기 위한 pointer를 하나 더 사용해야 하므로 그만큼의 메모리를 더 소비하게 된다. 

 

Double Linked List 구현해보기

---

public class DoubleLinkedList<T>{
    //전체 Linked List의 head
    public Node<T> head = null;
    //전체 Linked List의 tail 
    public Node<T> tail = null;
    
    //각각의 Node를 나타내는 inner class
    public class Node<T>{
        T data;
        //Node의 next pointer와 prev pointer
        Node<T> next = null;
        Node<T> prev = null;
        
        public Node(T data){
            this.data = data;
        }
    }
    
    //Node 추가하는 메소드
    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;
        }
    }
    
    //Linked List 전체를 확인하는 메소드
    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);
            }
            System.out.println("head : "+this.head.data);
            System.out.println("tail : "+this.tail.data);
        }
    }
    
    //Head에서 부터 찾고 싶은 Node를 찾는 메소드
    public T searchFromHead(T searchedData){
        if(this.head == null){
            return null;
        }else{
            Node<T> node = this.head;
            //head가 찾고 싶은 Node일 경우
            if(node.data == searchedData){
                return node.data;
            }
            //head에서 부터 Node 이동하면서 찾고싶은 Node 찾기
            while(node.next != null){
                node = node.next;
                if(node.data == searchedData){
                    return node.data;
                }                
            }
            return null;
        }
    }
    
    //Tail에서 부터 찾고 싶은 Node를 찾는 메소드
    public T searchFromTail(T searchedData){
        if(this.head == null){
            return null;
        }else{
            Node<T> node = this.tail;
            //tail이 찾고 싶은 Node일 경우
            if(node.data == searchedData){
                return node.data;
            }
            //tail에서 부터 Node 이동하면서 찾고싶은 Node 찾기
            while(node.prev != null){
                node = node.prev;
                if(node.data == searchedData){
                    return node.data;
                }
            }
            return null;
        }
    }
    
    //특정 Node 앞에 Node를 추가하는 메소드
    public boolean insertToFront(T searchedData, T addData){
        if(this.head == null){
            return false;
        }else{
            Node<T> node = this.head;
            //head의 data와 특정 Node의 data와 일치할 경우
            if(node.data == searchedData){
                Node<T> newHead = new Node<T>(addData);
                newHead.next = this.head;
                this.head.prev = newHead;
                this.head = newHead;
                
                return true;
            }
            
            //head 이외의 Node에서 특정 Node 찾기
            while(node.next != null){
                node = node.next;
                //특정 Node를 찾았을 경우
                if(node.data == searchedData){
                    //특정 Node앞에 새로운 Node를 추가하기 위해서 스와핑
                    Node<T> prevNode = node.prev;
                    
                    node.prev = new Node<T>(addData);
                    node.prev.prev = prevNode;
                    
                    node.prev.prev.next = node.prev;
                    node.prev.next = node;
                    
                    return true;
                }
            }
            return false;
        }
    }
    
    //특정 Node 뒤에 Node를 추가하는 메소드
    public boolean insertToBack(T searchedData, T addData){
        if(this.head == null){
            return false;
        //head의 data와 특정 Node의 data와 일치할 경우
        }else if(this.head.data == searchedData){
            //Linked List에 head Node만 있을 경우(해당 if문 없을 경우 nullpointerexception 발생함)
            if(this.head.next == null){
                this.head.next = new Node<T>(addData);
                this.head.prev = this.head;
                this.tail = this.head.next;
                
                return true;
            }
            
            //특정 Node 뒤에 Node를 추가하기 위한 스와핑
            Node<T> nextNode = this.head.next;
            
            this.head.next = new Node<T>(addData);
            this.head.next.next = nextNode;
            
            this.head.next.next.prev = this.head.next;
            this.head.next.prev = this.head;
            
            return true;
        }else{
            Node<T> node = this.head;
            while(node.next != null){
                node = node.next;
                if(node.data == searchedData){
                    //특정 Node 뒤에 Node를 추가하기 위한 스와핑
                    Node<T> nextNode = node.next;
                    
                    node.next = new Node<T>(addData);                                                                    
                    node.next.next = nextNode;
                    
                    //특정 Node가 마지막 Node일 경우 Node추가 후 tail Node 지정
                    if(node.next.next == null){
                        node.next.prev = node;
                        this.tail = node.next;
                    }else{
                        node.next.next.prev = node.next;
                        node.next.prev = node;
                    }                    
                    
                    return true;
                }
            }
            return false;
        }
    }
    
    //특정 Node를 삭제하는 메소드
    public boolean delNode(T data){
        if(this.head == null){
            return false;
        
        }else if(this.head.data == data){
             //Linked List에 head Node만 있을 경우
            if(this.head.next == null){
                this.head = null;
                return true;
            }
            
            this.head = this.head.next;
            this.head.prev = null;
            
            return true;
        }else{
            Node<T> node = this.head;
            while(node.next != null){
                if(node.next.data == data){
                    node.next = node.next.next;                    
                    
                    //마지막 Node 삭제 시 tail Node 지정(해당 if문 없을 경우 nullpointerexception 발생함)
                    if(node.next == null){
                        this.tail = node;
                    }else{
                        node.next.prev = node;
                    }
                    
                    return true;
                }
                node = node.next;
            }
            return false;
        }
    }
}