자료구조 & 알고리즘/알고리즘
[Java] 리스트 구현(SLL, DLL)
seungwook_TIL
2024. 1. 21. 23:14
단일 연결 리스트(Singly Linked List)
직접 구현
노드
class Node<E>
{
E data;
Node<E> next;
Node(E data)
{
this.data = data;
this.next = null;
}
}
노드 추가
//리스트의 가장 뒷쪽에 데이터 추가
public void add(E data)
{
Node<E> newNode = new Node<>(data);
if (head == null) head = newNode;
else
{
Node<E> currentHead = head;
while (currentHead.next != null) currentHead = currentHead.next;
currentHead.next = newNode;
}
}
노드 삽입
//리스트의 원하는 인덱스에 데이터 삽입
public void insert(E data, int idx)
{
if (head == null)
{
add(data);
return;
}
Node<E> newNode = new Node<>(data);
Node<E> currentNode = head;
if (currentNode != null && idx == 0)
{
newNode.next = head;
head = newNode;
return;
}
for (int i = 0; i < idx - 1; ++i)
{
if (currentNode == null)
{
System.out.println("Error");
return;
}
currentNode = currentNode.next;
}
if (currentNode == null)
{
System.out.println("Invalid index");
return;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
노드 삭제
//앞쪽의 데이터 삭제
public void delete()
{
if (head == null) System.out.println("Empty");
else head = head.next;
}
//특정 데이터의 내용을 포함하는 노드 삭제
public void delete(E data)
{
if (head == null) System.out.println("Empty");
else if (head.data.equals(data)) head = head.next;
else
{
Node<E> currentHead = head;
while (currentHead.next != null && !currentHead.next.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead.next != null) currentHead.next = currentHead.next.next;
else currentHead.next = null;
}
}
노드 검색
//해당 데이터가 존재하는지 아닌지 확인
public void search(E data)
{
if (head == null)
{
System.out.println("Invalid");
return;
}
else
{
Node<E> currentHead = head;
while (currentHead != null && !currentHead.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead == null) System.out.println("Invalid");
else System.out.println("Valid");
}
}
노드 출력
public void printList()
{
Node<E> currentNode = head;
if (currentNode == null)
{
System.out.println("Empty");
return;
}
while (currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
}
전체 소스코드
public class SinglyLinkedList<E>
{
class Node<E>
{
E data;
Node<E> next;
Node(E data)
{
this.data = data;
this.next = null;
}
}
private Node<E> head;
SinglyLinkedList() { this.head = null; }
public void printList()
{
Node<E> currentNode = head;
if (currentNode == null)
{
System.out.println("Empty");
return;
}
while (currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
}
//리스트의 가장 뒷쪽에 데이터 추가
public void add(E data)
{
Node<E> newNode = new Node<>(data);
if (head == null) head = newNode;
else
{
Node<E> currentHead = head;
while (currentHead.next != null) currentHead = currentHead.next;
currentHead.next = newNode;
}
}
//리스트의 원하는 인덱스에 데이터 삽입
public void insert(E data, int idx)
{
if (head == null)
{
add(data);
return;
}
Node<E> newNode = new Node<>(data);
Node<E> currentNode = head;
if (currentNode != null && idx == 0)
{
newNode.next = head;
head = newNode;
return;
}
for (int i = 0; i < idx - 1; ++i)
{
if (currentNode == null)
{
System.out.println("Error");
return;
}
currentNode = currentNode.next;
}
if (currentNode == null)
{
System.out.println("Invalid index");
return;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
//앞쪽의 데이터 삭제
public void delete()
{
if (head == null) System.out.println("Empty");
else head = head.next;
}
//특정 데이터의 내용을 포함하는 노드 삭제
public void delete(E data)
{
if (head == null) System.out.println("Empty");
else if (head.data.equals(data)) head = head.next;
else
{
Node<E> currentHead = head;
while (currentHead.next != null && !currentHead.next.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead.next != null) currentHead.next = currentHead.next.next;
else currentHead.next = null;
}
}
//해당 데이터가 존재하는지 아닌지 확인
public void search(E data)
{
if (head == null)
{
System.out.println("Invalid");
return;
}
else
{
Node<E> currentHead = head;
while (currentHead != null && !currentHead.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead == null) System.out.println("Invalid");
else System.out.println("Valid");
}
}
public static void main(String args[])
{
SinglyLinkedList sll = new SinglyLinkedList();
sll.add(1);
sll.add(2);
sll.add(3);
sll.add(4);
sll.insert(0, 0);
sll.insert(0, 2);
sll.insert(0, 4);
sll.delete();
sll.delete(1);
sll.delete(0);
sll.printList();
}
}
책 코드
책 : Do it! 자료구조와 알고리즘 입문 자바편
ArrayLinkedList.java
// 연결 리스트 클래스(배열 커서 버전）
import java.util.Comparator;
public class ArrayLinkedList<E> {
//--- 노드 ---//
class Node<E> {
private E data; // 데이터
private int next; // 리스트의 뒤쪽포인터
private int dnext; // 프리 리스트의 뒤쪽포인터
//--- 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; // 프리 리스트의 머리노드
private static final int NULL = -1; // 뒤쪽노드가 없음 / 리스트가 가득 참
//--- 생성자(constructor) ---//
public ArrayLinkedList(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; // 프리 리스트에서
deleted = n[rec].dnext; // 머리 rec을 꺼냄
return rec;
}
}
//--- record idx를 프리 리스트에 등록 ---//
private void deleteIndex(int idx) {
if (deleted == NULL) { // 삭제 record가 존재하지 않음
deleted = idx; // idx를 프리 리스트의
n[idx].dnext = NULL; // 머리에 등록
} else {
int rec = deleted; // idx를 프리 리스트의
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; // 제 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) { // 제 rec 번째 레코드에 삽입
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;
}
}
}
//--- 레코드 p를 삭제 ---//
public void remove(int p) {
if (head != NULL) {
if (p == head) // p가 머리 노드이면
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;
}
}
}
ArrayLinkedListTester.java
// 선형리스트 클래스 ArrayLinkedList<E>의 사용 예
import java.util.Scanner;
import java.util.Comparator;
class ArrayLinkedListTester {
static Scanner stdIn = new Scanner(System.in);
//--- 데이터(회원번호＋이름) ---//
static class Data {
static final int NO = 1; // 번호를 읽어 들일까요?
static final int NAME = 2; // 이름을 읽어 들일까요?
private Integer no; // 회원번호
private String name; // 이름
//--- 문자열 표현을 반환 ---//
public String toString() {
return "(" + no + ") " + name;
}
//--- 데이터를 읽어 들임 ---//
void scanData(String guide, int sw) {
System.out.println(guide + "할 데이터를 입력하세요.");
if ((sw & NO) == NO) {
System.out.print("번호: ");
no = stdIn.nextInt();
}
if ((sw & NAME) == NAME) {
System.out.print("이름: ");
name = stdIn.next();
}
}
//--- 회원번호로 순서를 매기는 comparator ---//
public static final Comparator<Data> NO_ORDER =
new NoOrderComparator();
private static class NoOrderComparator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return (d1.no > d2.no) ? 1 : (d1.no < d2.no) ? -1 : 0;
}
}
//--- 이름으로 순서를 매기는 comparator ---//
public static final Comparator<Data> NAME_ORDER =
new NameOrderComparator();
private static class NameOrderComparator implements Comparator<Data> {
public int compare(Data d1, Data d2) {
return d1.name.compareTo(d2.name);
}
}
}
//--- 메뉴 열거형 ---//
enum Menu {
ADD_FIRST( "머리 노드 삽입"),
ADD_LAST( "꼬리 노드 삽입"),
RMV_FIRST( "머리 노드 삭제"),
RMV_LAST( "꼬리 노드 삭제"),
RMV_CRNT( "선택 노드 삭제"),
CLEAR( "전체 노드 삭제"),
SEARCH_NO( "번호 검색"),
SEARCH_NAME("이름 검색"),
NEXT( "선택 노드 진행"),
PRINT_CRNT( "선택 노드 표시"),
DUMP( "전체 노드 표시"),
TERMINATE( "종료");
private final String message; // 표시할 문자열
static Menu MenuAt(int idx) { // 순서가 idx번째인 열거를 반환
for (Menu m : Menu.values())
if (m.ordinal() == idx)
return m;
return null;
}
Menu(String string) { // 생성자(constructor)
message = string;
}
String getMessage() { // 표시할 문자열을 반환
return message;
}
}
//--- 메뉴 선택 ---//
static Menu SelectMenu() {
int key;
do {
for (Menu m : Menu.values()) {
System.out.printf("(%d) %s ", m.ordinal(), m.getMessage());
if ((m.ordinal() % 3) == 2 &&
m.ordinal() != Menu.TERMINATE.ordinal())
System.out.println();
}
System.out.print(" : ");
key = stdIn.nextInt();
} while (key < Menu.ADD_FIRST.ordinal() ||
key > Menu.TERMINATE.ordinal());
return Menu.MenuAt(key);
}
public static void main(String[] args) {
Menu menu; // 메뉴
Data data; // 추가용 데이터 참조
Data ptr; // 검색용 데이터 참조
Data temp = new Data(); // 읽어 들일 데이터
ArrayLinkedList<Data> list = new ArrayLinkedList<Data>(100);
do {
switch (menu = SelectMenu()) {
case ADD_FIRST : // 머리 노드 삽입
data = new Data();
data.scanData("머리에 삽입", Data.NO | Data.NAME);
list.addFirst(data);
break;
case ADD_LAST : // 꼬리 노드 삽입
data = new Data();
data.scanData("꼬리에 삽입", Data.NO | Data.NAME);
list.addLast(data);
break;
case RMV_FIRST : // 머리 노드 삭제
list.removeFirst();
break;
case RMV_LAST : // 꼬리 노드 삭제
list.removeLast();
break;
case RMV_CRNT : // 선택 노드 삭제
list.removeCurrentNode();
break;
case SEARCH_NO : // 회원번호 검색
temp.scanData("검색", Data.NO);
ptr = list.search(temp, Data.NO_ORDER);
if (ptr == null)
System.out.println("그 번호의 데이터가 없습니다.");
else
System.out.println("검색 성공 : " + ptr);
break;
case SEARCH_NAME : // 이름 검색
temp.scanData("검색", Data.NAME);
ptr = list.search(temp, Data.NAME_ORDER);
if (ptr == null)
System.out.println("그 이름의 데이터가 없습니다.");
else
System.out.println("검색 성공 : " + ptr);
break;
case NEXT : // 선택 노드를 뒤쪽으로 진행
list.next();
break;
case PRINT_CRNT : // 선택 노드의 데이터를 표시
list.printCurrentNode();
break;
case DUMP : // 모든 데이터를 리스트 순서로 표시
list.dump();
break;
case CLEAR : // 전체노드 삭제
list.clear();
break;
}
} while (menu != Menu.TERMINATE);
}
}
이중 연결 리스트(Doubly Linked List)
노드
class Node<E>
{
E data;
Node<E> prev;
Node<E> next;
Node(E data)
{
this.data = data;
this.prev = null;
this.next = null;
}
}
노드 추가
//리스트 앞쪽에 추가
public void add(E data)
{
Node<E> newNode = new Node(data);
Node<E> currentNode = head;
if(currentNode == null)
{
head = newNode;
tail = newNode;
}
else
{
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
//리스트 뒷쪽에 추가
public void add(E data, boolean back)
{
if(back == false) add(data);
else
{
Node<E> newNode = new Node(data);
Node<E> currentNode = tail;
if(currentNode == null)
{
head = newNode;
tail = newNode;
}
else
{
head.prev = newNode;
newNode.prev = null;
head = newNode;
}
}
}
노드 삽입
//원하는 인덱스에 노드 삽입
public void insert(E data, int idx)
{
Node<E> newNode = new Node(data);
if(head == null) add(data);
if (head == null || idx == 0)
{
newNode.next = head;
if (head != null) head.prev = newNode;
head = newNode;
if (tail == null) tail = newNode;
}
else
{
Node<E> currentNode = head;
for(int i = 0; i < idx - 1; ++i)
{
if(currentNode == null)
{
System.out.println("Error");
return;
}
currentNode = currentNode.next;
}
if (currentNode == null)
{
System.out.println("Invalid index");
return;
}
newNode.next = currentNode.next;
if (currentNode.next != null) currentNode.next.prev = newNode;
newNode.prev = currentNode;
currentNode.next = newNode;
if(newNode.next == null) tail = newNode;
}
}
노드 삭제
//노드를 앞 또는 뒷부분 삭제
public void delete(boolean back)
{
if (head == null) System.out.println("Empty");
else if(back == false) //앞부분 삭제
{
head = head.next;
if (head != null) head.prev = null;
else tail = null; // 리스트에 하나의 노드만 있었고 삭제한 경우
}
else //뒷부분 삭제
{
tail = tail.prev;
if (tail != null) tail.next = null;
else head = null; // 리스트에 하나의 노드만 있었고 삭제한 경우
}
}
//특정 데이터의 내용을 포함하는 노드 삭제
public void delete(E data)
{
if (head == null) System.out.println("Empty");
else
{
Node<E> currentNode = head;
while(currentNode.next != null && !currentNode.next.data.equals(data))
{
currentNode = currentNode.next;
}
if(currentNode.next != null)
{
currentNode.next = currentNode.next.next;
currentNode.next.next.prev = currentNode;
}
}
}
노드 검색
//해당 데이터가 존재하는지 아닌지 확인
public void search(E data)
{
if (head == null)
{
System.out.println("Invalid");
return;
}
else
{
Node<E> currentHead = head;
while (currentHead != null && !currentHead.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead == null) System.out.println("Invalid");
else System.out.println("Valid");
}
}
노드 출력
//리스트를 앞쪽부터 출력
public void printList()
{
Node<E> currentNode = head;
while(currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
}
//리스트를 뒷쪽부터 출력
public void printList(boolean back)
{
if(back == false) printList();
else
{
Node<E> currentNode = tail;
while(currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.prev;
}
System.out.println();
}
}
전체 코드
public class DoublyLinkedList<E>
{
class Node<E>
{
E data;
Node<E> prev;
Node<E> next;
Node(E data)
{
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node<E> head;
private Node<E> tail;
DoublyLinkedList()
{
this.head = null;
this.tail = null;
}
//리스트를 앞쪽부터 출력
public void printList()
{
Node<E> currentNode = head;
while(currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
}
//리스트를 뒷쪽부터 출력
public void printList(boolean back)
{
if(back == false) printList();
else
{
Node<E> currentNode = tail;
while(currentNode != null)
{
System.out.print(currentNode.data + " ");
currentNode = currentNode.prev;
}
System.out.println();
}
}
//리스트 앞쪽에 추가
public void add(E data)
{
Node<E> newNode = new Node(data);
Node<E> currentNode = head;
if(currentNode == null)
{
head = newNode;
tail = newNode;
}
else
{
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
//리스트 뒷쪽에 추가
public void add(E data, boolean back)
{
if(back == false) add(data);
else
{
Node<E> newNode = new Node(data);
Node<E> currentNode = tail;
if(currentNode == null)
{
head = newNode;
tail = newNode;
}
else
{
head.prev = newNode;
newNode.prev = null;
head = newNode;
}
}
}
//원하는 인덱스에 노드 삽입
public void insert(E data, int idx)
{
Node<E> newNode = new Node(data);
if(head == null) add(data);
if (head == null || idx == 0)
{
newNode.next = head;
if (head != null) head.prev = newNode;
head = newNode;
if (tail == null) tail = newNode;
}
else
{
Node<E> currentNode = head;
for(int i = 0; i < idx - 1; ++i)
{
if(currentNode == null)
{
System.out.println("Error");
return;
}
currentNode = currentNode.next;
}
if (currentNode == null)
{
System.out.println("Invalid index");
return;
}
newNode.next = currentNode.next;
if (currentNode.next != null) currentNode.next.prev = newNode;
newNode.prev = currentNode;
currentNode.next = newNode;
if(newNode.next == null) tail = newNode;
}
}
//노드를 앞 또는 뒷부분 삭제
public void delete(boolean back)
{
if (head == null) System.out.println("Empty");
else if(back == false) //앞부분 삭제
{
head = head.next;
if (head != null) head.prev = null;
else tail = null; // 리스트에 하나의 노드만 있었고 삭제한 경우
}
else //뒷부분 삭제
{
tail = tail.prev;
if (tail != null) tail.next = null;
else head = null; // 리스트에 하나의 노드만 있었고 삭제한 경우
}
}
//특정 데이터의 내용을 포함하는 노드 삭제
public void delete(E data)
{
if (head == null) System.out.println("Empty");
else
{
Node<E> currentNode = head;
while(currentNode.next != null && !currentNode.next.data.equals(data))
{
currentNode = currentNode.next;
}
if(currentNode.next != null)
{
currentNode.next = currentNode.next.next;
currentNode.next.next.prev = currentNode;
}
}
}
//해당 데이터가 존재하는지 아닌지 확인
public void search(E data)
{
if (head == null)
{
System.out.println("Invalid");
return;
}
else
{
Node<E> currentHead = head;
while (currentHead != null && !currentHead.data.equals(data))
{
currentHead = currentHead.next;
}
if (currentHead == null) System.out.println("Invalid");
else System.out.println("Valid");
}
}
public static void main(String args[])
{
DoublyLinkedList dll = new DoublyLinkedList<>();
dll.add(1);
dll.add(2);
dll.add(3);
dll.add(4);
dll.insert(0,0);
dll.insert(0,2);
dll.insert(0,4);
dll.insert(0,6);
dll.printList();
dll.delete(false);
dll.printList();
dll.delete(true);
dll.printList();
dll.search(9);
}
}