포인터로 연결 리스트 만들기
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;
}
}
💬 head는 머리 노드에 대한 참조이지, 머리 노드 그 자체가 아님을 주의해야 한다.
💬 비어있는 연결 리스트는 노드도 없고, head가 가리키는 노드도 없으므로 그 값을 null로 초기화한다.
검색을 수행하는 search 메서드
// 노드 검색
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; // 검색 실패
}
머리에 노드를 삽입하는 addFirst 메서드
// 머리에 노드 삽입
public void addFirst(E obj) {
Node<E> ptr = head; // 삽입 전의 머리 노드
head = crnt = new Node<E>(obj, ptr);
}
꼬리에 노드를 삽입하는 addLast 메서드
// 꼬리에 노드 삽입
public void addLast(E obj) {
if (head == null) // 리스트가 비어 있으면
addFirst(obj); // 머리에 삽입
else {
Node<E> ptr = head;
// while문 종료 시, ptr은 꼬리 노드를 가리킨다.
while (ptr.next != null)
ptr = ptr.next;
// 새로운 노드를 가장 마지막에 넣고, 마지막을 가리키던 포인터를 새로운 노드로 설정
ptr.next = crnt = new Node<E>(obj, null);
}
}
머리 노드를 삭제하는 removeFirst 메서드
// 머리 노드를 삭제
public void removeFirst() {
if (head != null)
head = crnt = head.next;
}
꼬리 노드를 삭제하는 removeLast 메서드
// 꼬리 노드를 삭제
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;
}
}
}
선택한 노드를 삭제하는 remove 메서드
선택 노드를 삭제하는 removeCurrentNode 메서드
// 노드 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);
}
모든 노드를 삭제하는 clear 메서드
선택 노드를 하나 뒤쪽으로 이동하는 next 메서드
// 모든 노드를 삭제
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;
}
선택 노드를 표시하는 printCurrentNode 메서드
모든 노드를 표시하는 dump 메서드
// 선택 노드를 출력
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 값
커서로 연결 리스트 만들기
💬 포인터로 연결 리스트를 만들기 위해서는 삽입, 삭제할 때마다 노드 객체를 위한 메모리 영역을 만들고 해제하는 과정이 필요했다.
💬 하지만, 메모리 영역을 만들고 해제하는 데 필요한 비용은 무시할 수 없다.
💬 프로그램 실행 중에 데이터 수가 크게 바뀌지 않고 데이터 수의 최댓값을 미리 알 수 있다고 가정하여 배열을 이용하여 연결 리스트를 운용해보자.
💬 배열의 커서에 해당하는 값은 다음 노드가 들어 있는 요소의 인덱스 값이다.
💬 포인터 역할을 하는 인덱스를 커서라고 한다.
💬 노드의 삽입과 삭제를 그림을 통해 이해해보자.
◽ 연결 리스트의 머리에 노드 E를 삽입한 상태이다. 삽입한 노드는 배열 안에서 가장 꼬리 쪽에 있는 인덱스 위치에 들어가 있지만 연결리스트의 꼬리에 이를 추가한 것은 아니라는 차이점을 알아야 한다.
◽ 노드 B를 삭제한 상태이다. 삭제 자체는 어려운 일이 아니지만, 배열과 커서를 통한 연결 리스트에서 삭제를 할 경우, c와 같이 비어 있는 공간이 생기게 되며, 노드를 추가할 경우 비어 있는 공간부터 채워야 한다.
◽ 이에 따라 삭제된 레코드를 관리하기 위해 만든 연결 리스트인 프리 리스트를 만든다.
💬 프리 리스트를 추가한 후 삽입과 삭제를 진행하면 아래와 같다.
import java.util.Comparator;
public class AryLinkedList<E> {
// 노드
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; // 다음 노드 없음 / 리스트가 가득 참
// 생성자
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) { // 삭제할 record가 없음
deleted = idx; // idx를 free 리스트의
n[idx].dnext = NULL; // 머리에 등록
} else {
int rec = deleted; // idx를 free 리스트의
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) {
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; // 스캔 중인 노드의 앞쪽 노드
while (n[ptr].next != NULL) {
pre = ptr;
ptr = n[ptr].next;
}
n[pre].next = NULL; // pre는 삭제 후의 꼬리 노드
deleteIndex(ptr);
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(p);
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;
}
}
}
원형 리스트
💬 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조이다.
💬 원형 리스트와 연결 리스트의 차이점은 꼬리 노드의 다음 노드를 가리키는 포인터가 NULL이 아니라 머리 노드의 포인터 값이라는 점이다.
이중 연결 리스트
💬 연결 리스트의 가장 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽의 노드는 찾을 수 없다는 것이다.
💬 이러한 단점을 개선한 자료구조가 이중 연결 리스트이다.
💬 이중 연결 리스트의 노드 구조
class Node<E> {
E data;
Node<E> prev; // 머리 노드를 가리킴
Node<E> next; // 꼬리 노드를 가리킴
}
원형 이중 연결 리스트
import java.tuil.Comparator;
// 원형 이중 연결 리스트 클래스
public class DblLinkedList<E> {
// 노드
class Node<E> {
private E data; // 데이터
private Node<E> prev; // 앞쪽 포인터 (앞쪽 노드에 대한 참조)
private Node<E> next; // 뒤쪽 포인터 (뒤쪽 노드에 대한 참조)
// 생성자
// 자기 자신의 노드가 앞쪽 노드이면서 동시에 다음 노드가 된다.
Node() {
data = null;
prev = next = this;
}
// 생성자
Node(E obj, Node<E> prev, Node<E> next) {
data = obj;
this.prev = prev;
this.next = next;
}
}
private Node<E> head; // 머리 노드 (더미 노드)
private Node<E> crnt; // 선택 노드
// 생성자
public DblLinkedList() {
head = crnt = new Node<E>();
}
// 리스트가 비어 있는가?
public boolean isEmpty() {
return head.next = head;
}
생성자 DbLinkedList 메서드
💬 비어 있는 원형 이중 연결 리스트를 생성하며 데이터를 갖지 않는 노드를 1개만 만든다.
💬 이 노드는 노드의 삽입과 삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 더미 노드이다.
💬 노드를 생성할 때 new Node<E>()에 의해 생성자를 호출하므로 더미 노드의 prev와 next는 자기 자신의 노드를 가리키도록 초기화된다.
💬 또한 head와 crnt가 가리키는 곳도 이때 생성한 더미 노드이다.
노드를 검색하는 search 메서드
💬 연결 리스트와 로직은 비슷하나 머리 노드가 더미 노드의 다음 노드이므로 검색을 시작하는 곳은 head가 아니라 head.next이다.
💬 더미 노드, 머리 노드, 꼬리 노드를 가리키는 포인터는 각각 head, head.next, head.prev이다.
// 노드를 검색
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;
return ptr.data; // 검색 성공
}
ptr = ptr.next; // 다음 노드로 선택
}
return null; // 검색 실패
}
모든 노드를 출력하는 dump 메서드
모든 노드를 거꾸로 출력하는 dumpReverse 메서드
// 선택 노드를 출력
public void printCurrentNode() {
if (isEmpty())
System.out.println("선택 노드가 없습니다.");
else
System.out.println(crnt.data);
}
// 모든 노드를 출력
public void dump() {
Node<E> ptr = head.next; // 더미 노드의 다음 노드
while (ptr != 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;
}
}
// 선택 노드를 하나 뒤쪽으로 이동
public boolean next() {
if (isEmpty() || crnt.next == head)
return false; // 이동할 수 없음
crnt = crnt.next;
return true;
}
// 선택 노드를 하나 앞쪽으로 이동
public boolean prev() {
if (isEmpty() || crnt.prev == head)
return false; // 이동할 수 없음
crnt = crnt.prev;
return true;
}
선택 노드의 바로 뒤에 노드를 삽입하는 add 메서드
비어 있는 리스트에 노드를 삽입하는 경우
선택 노드의 바로 뒤에 노드를 삽입하는 경우
// 선택 노드의 바로 뒤에 노드를 삽입
public void add(E obj) {
Node<E> node = new Node<E>(obj, crnt, crnt.next);
crnt.next = crnt.next.prev = node;
crnt = node;
}
// 머리에 노드를 삽입
public void addFirst(E obj) {
crnt = head; // 더미 노드 head의 바로 뒤에 삽입
add(obj);
}
// 꼬리에 노드를 삽입
public void addLast(E obj) {
crnt = head.prev; // 꼬리 노드 head.prev의 바로 뒤에 삽입
add(obj);
}
선택 노드를 삭제하는 removeCurrentNode
// 선택 노드를 삭제
public void removeCurrentNode() {
if (!isEmpty()) {
crnt.prev.next = crnt.next;
crnt.next.prev = crnt.prev;
crnt = crnt.prev;
if (crnt == head) crnt = head.next;
}
}
// 노드 p를 삭제
public void remove(Node p) {
Node<E> ptr = head.next;
while (ptr != head) {
if (ptr == p) { // p를 찾음
crnt = p;
removeCurrentNode();
break;
}
ptr = ptr.next;
}
}
// 머리 노드를 삭제
public void removeFirst() {
crnt = head.next; // 머리 노드 head.next를 삭제
removeCurrentNode();
}
// 꼬리 노드를 삭제
public void removeLast() {
crnt = head.prev; // 꼬리 노드 head.prev를 삭제
removeCurrentNode();
}
// 모든 노드를 삭제
public void clear() {
while (!isEmpty()) // 텅 빌 때까지
removeFirst(); // 머리 노드를 삭제
}
}
'Data Structure' 카테고리의 다른 글
해시 (0) | 2022.01.11 |
---|---|
트리 (0) | 2022.01.03 |
문자열 검색 (0) | 2021.12.14 |
배열로 집합 만들기 (0) | 2021.12.13 |
재귀 알고리즘 (0) | 2021.11.30 |