[자바 Do It! 알고리즘]Chapter08 리스트(포인터로 연결 리스트 만들기)

[포인터로 연결 리스트 만들기]

1. 연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 삽입,삭제 시 모든 데이터를 밀고 당기는 문제를 해결할 수 있습니다.

class Node<E> {

E data; // 데이터

Node<E> next; // 다음 노드를 가리키는 포인터

}

2. 데이터용 필드인 data와는 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 가집니다. 일반적으로 이런 클래스 구조를 자기 참조(self-referential)형이라고 합니다.

3. Node<E>는 제네릭으로 구현되므로 데이터 형 E는 임의의 클래스형이 허용됩니다.

4. 필드 data 형인 E는 참조형입니다.

노드 형이 클래스 Node<E> 형인 연결 리스트를 클래스 LinkedList<E>로 구현한 프로그램

노드 클래스 Node<E>

data : 데이터를 가리킵니다.

next : 다음 노드를 가리키는 포인터입니다.

생성자 : Node<E>의 생성자는 인수로 전달받은 data, next를 해당 필드에 설정합니다.

​

연결리스트 클래스 LinkedList<E>

head : 머리 노드를 가리킵니다.

crnt : 현재 선택한 노드를 가리킵니다. "검색"한 노드를 선택하고 "삭제"하는 등의 용도로 사용합니다.

​

생성자 LinkedList

클래스 LinkedList<E>의 생성자는 머리 노드를 가리키는 변수 head에 null을 대입합니다.

그 결과 노드가 하나도 없는 비어 있는 연결리스트가 생성됩니다.

​

(뒷내용은 내일하겠습니다.)