9. 리스트(2) - bloodfinger8/AlgorithmStudy GitHub Wiki
- 기존의 연결리스트는 노드를 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 만들고 해제하는 과정 필요
- 실행중 데이터 갯수의 최댓값을 미리 안다면 배열을 이용해 효율적으로 연결 리스트를 운용할 수 있다.
- 배열의 커서에 해당하는 값은, 다음 노드에 대한 포인터가 아니라 다음 노드가 들어있는 요소의 인덱스에 대한 값이다.
- 여기서 포인터 역할을 하는 인덱스를 커서라고 한다.
- 꼬리 노드의 커서는
-1로 설정한다. - 머리노드를 나타내는 노드
head도 커서기 때문에 머리 노드 A가 들어있는 곳인 인덱스 1이 head값이 된다. - 노드의 삽입, 삭제시 요소를 옮길 필요가 없다.
- 예를 들어, 신규 노드를 삽입할 때, 연결리스트 head에 노드를 삽입하면 그림과 같이 head를 1에서 6으로 업데이트한다.
- 프리 리스트란 삭제한 여러 레코드를 관리하기 위해 사용하는 것이 그 순서를 넣어두는 연결 리스트인 프리 리스트(free list)입니다.
- 삭제한 노드 관리. 삭제를 여러번 반복하면 배열 안은 빈 레코드 투성이가 되므로, 삭제한 여러 레코드를 관리하기 위해 사용하는 것이 그 순서를 넣어두는 연결 리스트인 프리 리스트이다.
package common;
import com.sun.deploy.panel.SpecialTreeListener;
import java.util.Comparator;
public class CursorLinkedList<E> {
class Node<E> {
private E data;
private int next; // 리스트의 뒤쪽 포인터
private int dnext; // free 리스트의 뒤쪽 포인터
void set(E data, int next) {
this.data = data;
this.next = next;
}
}
private Node<E>[] n; // 리스트 본체
private int size; // 리스트의 용량
private int max; // 사용중인 꼬리 record
private int head; // 머리 노드
private int current; // 선택 노드
private int deleted; // free 리스트의 머리 노드
private static final int NULL = -1;
public CursorLinkedList(int capacity) {
head = current = max = deleted = NULL;
try {
n = new Node[capacity];
for(int i=0 ; i<capacity ; i++) {
n[i] = new Node<E>();
}
size = capacity;
} catch (OutOfMemoryError e) {
size = 0;
}
}
private int getInsertIndex() {
if(deleted == NULL) {
if(max < size)
return ++max;
else
return NULL;
} else {
int rec = deleted;
deleted = n[rec].dnext;
return rec;
}
}
public void deleteIndex(int idx) {
if(deleted == NULL) {
deleted = idx;
n[idx].dnext = NULL;
} else {
int rec = deleted;
deleted = idx;
n[idx].dnext = rec;
}
}
public E search(E obj, Comparator<? super E> c) {
int ptr = head;
while(ptr != NULL) {
if(c.compare(obj, n[ptr].data) == 0) {
current = 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 = current = rec;
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) {
n[ptr].next = current = rec;
n[rec].set(obj, NULL);
}
}
}
}
public void removeFirst() {
if(head != NULL) {
int ptr = n[head].next;
deleteIndex(head);
head = current = ptr;
}
}
public void removeLast() {
if (head != NULL) {
if(n[head].next == NULL)
removeFirst();
else {
int ptr = head;
int pre = head;
while(n[ptr].next != NULL) {
pre = ptr;
ptr = n[ptr].next;
}
n[pre].next = NULL;
deleteIndex(ptr);
current = pre;
}
}
}
public void remove(int p) {
if(head != NULL) {
if(p == head)
removeFirst();
else {
int ptr = head;
while(n[ptr].next != p) {
ptr = n[ptr].next;
if(ptr == NULL) return;
}
n[ptr].next = NULL;
deleteIndex(p);
n[ptr].next = n[p].next;
current = ptr;
}
}
}
public void removeCurrentNode() {
remove(current);
}
public void clear() {
while(head != NULL) {
removeFirst();
}
current = NULL;
}
public boolean next() {
if(current == NULL || n[current].next == NULL) {
return false;
}
current = n[current].next;
return true;
}
public void printCurrentNode() {
if(current == NULL)
System.out.println("선택 노드가 없습니다.");
else
System.out.println(n[current].data);
}
public void dump() {
int ptr = head;
while(ptr != NULL) {
System.out.println(n[ptr].data);
ptr = n[ptr].next;
}
}
}
- 더미노드 : 이 노드는 노드의 삽입과 삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 더미 노드입니다.
- 노드를 생성할 때 new Node()에 의해 생성자를 호출하므로 더미 노드의 prev와 next는 자기 자신 노드를 가리키도록 초기화됩니다.