9. 리스트 - bloodfinger8/AlgorithmStudy GitHub Wiki
리스트는 데이터를 순서대로 나열한 자료구조 입니다.
선형 리스트란 가장 단순한 구조를 이루고 있는 리스트로, 선형 리스트(Linear list) 또는 연결 리스트(Linked list)라고 합니다.
리스트의 데이터는 노드(node) 혹은 요소(element)라고 합니다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있습니다.
처음과 끝에 있는 노드는 특별히 각각 머리 노드(head node), 꼬리 노드(tail node)라고 합니다. 또한 하나의 노드에 대해 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고 합니다.
class Node<E> {
private E data; // 데이터
private Node<E> next; // 뒤쪽 포인터(다음 노드 참조)
// 생성자
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}데이터용 필드인 data와 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 가집니다. 일반적으로 이런 클래스 구조를 자기참조(self-referential)형이라고 합니다.
public class LinkedList<E> {
// 노드
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;
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;
}
pre.next = null; // pre는 삭제 후의 꼬리 노드
crnt = pre;
}
}
}
// 노드 p를 삭제
public void remove(Node 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;
}
}
}