연결 자료구조 & 객체 다이어그램

>>>>>>> 소스코드.git

자료구조가 연결되었다 함은 노드(node)라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미한다. 연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함한다. 연결 구조의 다른 예로는 트리와 그래프가 있다. 이때 노드는 둘 이상의 다른 노드에 대한 참조를 포함한다.

 

다음은 간단한 노드에 대한 클래스의 정의이다. (ListNode.java)

public class ListNode {

    public Object cargo;
    public ListNode next;

    public ListNode() {
        this.cargo = null;
        this.next = null;
    }

    public ListNode(Object cargo) {
        this.cargo = cargo;
        this.next = null;
    }

    public ListNode(Object cargo, ListNode next) {
        this.cargo = cargo;
        this.next = next;
    }

    public String toString() {
        return "ListNode(" + cargo.toString() + ")";
    }
}

ListNode 객체에는 두 개의 인스턴스 변수가 있다. cargo 변수는 어떤 Object에 대한 참조고, next 변수는 리스트에서 다음 노드에 대한 참조이다. 리스트의 마지막 노드에서 관례상 next 변수는 null이다.

 

ListNode 클래스는 cargo와 next 값을 제공하거나 기본값인 null로 초기화하는 몇개의 생성자를 제공한다.

 

각 ListNode 객체는 단일 요소를 가진 리스트로 생각할 수 있지만, 좀 더 일반적으로 리스트는 다수의 노드를 포함할 수 있다. 새로운 리스트를 만드는 몇 가지 방법이 있다. 다음과 같이 간단히 ListNode 객체들의 집합을 생성한다.

ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

그리고 이것들을 연결한다.

node1.next = node2;
node2.next = node3;
node3.next = null;

아니면 노드와 링크를 동시에 생성할 수도 있다. 예를 들어, 리스트 시작에 새로운 노드를 추가하려면 다음과 같이 한다.

ListNode node0 = new ListNode(0, node1);

일련의 작업을 수행하고 나면 데이터로 정수 0, 1, 2, 3이 들어 있는 노드들이 오름차순으로 연결되었음을 알 수 있다. 마지막 노드에서 next 필드는 null이다.

 

다음 그림은 이러한 변수와 변수가 참조하는 객체를 보여주는 객체 다이어그램이다. 다이어그램에서 변수는 상자 안에 이름이 있고 참조 방향을 화살표로 나타낸다. 객체는 상자 밖에 Listnode와 Integer처럼 타입을, 상자 안에 인스턴스 변수를 표기한다.

연결 리스트의 객체 다이어그램