[Java 복습] 노드란? 노드 연결, 기능구현 해보기

배열 리스트의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.

이로 인해 다음과 같은 단점을 가진다.

• 배열의 사용하지 않는 공간 낭비
• 배열의 중간에 데이터 추가

 

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 

삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

 

노드 클래스

public class Node {
    Object item;
    Node next;
}

• 노드 클래스는 내부에 저장할 데이터인 item 과, 다음으로 연결할 노드의 참조인 next 를 가진다.
• 이 노드 클래스를 사용해서 데이터 A, B, C를 순서대로 연결해보자.

public class Node {

    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }
}

public class NodeMain1 {

    public static void main(String[] args) {
        // 노드 생성하고 연결하기: A-> B -> C
        Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("C");

        System.out.println("모든 노드 탐색하기");
        Node x = first;
        while (x != null) {
            System.out.println(x.item);
            x = x.next;
        }
    }
}

모든 노드 탐색하기
A
B
C

 

 

 

Node x 는 처음 노드부터 순서대로 이동하면서 모든 노드를 가리킨다. 처음에 Node x 는 x01 을 참조한다. 

그리고 while 문을 통해 반복해서 다음 노드를 가리킨다. while 문은 다음 노드가 없을 때 까지 반복한다. 

Node.next 의 참조값이 null 이면 노드의 끝이다.

 

노드끼리 연결 해보고 기능 만들기

public class NodeMain3 {

    public static void main(String[] args) {
        // 노드 생성하고 연결하기: A-> B -> C
        Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("C");

        System.out.println("연결된 노드 출력하기");
        System.out.println(first);
        
        // 모든 노드 탐색하기
        System.out.println("모든 노드 탐색하기");
        printAll(first);
        
        // 마지막 노드 조회하기
        Node lastNode = getLastNode(first);
        System.out.println(lastNode);
        
        // 특정 인덱스의 노드 아이템 조회하기
        int index = 1;
        Node indexNode = getNode(first, index);
        System.out.println(indexNode.item);
        
        // 데이터 추가하기
        System.out.println("데이터 추가하기");
        add(first, "D");
        System.out.println(first);

        add(first, "E");
        add(first, "F");
        System.out.println(first);

    }

    private static void printAll(Node node) {
        Node x = node;
        while (x != null) {
            System.out.println(x.item);
            x = x.next;
        }
    }

    private static Node getLastNode(Node node) {
        Node x = node;
        while (x.next != null) {
            x = x.next;
        }
        return x; // x.next가 null
    }

    private static Node getNode(Node node, int index) {
        Node x = node;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    private static void add(Node node, String param) {
        Node lastNode = getLastNode(node);
        lastNode.next = new Node(param);
    }
}

연결된 노드 출력하기
[A->B->C]
모든 노드 탐색하기
A
B
C
[C]
B
데이터 추가하기
[A->B->C->D]
[A->B->C->D->E->F]

 

 

정리

• 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
• 지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결(Link, 링크) 되어 있다.
• 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 
• 따라서 배열과 다르게 메모리를 낭비하지 않는다.
• 물론 next 필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
• 이렇게 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라 한다.

 

 

연결 리스트 구현해보기

노드와 연결 구조를 통해서 리스트를 만들어보자. 이런 자료 구조를  링크드 리스트, 연결 리스트( LinkedList )라 한다. 

연결 리스트는 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능 문제를 어느정도 극복할 수 있다.

 

 

리스트 자료 구조

배열 리스트도, 연결 리스트도 모두 같은 리스트이다.

리스트의 내부에서 배열을 사용하는가 아니면 노드와 연결 구조를 사용하는가의 차이가 있을 뿐이다.
배열 리스트를 사용하든 연결 리스트를 사용하든 둘다 리스트 자료 구조이기 때문에 리스트를 사용하는 개발자 입장에서는 거의 비슷하게 느껴져야 한다. 다음에는 연결 리스트를 구현해보겠다.