선형 리스트 단점 1. 쌓이는 데이터의 크기를 미리 알아야 함 2. 밀거나 당겨야 하기 때문에 효율이 좋지 않음
연결 리스트 - 포인터
head ▲ ▲ tail
연속된 노드의 결정체
자신과 같은 자료형의 인스턴스를 가리킴, 자기 참조(self-referential)형
클래스형 변수인 data는 데이터 그 자체가아니라 데이터에 대한 참조
꼬리 노드의 뒤쪽 포인터 값을 null을 참조
package chap09_1;
public class LinkedList<E> {
//노드
class Node<E> {
private E data; //데이터
private Node<E> next; //뒤쪽 포인터(다음 노드 참조)
//생성자 - 인수로 전달받은 data, next를 해당 필드에 설정
public Node(E data, Node<E> next) {
super();
this.data = data;
this.next = next;
}
}
private Node<E> head; //머리 노드
private Node<E> crnt; //현재 선택한 노드, 검색한 노드를 선택하고, 삭제하는 등의 용도로 사용
}
노드 개수에 따른 상태
생성자 LinkedList
//생성자
public LinkedList() {
head = crnt = null;
}
머리 노드를 가리키는 변수 head에 null 대입
crnt에도 null을 넣어 어떤 요소도 선택하지 않도록 함
1. 연결 리스트가 비어있는지
head == null; //연결 리스트가 비어있는지 확인
2. 노드가 1개인 연결 리스트
head.next == null; //노드가 1개인지 확인
head가 가리키는 곳은 머리 노드 A(head.next)이고, 뒤쪽 포인터 값이 null이므로 위처럼 판단 가능
3. 노드가 2개인 연결 리스트
head.next.next == null; //노드가 2개인지 확인
머리 노드는 A(head.next), 꼬리 노드는 B(head.next.next)이고, head.next는 노드 B를 가리킴
꼬리 노드 B의 next는 null이기 때문에 위처럼 판단 가능
3. 꼬리 노드인지 판단
p.next == null; //p가 가리키는 노드가 꼬리 노드인지 확인
메서드
메서드
실행 후 선택 노드(crnt)가 가리키는 노드
조건
생성자
null
search
검색에 성공하면 검색한 노드
addFirst
삽입한 머리 노드
addLast
삽입한 꼬리 노드
리스트가 비어있으면
removeFirst
삭제 후 머리 노드 (리스트가 비어 있으면 null)
리스트가 비어있지 않으면
removeLast
삭제 후 꼬리 노드 (리스트가 비어 있으면 null)
리스트가 비어있지 않으면
remove
삭제한 노드의 앞쪽 노드
리스트가 비어있지 않으면
removeCurrentNode
삭제한 노드의 앞쪽 노드
clear
null
next
옮긴 후 선택 노드
결과 - false, true
printCurrentNode
업데이트X
dump
업데이트X
search
검색에 사용하는 알고리즘은 선형 검색
검색할 노드를 만날 때까지 머리 노드부터 스캔
조건 하나만 성립하면 종료 1. 검색 조건을 만족하지 못하고,꼬리 노드를 지나가기 직전인 경우 2. 검색 조건을 만족하는 노드를 찾은 경우
매개변수 2개 (obj, c) 1. obj : 검색할 key가 되는 데이터를 넣어둔 object 2. c : obj와 노드 안의 데이터를 비교하기 위한 comparator.comparator c에 의해 obj와 선택한 노드의 데이터를 비교하여 그 결과가 0이면 검색 조건이 성립하는 것으로 봄
//검색
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head; //현재 스캔 중인 노드
while(ptr != null) { //마지막 노드 직전까지
if(c.compare(obj, ptr.data) == 0) { //검색 성공
crnt = ptr;
return ptr.data;
}
ptr = ptr.next; //다음 노드 선택
}
return null;
}
스캔하는 노드를 가리키는 변수 ptr을 head(머리 노드 A)로 초기화
ptr == null 이면 스캔할 노드가 없으므로 while문을 빠져나옴
조건을 확인하기 위해 데이터 obj와 스캔하고 있는 노드의 데이터 ptr.data를 comparator c로 비교 성공: 0이면 성공, 선택 노드에 현재 스캔중인 노드를 대입하고 노드의 데이터 반환
조건에 맞지 않으면 ptr에 ptr.next를 대입하여 다음 노드 스캔
실패: return null;
addFirst, addLast - 머리, 꼬리에 노드 삽입
//머리에 노드 삽입
public void addFirst(E obj) {
Node<E> ptr = head; //삽입 전의 머리 노드(업데이트 하기 위해서)
head = crnt = new Node<E>(obj, ptr);
//삽입할 노드 생성 후
//생성한 노드를 참조하도록 head를 업데이트 함, 뒤쪽 포인터가 가리키는 곳은 ptr
//crnt도 새로 만든 노드를 가리키도록 업데이트
}
//꼬리에 노드 삽입
public void addLast(E obj) {
if(head == null) { //리스트가 비어있으면
addFirst(obj); //머리에 삽입
} else {
Node<E> ptr = head; //꼬리 노드를 찾기 위해 머리노드를 가리키도록 초기화한 ptr을
while(ptr.next != null) //뒤쪽 포인터 값이 null이 아니면 (=마지막 노드가 아님)
ptr = ptr.next; //다음 노드를 가리키도록 업데이트
ptr.next = crnt = new Node<E>(obj, null);
}
}
꼬리에 노드 삽입시 1. 리스트가 비어있는 경우 - head에 삽입, addFirst 메서드로 처리 2. 리스트가 비어있지 않은 경우 - 꼬리에 삽입
removeFirst, removeLast - 머리, 꼬리 노드 삭제
꼬리 노드 삭제 후 ptr의 참조를 해제하는 거라서 따로 없어지지는 않음
//머리 노드 삭제
public void removeFirst() {
if(head != null) //리스트가 비어있지 않으면
head = crnt = head.next;
}
//꼬리 노드 삭제
public void removeLast() {
if(head != null) { //리스트가 비어있지 않으면
if(head.next == null) //노드가 하나만 있으면
removeFirst(); //머리 노드 삭제
else {
//꼬리 노드, 꼬리 노드로부터 두번째 노드를 찾아야 함
Node<E> ptr = head; //현재 스캔 중인 노드
Node<E> pre = head; //현재 스캔 중인 노드의 앞쪽 노드
while(ptr.next != null) { //ptr이 마지막 노드가 아니면 다음 노드를 가리키도록 업데이트
pre = ptr;
ptr = ptr.next;
} //while 종료시 ptr은 꼬리 노드, pre는 꼬리로부터 두번째 노드
pre.next = null; //pre는 삭제 후의 꼬리 노드
crnt = pre; //crnt는 삭제 후의 꼬리노드 pre
}
}
}
꼬리 노드 삭제시 1. 노드가 하나만 있는 경우 - head 노드 삭제, removeFirst 메서드로 처리 2. 노드가 2개 이상 있는 경우 - 위의 코드 확인
remove - p노드 삭제
//p 노드 삭제
public void remove(Node p) {
if(head != null) { //리스트가 비어있지 않으면
if(p == head) { //p가 머리 노드이면
removeFirst(); //머리 노드 삭제
} else {
//p의 앞쪽 노드 찾기
Node<E> ptr = head; //현재 스캔 중인 노드
while(ptr.next != p) { //ptr의 뒤쪽 포인터가 p와 같을 때까지 반복
ptr = ptr.next;
if(ptr == null) return; //p가 리스트에 없으면 메서드 종료
}
ptr.next = p.next; //기존의 p다음 노드를 ptr의 다음 노드로 만들어주고, 참조되지 않은 노드의 메모리는 자동으로 해제
crnt = ptr; //현재 노드를 삭제한 노드의 앞 노드로 업데이트
}
}
}
특정 노드 삭제시 1. p가 머리 노드인 경우 - head 노드 삭제, removeFirst 메서드로 처리 2. p가 머리 노드가 아닌 경우 - 위의 코드 확인
removeCurrentNode
//선택 노드 삭제
public void removeCurrentNode() {
remove(crnt);
}
clear - 모든 노드 삭제
//모든 노드 삭제
public void clear() {
while(head != null) { //노드에 아무것도 없을 때까지
removeFirst(); //머리 노드 삭제
crnt = null; //리스트가 비어있으므로 crnt도 null로 업데이트
}
}
next
//선택 노드를 하나 뒤쪽으로 이동
public boolean next() {
if(crnt == null || crnt.next == null) { //리스트가 비어있거나 선택 노드의 뒤쪽 노트가 없으면
return false; //이동할 수 없음
}
crnt = crnt.next;
return true;
}
printCurrentNode
//선택 노드를 표시
public void printCurrentNode() {
if(crnt == null)
System.err.println("선택한 노드가 없습니다.");
else
System.err.println(crnt.data);
}
dump - 모든 노드 표시
//모든 노드를 표시
public void dump() {
Node<E> ptr = head;
while(ptr != null) {
System.out.println(ptr.data);
ptr = ptr.next;
}
//crnt 값을 업데이트 하지 않음, crnt는 메서드 실행 전 그대로임
}
purge - 서로 같은 노드 찾아서 모두 지우기
//서로 같은 노드를 찾아, 가장 앞쪽 노드를 남기고 모든 노드를 삭제해버림
public void purge(Comparator<? super E> c) { //비교할 값 = no 또는 name
Node<E> ptr = head;
while(ptr != null) { //마지막 노드 직전까지 반복
int count = 0;
Node<E> ptr2 = ptr; //비교할 ptr값인데 현재 노드로 초기화
Node<E> pre = ptr; //현재 노드의 앞쪽 노드
while(pre.next != null) { //현재 노드값(crnt, ptr)이 null이 아닐때까지 반복, 마지막까지
ptr2 = pre.next; //ptr하고, pre.next는 같은 값인데 변수명을 다르게
if(c.compare(ptr.data, ptr2.data) == 0) {
pre.next = ptr2.next;
count++; //지웠다고, 카운트 셈
} else { pre = ptr2; }
}
if(count == 0) { //같은 노드가 없으면
ptr = ptr.next;
} else { //같은 노드가 있었으면
Node<E> temp = ptr;
remove(ptr);
ptr = temp.next;
}
}
crnt = head;
}
retrieve - head부터 n개 뒤 노드의 데이터에 대한 참조
//머리부터 n개 뒤 노드의 데이터에 대한 참조를 반환
public E retireve(int n) {
Node<E> ptr = head;
while(n >= 0 && ptr != null) { //n은 양수, 노드에 값이 있음
if(n-- == 0) { //n번 반복(종료 조건은 n이 0이 될떄까지)
crnt = ptr; //현재 값이 ptr이 된 곳에서
return ptr.data; //data 리턴
}
ptr = ptr.next; //계속 넘기다가
}
return null;
}
package chap09_1;
import java.util.Comparator;
import chap09_1.LinkedList.Node;
public class LinkedListT<E> {
//노드
class Node<E> {
private E data;
private Node<E> next;
public Node(E data, Node<E> next) {
super();
this.data = data;
this.next = next;
}
}
//추가 노드
private Node<E> head; //머리노드
private Node<E> tail; //꼬리노드
private Node<E> crnt; //선택노드
public LinkedListT() {
super();
head = tail = crnt = null; //null로 초기화
}
//검색은 같음
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head = tail; //현재 스캔중인 노드
//ptr.next == null이면 꼬리였는데 지금은 ptr.next == tail 이면 꼬리임
while(ptr != null) { //마지막 노드 직전까지
if(c.compare(obj, ptr.data) == 0) { //검색 성공
crnt = ptr;
return ptr.data;
}
ptr = ptr.next;
}
return null;
}
//머리에 노드 삽입
public void addFirst(E obj) {
Node<E> ptr = head;
boolean empty = (tail == null); //비어있음
head = crnt = new Node<E>(obj, ptr); //머리에 삽입
if(empty) //꼬리에도 crnt 넣어줌
tail = crnt;
}
//질문 -> 이거 할 때 tail은 알아서 마지막을 잡고 있는 건가?
public void addLast(E obj) {
if(head == null) { //데이터가 없으면
addFirst(obj); //머리에 삽입
} else {
tail.next = crnt = new Node<E>(obj, null); //obj는 넣고, 그 뒤에 참조할 것은 없음
tail = crnt;
}
}
//머리 노드 삭제
public void removeFirst() {
if(head != null)
head = crnt = head.next; //head를 그 다음으로 옮기고
if(head == null) //그 값이 null이면
tail = null; //tail에도 null
}
//질문 -> 꼬리 노드 삭제
public void removeLast() {
if(head != null) {
if(head.next == null) //노드가 하나면
removeFirst(); //첫번째 노드 삭제
else {
Node<E> ptr = head;
Node<E> pre = head;
while(ptr.next != null) { //ptr이 마지막 노드가 아니면
pre = ptr;
ptr = ptr.next;
}
pre.next = null; //pre는 삭제 후의 꼬리
tail = crnt = pre; //꼬리에 pre, crnt 넣어줌.. 근데 head에는?
}
}
}
//p 노드 삭제
public void remove(Node p) {
if(head != null) {
if(p == head) { //p가 머리 노드이면
removeFirst(); //머리 노드 삭제
} else if(p == tail){ //p가 꼬리 노드이면
removeLast(); //꼬리 노드 삭제
} else { //그 외의 노드이면
Node<E> ptr = head;
while(ptr.next != p) { //ptr 다음 값이 p가 아닐때까지
ptr = ptr.next;
if(ptr == null)
return;
}
ptr.next = p.next; //ptr 다음값이 p이면, p의 다음값을 ptr 다음 값으로 만들고
crnt = ptr; //ptr을 현재값으로 만듦
}
}
}
////////////////////////////////////아래에는 tail 사용 안 함//////////////////////////////////
//선택 노드 삭제
public void removeCurrentNode() {
remove(crnt);
}
//모든 노드 삭제
public void clear() {
while(head != null) { //노드에 아무것도 없을 때까지
removeFirst(); //머리 노드 삭제
crnt = null; //리스트가 비어있으므로 crnt도 null로 업데이트
}
}
//선택 노드를 하나 뒤쪽으로 이동
public boolean next() {
if(crnt == null || crnt.next == null) { //리스트가 비어있거나 선택 노드의 뒤쪽 노트가 없으면
return false; //이동할 수 없음
}
crnt = crnt.next;
return true;
}
//선택 노드를 표시
public void printCurrentNode() {
if(crnt == null)
System.out.println("선택한 노드가 없습니다.");
else
System.out.println(crnt.data);
}
//모든 노드를 표시
public void dump() {
Node<E> ptr = head;
while(ptr != null) {
System.out.println(ptr.data);
ptr = ptr.next;
}
//crnt 값을 업데이트 하지 않음, crnt는 메서드 실행 전 그대로임
}
//머리부터 n개 뒤 노드의 데이터에 대한 참조를 반환
public E retireve(int n) {
Node<E> ptr = head;
while(n >= 0 && ptr != null) { //n은 양수, 노드에 값이 있음
if(n-- == 0) { //n번 반복(종료 조건은 n이 0이 될떄까지)
crnt = ptr; //현재 값이 ptr이 된 곳에서
return ptr.data; //data 리턴
}
ptr = ptr.next; //계속 넘기다가
}
return null;
}
}
연결 리스트 - 커서
포인터와 다르게 노드의 삽입, 삭제 시 요소를 옮길 필요가 없음
데이터 수의 최댓값을 미리 계산하여 모든 노드를 저장하기에 충분한 크기의 배열을 만들어야 함
Cursor(커서) - 포인터 역할, 다음 노드가 들어있는 요소의 인덱스 - head = 1 - 꼬리 노드의 커서 = -1 (인덱스로 있을 수 없는 값)
삽입한 노드는 배열 안에서 가장 꼬리 쪽에 들어가지만, 연결 리스트에서는 head 바로 다음으로 들어감
여기서 6은 인덱스 번호이고, G안에는 연결 리스트에서 다음에 나올 인덱스(1)가 들어감
삭제한 노드 관리
삽입한 노드는 배열 안에서 가장 꼬리 쪽에 있는 인덱스 위치에 들어가 있지만 연결 리스트의 꼬리에 추가한 것은 아님
배열 안에서의 물리적 위치 관계와 연결 리스트의 논리적인 순서 관계가 같지 않음
노드를 삭제하면 그 레코드가 비어있는 상태가 되므로 빈 레코드를 효율적으로 활용해야 함
이 그림 잘 해석하기
FreeList (프리 리스트)
삭제한 여러 레코드를 관리하기 위해 그 순서를 넣어두는 연결 리스트
별로도 선언된 변수가 아니며, deleted라는 변수가 freeList의 역할을 수행하는 것
freeList의 각 노드는 삭제된 노드의 인덱스와 다음 freeList 노드의 인덱스(dnext)를 저장
freeList의 head(여기서는 deleted)는 가장 최근에 삭제된 노드의 인덱스를 가리킴
삭제된 노드가 없는 경우, freeList의 head는 NULL 값을 가리킴
노드 클래스 Node<E>에 추가된 필드 dnext - 프리 리스트의 다음 노드를 가리키는 커서
연결 리스트 클래스 AryLinkedList<E>에 추가된 필드 deleted - 프리 리스트의 머리 노드를 가리키는 커서 max - 배열의 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호, 배열에서 가장 꼬리 인덱스
getInsertIndex - 다음에 삽인하는 노드의 인덱스 구하기
//다음에 삽입하는 record의 인덱스를 구함
private int getInsertIndex() {
if(deleted == NULL) { //deleted에서 삭제할 노드가 없음 = 삭제 리스트가 비어있거나 모든 노드가 사용중인 경우
if(max < size) //배열이 마지막 사용 인덱스보다 크다는 것은 아직 널널하다는 뜻
return ++max; //새 record를 사용
else
return NULL; //용량 넘침(over)
} else {
int rec = deleted; //free 리스트에서
deleted = n[rec].dnext; //머리 rec을 꺼냄
return rec;
}
}
deletedIndex - 삭제할 노드의 인덱스를 freeList에 등록
//삭제할 노드의 인덱스를 free 리스트에 등록
private void deleteIndex(int idx) {
if(deleted == NULL) { //deletd가 가리키는 노드 없음
deleted = idx; //idx를 free 리스트의
n[idx].dnext = NULL; //머리에 등록 = n[idx]의 다음 노드를 가리키는 포인터가 null 값을 가짐
} else {
int rec = deleted; //idx를 free리스트의
deleted = idx; //머리에 삽입
n[rec].dnext = rec;
//기존에 deleted가 가리키는 것을 rec에 넣고, idx를 deleted에 다음 노드는 rec를 가리킴
}
}
else 부분에 노드 D를 삭제할 때 idx = 7, deleted = 1이었을 때 rec = 1이 되고, deleted = 7이 되고, n[ rec = 1].next = 1; 이 왜그런가? n은 c그림에서 freeList까지 포함한 노드 n[rec].dnext = rec로 freeList에서 rec인덱스 노드의 필드에 자기 자신을 담아줌
package chap09_2;
import java.util.Comparator;
//외부 클래스
public class AryLinkedList<E> {
//연결 리스트 - 배열 커서 ver
//노드 - 중첩, 내부클래스, 캡슐화, 모듈화, 클래스들 간의 응집도 증가, 결합도 감소
class Node<E> { //각 요소를 표현하며 배열 n에 Node 객체를 저장하여 연결리스트 구성
private E data; //데이터
private int next; //다음 노드를 가키리는 포인터
private int dnext; //추가, free 리스트의 뒤쪽 포인터
//data와 next 설정
void set(E data, int next) {
this.data = data;
this.next = next;
}
}
//필드 = 멤버변수 = 전역변수
private Node<E>[] n; //리스트 본체
private int size; //리스트의 용량 (가장 큰 데이터 수)
private int max; //추가, 배열에서 꼬리 인덱스, 현재 사용중인 마지막 인덱스
private int head; //머리 노드
private int crnt; //선택 노드
private int deleted; //추가, free 리스트의 머리 노드
private static final int NULL = -1; //다음 노드 없음 / 리스트가 가득 참
//생성자
public AryLinkedList(int capacity) {
head = crnt = max = deleted = NULL;
try {
n = new Node[capacity];
for (int i = 0; i < capacity; i++) { //capacity 사이즈 만큼의 리스트 본체 생성하고
n[i] = new Node<E>(); //그 안에 노드 하나씩 생성
}
size = capacity;
} catch (OutOfMemoryError e) { //배열 생성에 실패
size = 0;
}
}
//다음에 삽입하는 record의 인덱스를 구함
private int getInsertIndex() {
if(deleted == NULL) { //deleted에서 삭제할 노드가 없음 = 삭제 리스트가 비어있거나 모든 노드가 사용중인 경우
if(max < size) //배열이 마지막 사용 인덱스보다 크다는 것은 아직 널널하다는 뜻
return ++max; //새 record를 사용
else
return NULL; //용량 넘침(over)
} else {
int rec = deleted; //free 리스트에서
deleted = n[rec].dnext; //머리 rec을 꺼냄
return rec;
}
}
//삭제할 노드의 인덱스를 free 리스트에 등록
private void deleteIndex(int idx) {
if(deleted == NULL) { //deletd가 가리키는 노드 없음
deleted = idx; //idx를 free 리스트의
n[idx].dnext = NULL; //머리에 등록 = n[idx]의 다음 노드를 가리키는 포인터가 null 값을 가짐
} else {
int rec = deleted; //idx를 free리스트의
deleted = idx; //머리에 삽입
n[rec].dnext = rec;
//기존에 deleted가 가리키는 것을 rec에 넣고, idx를 deleted에 다음 노드는 rec를 가리킴
}
}
//노드를 검색
public E search(E obj, Comparator<? super E> c) {
int ptr = head; //현재 스캔중인 노드
while(ptr != NULL) {
if(c.compare(obj, n[ptr].data) == 0) {
crnt = ptr;
return n[ptr].data; //검색 성공
}
ptr = n[ptr].next; //다음 노드에 주목
}
return null; //검색 실패
}
//머리에 노드를 삽입
public void addFirst(E obj) {
int ptr = head; //삽입 전의 머리 노드
int rec = getInsertIndex();
if(rec != NULL) {
head = crnt = rec; //인덱스 rec인 record에 삽입
n[head].set(obj, ptr);
}
}
//꼬리에 노드 삽입
public void addLast(E obj) {
if(head == NULL) //리스트가 비어 있으면
addFirst(obj); //머리에 삽입
else {
int ptr = head;
while(n[ptr].next != NULL) {
ptr = n[ptr].next;
}
int rec = getInsertIndex();
if(rec != NULL) { //인덱스 rec인 record에 삽입
n[ptr].next = crnt = rec;
n[rec].set(obj, NULL);
}
}
}
//머리 노드를 삭제
public void removeFirst() {
if(head != NULL) { //리스트가 비어있지 않으면
int ptr = n[head].next;
deleteIndex(head);
head = crnt = ptr;
}
}
//꼬리 노드를 삭제
public void removeLast() {
if(head != NULL) {
if(n[head].next == NULL) //노드가 하나면
removeFirst(); //머리 노드 삭제
else {
int ptr = head; //스캔 중인 노드
int pre = head; //ptr의 앞쪽 노드
while(n[ptr].next != NULL) {
pre = ptr;
ptr = n[ptr].next;
}
n[pre].next = NULL; //pre는 삭제 후의 꼬리 노드
deleteIndex(pre);
crnt = pre;
}
}
}
//record p를 삭제
public void remove(int p) {
if(head != NULL) {
if(p == head) //p가 머리 노드이면
removeFirst();
else {
int ptr = head;
while(n[ptr].next != p) {
ptr = n[ptr].next;
if(ptr == NULL) return; //p가 리스트에 없습니다.
}
n[ptr].next = NULL;
deleteIndex(ptr);
n[ptr].next = n[p].next;
crnt = ptr;
}
}
}
//선택 노드를 삭제
public void removeCurrentNode() {
remove(crnt);
}
//모든 노드를 삭제
public void clear() {
while(head != NULL) //텅 빌 때까지
removeFirst(); //머리 노드를 삭제
crnt = NULL;
}
//선택 노드를 하나 뒤쪽으로 이동
public boolean next() {
if(crnt == NULL || n[crnt].next == NULL)
return false; //이동할 수 없음
crnt = n[crnt].next;
return true;
}
//선택 노드를 출력
public void printCurrentNode() {
if(crnt == NULL)
System.out.println("선택 노드가 없습니다.");
else
System.out.println(n[crnt].data);
}
//모든 노드를 출력
public void dump() {
int ptr = head;
while(ptr != NULL) {
System.out.println(n[ptr].data);
ptr = n[ptr].next;
}
}
}
AryLinkedListTester
package chap09_2;
import java.util.Comparator;
import java.util.Scanner;
import chap09_1.LinkedListTester.Menu;
//연결 리스트 클래스 AryLinkedList<E> 사용 예시
public class AryLinkedListTester {
static Scanner scan = new Scanner(System.in);
//데이터 (회원번호 + 이름), 내부 클래스
static class Data {
static final int NO = 1; //번호를 입력받습니까?
static final int NAME = 2; //이름을 입력받습니까?
private Integer no; //회원번호
private String name; //이름
@Override
public String toString() {
return "data [no=" + no + ", name=" + name + "]";
}
//데이터를 입력
void scanData(String guide, int sw) {
System.out.println(guide + "할 데이터르 입력하세요.");
if((sw & NO) == NO) {
System.out.println("번호: ");
no = scan.nextInt();
}
if((sw & NAME) == NAME) {
System.out.println("이름: ");
name = scan.next();
}
}
//회원번호 순서를 매기는 comparator - 숫자
public static final Comparator<Data> NO_ORDER = new NoOrderComparator();
private static class NoOrderComparator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return (d1.no > d2.no) ? 1 : (d1.no < d2.no) ? -1 : 0;
}
}
//이름 순서를 매기는 comparator - 문자
public static final Comparator<Data> NAME_ORDER = new NameOrderCompator();
private static class NameOrderCompator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return d1.name.compareTo(d2.name);
}
}
} //end Data
//메뉴 열거형
enum Menu {
ADD_FIRST("머리에 노드를 삽입"),
ADD_LAST("꼬리에 노드를 삽입"),
RMV_FIRST("머리 노드를 삭제"),
RMV_LAST("꼬리 노드를 삭제 "),
RMV_CRNT("선택 노드를 삭제 "),
CLAER("모든 노드를 삭제 "),
SEARCH_NO("번호로 검색 "),
SEARCH_NAME("이름으로 검색 "),
NEXT("선택 노드로 이동"),
PRINT_CRNT("선택 노드를 출력 "),
DUMP("모든 노드를 출력 "),
TERMINATE("종료");
private final String message; //출력할 문자열
static Menu MenuAt(int idx) { //서수가 idx인 열거를 반환
for(Menu m : Menu.values())
if(m.ordinal() == idx)
return m;
return null;
}
Menu(String string) { //생성자
message = string;
}
String getMessage() { //출력할 문자열을 반환
return message;
}
} //end enum
//메뉴 선택
static Menu SelectMenu() {
int key;
do {
for(Menu m : Menu.values()) {
System.out.printf("(%d) %9s ", m.ordinal(), m.message);
if((m.ordinal() % 3) == 2 &&
m.ordinal() != Menu.TERMINATE.ordinal() )
System.out.println();
}
System.out.print(" : ");
key = scan.nextInt();
} while (key < Menu.ADD_FIRST.ordinal() || key > Menu.TERMINATE.ordinal());
return Menu.MenuAt(key);
}
//main
public static void main(String[] args) {
Menu menu; //메뉴
Data data; //추가용 데이터 참조
Data ptr; //검색용 데이터 참조
Data temp = new Data(); //입력용 데이터
AryLinkedList<Data> list = new AryLinkedList<Data>(100);
do {
System.out.println();
switch (menu = SelectMenu()) {
case ADD_FIRST : //머리에 노드 삽입
data = new Data();
data.scanData("머리에 삽입", Data.NO | Data.NAME);
list.addFirst(data);
break;
case ADD_LAST : //꼬리에 노드를 삽입
data = new Data();
data.scanData("꼬리에 삽입", Data.NO | Data.NAME);
list.addLast(data);
break;
case RMV_FIRST : //머리 노드를 삭제
list.removeFirst();
break;
case RMV_LAST : //꼬리 노드를 삭제
list.removeLast();
break;
case RMV_CRNT : //선택 노드를 삭제
list.removeCurrentNode();
break;
case SEARCH_NO : //회원번호로 검색
temp.scanData("검색", Data.NO);
ptr = list.search(temp, Data.NO_ORDER);
if(ptr == null)
System.out.println("그 번호의 데이터가 없습니다.");
else
System.out.println("검색 성공: " + ptr);
break;
case SEARCH_NAME : //이름으로 검색
temp.scanData("검색", Data.NAME);
ptr = list.search(temp, Data.NAME_ORDER);
if(ptr == null)
System.out.println("그 이름의 데이터가 없습니다.");
else
System.out.println("검색 성공: " + ptr);
break;
case NEXT : //선택 노드를 뒤쪽으로 이동
list.next();
break;
case PRINT_CRNT : //선택 노드의 데이터를 출력
list.printCurrentNode();
break;
case DUMP : //모든 노드를 리스트 순서로 출력
list.dump();
break;
case CLAER : //모든 노드 삭제
list.clear();
break;
}
} while (menu != Menu.TERMINATE);
} //end main
}
원형 이중 연결 리스트
원형 리스트 + 이중 연결 리스트
원형 리스트 - 연결 리스트의 꼬리 노드가 머리 노드를 가리키는 리스트 - 꼬리 노드의 다음 노드를 가리키는 포인터가 null이 아니라 head임 - 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조
이중 연결 리스트 - 앞쪽의 노드를 찾기 힘든 연결 리스트의 단점을 개선한 자료구조 - 각 노드에 다음 노드에 대한 포인터 + 앞쪽 노드에 대한 포인터를 가지고 있음 - Node<E> prev; //머리 노드를 가리킴 (추가)
구현
package chap09_4;
//원형 이중 연결 리스트 클래스
public class DblLinkedList<E> { //<E> 꼭 넣어줘야 함
//노드
class Node<E> {
private E data;
private Node<E> prev; //앞쪽 포인터
private Node<E> next; //뒤쪽 포인터
//생성자
public Node() {
super();
data = null; //데이터 없음
prev = next = this; //현재값 위치
}
//생성자
public Node(E obj, Node<E> prev, Node<E> next) {
super();
this.data = obj;
this.prev = prev;
this.next = next;
}
} //end Node<E> class
private Node<E> head; //머리 노드(더미 노드는 자기 자신을 가리킴)
private Node<E> crnt; //선택 노드
//생성자
public DblLinkedList() {
super();
head = crnt = new Node<E>(); //더미 노드를 생성, prev.next = this
}
//리스트가 비어있는가?
public boolean isEmpty() {
return head.next == head; //true이면 비어있음, head 다음이 head
}
}
Node<E>
자기 자신의 노드가 앞쪽 노드이면서 동시에 다음 노드, prev = next = this
data = obj, this.prev = prev, this.next = next 인 생성자
DblLinkedList<E>
head(더미노드), crnt 노드를 가짐
DblLinkedList<E> 생성자
데이터를 갖지 않는 노드를 1개 만듦 = head
더미 노드는 노드의 삽입과 삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 노드
isEmpty
리스트가 비어있는지 확인하는 메서드
비어있으면 head, head.next, head.prev가 가리키는 곳이 모두 더미 노드이므로 모두 head가 됨
search
//검색 - 검색의 시작은 head.next
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head.next; //현재 스캔중인 노드, 처음에는 검색의 시작
while(ptr != head) { //리스트가 있으면 반복
if(c.compare(obj, ptr.data) == 0) { //비교했을 때 같으면
crnt = ptr; //선택 노드는 ptr
return ptr.data; //검색 성공
}
ptr = ptr.next; //같지 않으면 다음 노드로 선택
}
return null; //끝까지 찾아도 없으면 검색 실패
}
head는 더미노드이므로, 검색의 시작은 head.next
while 조건에서 ptr == head 이면 더미 노드이므로 빈 리스트임 = while문 실행하지 않고 null 반환 후 메서드 종료
p가 가리키는 노드의 위치를 판단
dump에서 사용
printCurrentNode
//선택 노드를 출력
public void printCurrentNode() {
if(isEmpty())
System.out.println("선택한 노드가 없습니다.");
else
System.out.println(crnt.data); //crnt = 선택 노드 출력
}
dump + dumpReverse (모든 노드 출력)
//모든 노드를 출력
public void dump() {
Node<E> ptr = head.next; //더미 노드의 다음 노드
while(ptr != head) { //리스트가 있으면 + 한바퀴 돌아서 head로 돌아오면 스캔 끝
System.out.println(ptr.data);
ptr = ptr.next;
}
}
//모든 노드를 거꾸로 출력
public void dumpReverse() {
Node<E> ptr = head.prev; //더미 노드의 앞쪽 노드
while(ptr != head) {
System.out.println(ptr.data);
ptr = ptr.prev;
}
}
next, prev - 선택 노드를 뒤쪽, 앞쪽으로 이동
//선택 노드를 하나 뒤쪽으로 이동
public boolean next() {
if(isEmpty() || crnt.next == head) //비어있지 않고, 선택 노드의 뒤쪽 노드가 있을 때만 이동 가능
return false; //이동할 수 없음
else {
crnt = crnt.next;
return true;
}
}
//선택 노드를 하나 앞쪽으로 이동
public boolean prev() {
if(isEmpty() || crnt.prev == head) //비어있지 않고, 선택 노드의 앞쪽 노드가 있을 때만 이동 가능
return false; //이동할 수 없음
else {
crnt = crnt.prev;
return true;
}
}
add
//선택 노드의 바로 뒤에 노드를 삽입
public void add(E obj) {
//새로운 노드 생성
//생성자는 Node(E obj, Node<E> prev, Node<E> next), 객체, 앞쪽노드, 뒤쪽노드
Node<E> node = new Node<E>(obj, crnt, crnt.next);
//들어갈 노드의 앞쪽 포인터와 뒤쪽 포인터가 전부 들어갈 노드를 가리키도록 업데이트
crnt.next = crnt.next.prev = node; //crnt = B 였고, crnt.next = node 로 업데이트 / crnt.next = C 였고, crnt.next.prev = node 로 업데이트
crnt = node; //현재 선택 노드는 삽입한 노드
}
리스트의 머리에 더미 노드가 있으므로 비어있는 리스트에 삽입하거나 리스트의 머리에 삽입하는 것을 특별히 따로 다룰 필요 없음 삽입전의 crnt와 head는 모두 더미 노드를 가리키고 있으므로
1. 생성한 노드의 앞쪽 포인터와 뒤쪽 포인터는 더미 노드를 가리킴 2. 더미 노드의 뒤쪽 포인터와 앞쪽 포인터가 가리키는 곳은 노드 A 3. 선택 노드가 가리키는 곳은 삽입한 노드가 됨
addFirst, addLast
//머리에 노드 삽입
public void addFirst(E obj) {
crnt = head; //더미 노드 head의 바로 뒤에 삽입하므로 선택 crnt가 가리키는 곳을 head로 업데이트
add(obj); //add() 메서드 호출
}
//꼬리에 노드 삽입
public void addLast(E obj) {
crnt = head.prev; //더미 노드 head의 바로 앞에 삽입하므로 선택 crnt가 가리키는 곳을 head.prev로 업데이트
add(obj);
}
