Linked List - 3

Doubly linked list

1. 하나의 노드에 이전 데이터를 가리키는 포인터와 데이터, 이후 데이터를 가리키는 포인터로 이루어져있다.
2. single linked list는 head에서부터 순차적으로 검색해야하지만, double linked list의 경우 head 또는 tail에서부터 검색할 수 있으므로 상대적으로 효율적으로 사용될 수 있다.

doubly linked list 선언

	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 static void main(String[] args) {
        // DoubleLinkedList 선언
        System.out.println("");
        System.out.println("======================== DoubleLinkedList 선언 ========================");

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

        // DoubleLinkedList에 node 추가
        doubleLinkedList.addNode(1);
        System.out.println(doubleLinkedList.head.data);			// 1

        doubleLinkedList.addNode(2);
        System.out.println(doubleLinkedList.head.next);			// $Node@1324409e
        System.out.println(doubleLinkedList.head.next.data);	// 2

        // DoubleLinkedList에 데이터 출력
        System.out.println("");
        System.out.println("======================== DoubleLinkedList 출력 ========================");

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

        doubleLinkedList2.addNode(1);
        doubleLinkedList2.addNode(2);
        doubleLinkedList2.addNode(3);

        doubleLinkedList2.printAll();	// 1, 2, 3
	}