-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLinkedList.java
More file actions
143 lines (122 loc) · 3.26 KB
/
Copy pathLinkedList.java
File metadata and controls
143 lines (122 loc) · 3.26 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
package list;
import java.util.Comparator;
/* 1. 포인터로 연결 리스트 만들기 실습 예제
* 연결 리스트 클래스 구현
*/
public class LinkedList<E> {
@SuppressWarnings("hiding")
// 노드
class Node<E> {
private E data; // 데이터
private Node<E> next; // 뒤쪽 포인터(다음 노드 참조)
// 생성자
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
private Node<E> head; // 머리 노드
private Node<E> crnt; // 선택 노드
// 생성자
public LinkedList() {
head = crnt = null;
}
// 노드 검색
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; // 검색 실패
}
// 머리에 노드 삽입
public void addFirst(E obj) {
Node<E> ptr = head; // 삽입 전의 머리 노드
head = crnt = new Node<E>(obj, ptr);
}
// 꼬리에 노드 삽입
public void addLast(E obj) {
if(head == null) // 리스트가 비어 있으면
addFirst(obj); // 머리에 노드 삽입
else {
Node<E> ptr = head;
while(ptr.next != null)
ptr = ptr.next; // while문 종료시 ptr은 꼬리 노드를 가리킴
ptr.next = crnt = new Node<E>(obj, null);
}
}
// 머리 노드를 삭제
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) {
pre = ptr;
ptr = ptr.next; // 종료시, ptr은 꼬리 노드를 가리키고 pre는 꼬리로부터 두 번째 노드를 가리킴
}
pre.next = null; // pre는 삭제 후의 꼬리 노드
crnt = pre;
}
}
}
// 노드 p를 삭제
public void remove(Node<E> p) {
if(head != null) {
if(p == head) // p가 머리 노드면
removeFirst(); // 머리 노드를 삭제
else {
Node<E> ptr = head;
while(ptr.next != p) {
ptr = ptr.next;
if(ptr == null) return; // p가 리스트에 없습니다
}
ptr.next = p.next;
crnt = ptr;
}
}
}
// 선택 노드를 삭제
public void removeCurrentNode() {
remove(crnt);
}
// 모든 노드를 삭제
public void clear() {
while(head != null) // 노드에 아무것도 없을 때까지
removeFirst(); // 머리 노드를 삭제
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;
}
}
}