-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAryLinkedList.java
More file actions
195 lines (173 loc) · 4.17 KB
/
Copy pathAryLinkedList.java
File metadata and controls
195 lines (173 loc) · 4.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
package list;
import java.util.Comparator;
// 연결 리스트 클래스( 배열 커서를 이용한 버전 )
public class AryLinkedList<E> {
// 노드
@SuppressWarnings("hiding")
class Node<E> {
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; // 사용 중인 꼬리 record
private int head; // 머리 노드
private int crnt; // 선택 노드
private int deleted; // free 리스트의 머리 노드
private static final int NULL = -1; // 다음 노드 없음 / 리스트가 가득 참
// 생성자
@SuppressWarnings("unchecked")
public AryLinkedList(int capacity) {
head = crnt = 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;
}
}
// 다음에 삽입하는 record 인덱스를 구함
private int getInsertIndex() {
if(deleted == NULL) { // 삭제할 record가 없음
if(max < size)
return ++max; // 새 record를 사용
else
return NULL; // 용량 over(넘침)
} else {
int rec = deleted; // free 리스트에서
deleted = n[rec].dnext; // 머리 rec를 꺼냄
return rec;
}
}
// record idx를 free 리스트에 등록
private void deleteIndex(int idx) {
if(deleted == NULL) {
deleted = idx; // idx를 free리스트의
n[idx].dnext = NULL; // 머리에 등록
} else {
int rec = deleted; // idx를 free리스트의
deleted = idx; // 머리에 삽입
n[rec].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) {
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;
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 = 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; // 스캔 중인 노드의 앞쪽 노드
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)
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;
}
}
}