Java LinkedList - 노드 연결 1

이전에 List 직접 구현한 것을 떠올려보자.
배열 리스트의 내부에 배열을 사용해 보관하고 관리 도중에 단점이 몇 가지 발견되었다.

배열 크기를 정의하고 사용하지 않는 낭비

+---+---+---+---+---+
| a |   |   |   |   |
+---+---+---+---+---+
0   1   2   3   4

배열의 크기를 미리 확보한다.
남은 공간에서 데이터가 얼마나 필요한지 예측할 수 없을 때 비어있는 공간을 낭비하고 있다.

배열 중간에 데이터 삽입으로 인한 데이터 이동 - 성능 하락

1. add(0, "h")
  h
  ↓
+---+---+---+---+---+
| a |   |   |   |   |
+---+---+---+---+---+

2. add() Complate
+---+---+---+---+---+
| h | a |   |   |   |
+---+---+---+---+---+

노드와 연결

배열 리스트를 문제를 대체할만한 자료구조로 노드 클래스를 사용한다.

노드 클래스

낭비되는 메모리 없이 필요한 만큼 메모리를 확보해 사용
앞이나 중간 데이터 추가 및 삭제에도 효율적인 구조로 사용

직접 구현해보도록 한다.

Node.class

public class Node {
    Object item;
    Node next;
}

노드 클래스는 내부 저장할 데이터로 item 필드 선언
다음 노드로 가리키는 next 필드 선언

노드 클래스를 이용해 A, B, C 순서대로 연결 예시

노드 데이터 A 추가

+-----------------+
| +------+------+ |
| | "A"  | null | |
| +------+------+ |
| item   next     |
+-----------------+
x001

노드 객체 선언과 동시에 item 필드의 값으로 "A" 데이터를 입력한다.

노드 데이터 B 추가

Node 0               Node 1
+-----------------+  +-----------------+
| +------+------+ |  | +------+------+ |  
| | "A"  | x002 | |  | | "B"  | null | |
| +------+------+ |  | +------+------+ |
| item   next     |  | item   next     |
+-----------------+  +-----------------+
x001                 x002

Node 1 인스턴스를 생성하고 item 에 "B" 로 넣어준다.
처음 만든 노드 Node 0의 next 필드 값으로 Node 1 참조 값을 기입한다.
첫 번째 노드와 두 번째 노드와 서로 연결한다.
첫 번째 노드에서 node.next 호출 시 두 번째 노드의 객체를 구할 수 있다.

노드 데이터 C 추가

Node 0               Node 1               Node 2
+-----------------+  +-----------------+  +-----------------+
| +------+------+ |  | +------+------+ |  | +------+------+ |  
| | "A"  | x002 | |  | | "B"  | null | |  | | "C"  | null | |
| +------+------+ |  | +------+------+ |  | +------+------+ |
| item   next     |  | item   next     |  | item   next     |
+-----------------+  +-----------------+  +-----------------+
x001                 x002                 x003

Node2 객체 인스턴스를 생성한 다음 item 값으로 "C" 기입한다.
두 번째 노드의 next 참조 값으로 세 번째 노드를 참조한다.
두 번째 노드와 세 번째 노드와 서로 연결된다.
첫 번째 노드로 node.next 호출 시 두 번째 노드를 구할 수 있다.
두 번째 노드로 node.next 호출 시 세 번째 노드를 구할 수 있다.
첫 번째 노드로 node.node.next 호출 시 세 번째 노드를 구할 수 있다.

노드 연결 실습

간단한 실습 형태로 진행한다.

Node.class 다시 작성

public class Node {
    Object item;
    Node next;

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

필드의 접근 제어자는 private 선언이 좋으나, 이 예제에서는 디폴트 접근 제어자로 사용하였다.
간단한 실습 용도의 생성자로 만들어 item 객체 생성 시 바로 item으로 할당한다.

Main.class

public class Main {
    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.item = " + first.item);
        System.out.println("first.next.item = " + first.next.item);
        System.out.println("first.next.next.item = " + first.next.next.item);
    }
}

노드 탐색하기
first.item = A
first.next.item = B
first.next.next.item = C

위의 그림과 같이 메인에서 노드들을 호출하도록 하였다.

node.next .. 형태로 호출하는 것이 익숙하지 않다면 다음과 같이 순회하면서 호출하는 방법도 있다.

Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");

Node n = first;
while (n != null) {
    System.out.println(n.item);
    n = n.next;
}

A
B
C

Node n 의 처음 노드부터 순서대로 이동하며 모든 노드를 가리키도록 순회한다.
어떤 의미냐면 n의 참조는 first 객체의 참조한다. while 문 통해서 n.next 참조 값을 찾게되고 item를 출력한다. 그리고 빠져나올 때는 n.next 값이 null인 경우 반복문에서 탈출하게 된다.

Main 반복 실행의 코드 분석

Node n = x001(first)
1. n.item 출력 요청 -> "A" 콘솔 출력
2. n = n.next(x002) -> n의 참조를 다음 노드로 할당
Node n = x002(n.next)
1. n.item 출력 요청 -> "B" 콘솔 출력
2. n = n.next(x003) -> n의 참조를 다음 노드로 할당
Node n = x003(n.next)
1. n.item 출력 요청 -> "C" 콘솔 출력
2. n = n.next(null) -> 다음 노드가 없으므로 while 문 종료함