연결리스트 알고리즘

연결 리스트

자료 구조가 연결은 노드라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미한다.

연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함한다.

연결 구조의 다른예로는 트리와 그래프가 있다.

이때 노드는 둘 이상의 다른 노드에 대한 참조를 포함한다.

public class ListNode { public Object data; public ListNode next; public ListNode() { this.data = null; this.next = null; } public ListNode(Object data) { this.data = data; this.next = null; } public ListNode(Object data, ListNode next) { this.data = data; this.next = next; } public String toString() { return "ListNode(" + data.toString() + ")"; } }

설명

ListNode 객체에는 두개의 인스턴스 변수가 있다.

data 변수는 어떤 Object에 대한 참조

next 변수는 리스트에서 다음 노드에 대한 참조

리스트의 마지막 노드에서 관례상 next 변수는 null이다.

각 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);

마지막 노드에서는 next 필드가 null이다.