링크드 리스트 (Linked List) - 2

더블 링크드 리스트(Doubly linked list)

이중 연결 리스트
양방향으로 연결되있어, 탐색이 양쪽으로 가능함

 

Doubly-linked-list - Linked list - Wikipedia

 

더블 링크드 리스트 구현

public class DoubleLinkedList<T> {
    public Node<T> head = null;
    puclic 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 add(T data) {
        if(this.head == null) {
            this.head = new Node<T>(data);
            thus.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 getList() {
        if(this.head != null) {
            Node<T> node = this.head;
            System.out.print(node.data + " ");
           
            while(node.next != null) {
                node = node.next;
                System.out.print(node.data + " ");
            }
            System.out.println();
        }
    }
    
    /*
    * 앞에서 찾기
    */
    public T searchNodeFromHead(T searchData) {
        if(this.head == null) {
            return null;
            
        } else {
            Node<T> node = this.head;
            while(node != null) {
            	if(node.data == searchData) {
                    return node.data;
                    
                } else {
                    // 앞쪽에서 뒤쪽으로 찾는거라 next
                    node = node.next;
                }
            }
            return null;
        }
    }
    
    /*
    * 뒤에서 찾기
    */
    public T searchNodeFromTail(T searchData) {
        if(this.head == null) {
            return null;
            
        } else {
            Node<T> node = this.tail;
            while(node != null) {
                if(node.data == searchData) {
                    return node.data;
                    
                } else {
                    // 뒤쪽에서 앞쪽으로 찾는거라 prev
                    node = node.prev;
                }
            }
            return null;
        }
    }
    
    /*
    * 앞쪽에 데이터 추가 (다시 이해해야함)
    */
    public boolean addToFront(T searchData, T addData) {
        if(this.head == null) {
            this.head = new Node<T>(addData);
            this.tail = this.head;
            return true;
            
        } else if(this.head.data == searchData) {
            Node<T> newHead == new Node<T>(addData);
            newHead.next = this.head;
            
            this.head = newHead;
            this.head.next.prev = this.head;
            return true;
            
        } else {
            Node<T> node = this.head;
            while(node != null) {
                if(node.data == searchData) {
                    Node<T> nodePrev = node.prev;
                    
                    nodePrev.next = new Node<T>(searchData);
                    nodePrev.next.next = node;
                    
                    nodePrev.next.prev = nodePrev;
                    node.prev = nodePrev.next;
                    return true;
                    
                } else {
                    node = node.next;
                }
            }
            return false;
        }
    }
}

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

// 추가
dLinkedList.add(1);
dLinkedList.add(2);
dLinkedList.add(3);
dLinkedList.add(4);
dLinkedList.add(5);

dLinkedList.getList();    // 1 2 3 4 5

// head/tail 부터 찾기
dLinkedList.searchNodeFromHead(3);	// 3
dLinkedList.searchNodeFromTail(1);	// 1
dLinkedList.searchNodeFromTail(7);	// null

// 앞쪽 추가
dLinkedList.addToFront(2, 6);
dLinkedList.getList();		// 1 6 2 3 4 5

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스