Linked List

Linked List란?

• 배열의 한계를 극복하기 위한 자료구조
• 노드(하나의 데이터) 생성 시, 데이터와 다음 데이터의 주소를 담을 공간을 만든다.
  - 노드(Node) : 데이터의 저장 단위로 데이터 값과 포인터로 구성된다.
  • 포인터(Pointer) : 각 노드 안에서, 이전 또는 다음 노드와의 연결 정보를 담는 공간이다.

Linked List의 특징

• 데이터의 순서가 존재한다.
• 배열이나 스택의 경우 데이터의 길이를 미리 정해놔야하지만, Linked List의 경우 데이터가 늘어날 경우 자동으로 길이가 늘어난다.
• k번째 원소를 확인/변경하기 위해 O(k)가 필요하다.
• 임의의 위치에 원소를 추가/제거를 위해 O(1)이 필요하다. (단, 추가/제거할 위치의 주소값을 알고 있을 경우에만)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다.

Linked List의 장단점

장점

1. 데이터 공간을 미리 할당하지 않다도 된다.

단점

1. 노드 생성 시 데이터 공간과 함께 다음 데이터의 공간이 필요하여, 저장공간 효율이 높지 않다.
2. 데이터 검색 시 가장 앞의 데이터부터 순자척으로 검색하므로 속도가 느리다.
3. 데이터 핸들링 시 전, 후 데이터까지 변동하는 작업이 필요하다.

Linked List 구현

Node 구현

	// Node 클래스 구현
    public static class Node<T> {
        T data;
        Node<T> next = null;

        public Node(T data) {
            this.data = data;
        }
    }
    
    public static void main(String[] args) {
    
        System.out.println("======================== Node 선언 ========================");

        // Node 선언
        Node<Integer> node1 = new Node<Integer>(1);
        Node<Integer> node2 = new Node<Integer>(2);

        // 첫번째 노드
        Node head = node1;
        // 두번째 노드의 정보를 저장
        head.next = node2;

        System.out.println(head.data);			// 1
        System.out.println(head.next);			// LinkedListOperation$Node@6a5fc7f7
        System.out.println(head.next.data);		// 2
	}

Node 클래스를 사용하여 Linked List 구현

// SingleLinkedList 구현
    public static class SingleLinkedList<T> {
        public Node<T> head = null;

        // Node 추가 메소드
        public void addNode(T data) {
            if(head == null) {
                head = new Node<T>(data);
            } else {
                Node<T> node = this.head;
                while(node.next != null) {
                    node = node.next;
                }
                node.next = new Node<T>(data);
            }
        }

        // Node 출력 메소드
        public void printAll() {
            String str = "";

            if(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) {
        
        System.out.println("======================== LinkedList 선언 ========================");

        // SingleLinkedList 선언
        SingleLinkedList<Integer> linkedList = new SingleLinkedList<Integer>();
        
        // linkedList에 node 추가
        linkedList.addNode(1);
        System.out.println(linkedList.head.data);		// 1
        
        linkedList.addNode(2);
        System.out.println(linkedList.head.next);		// LinkedListOperation$Node@1e643faf
        System.out.println(linkedList.head.next.data);	// 2

        System.out.println("");
        System.out.println("======================== LinkedList 출력 ========================");

        // LinkedList 데이터 출력
        SingleLinkedList<Integer> LinkedList2 = new SingleLinkedList<Integer>();

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

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