LinkedList(연결리스트) 란?
-양방향 연결리스트를 구현한 클래스
-LinkedList 는 List 인터페이스와 Deque 인터페이스를 모두 구현하여 List, Queue, Stack의 기능을 모두 사용할 수 있음.
-Node(노드) 기반 자료구조로, 각 Node는 데이터와 다음 및 이전 Node에 대한 참조를 가지고 있음
단순 연결 리스트 구현하기
class Node {
int data;
Node next;
Node() {}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
// 연결 리스트 비어있는지 확인
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 연결 리스트의 맨 뒤에 데이터 추가
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
// 연결 리스트의 맨 뒤의 데이터 삭제
public void removeData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node prev = cur;
while (cur.next != null) {
prev = cur;
cur = cur.next;
}
if (cur == this.head) {
this.head = null;
} else {
prev.next = null;
}
}
// 연결 리스트에서 데이터 찾기
public void findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
while (cur != null) {
if (cur.data == data) {
System.out.println("Data exist!");
return;
}
cur = cur.next;
}
System.out.println("Data not found!");
}
// 연결 리스트의 모든 데이터 출력
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
// Test Code
LinkedList myList = new LinkedList(new Node(1, null));
myList.showData(); // 1
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.showData(); // 1 2 3 4 5
myList.findData(3); // Data exist!
myList.findData(100); // Data not found!
myList.removeData();
myList.removeData();
myList.removeData();
myList.showData(); // 1 2
myList.removeData();
myList.removeData();
myList.removeData(); // List is empty
}
}Node 클래스
class Node {
int data;
Node next;
Node() {}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}-Node 클래스는 연결 리스트의 각 노드를 나타냄
-data 필드는 노드가 저장하는 데이터를 나타내고, next 필드는 다음 노드를 참조
-기본 생성자와 데이터와 다음 노드를 지정하는 생성자가 있음
LinkedList 클래스
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}-LinkedList 클래스는 연결 리스트의 전체 구조를 나타냄
-head 필드는 리스트의 첫 번째 노드를 가리킴
-기본 생성자와 노드를 받아 초기화하는 생성자가 있음
isEmpty 메서드
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}-리스트가 비어있는지 확인
-head가 null이면 리스트가 비어있는것
addData 메서드
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.haed;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}-리스트의 끝에 데이터를 추가
-리스트가 비어있으면 head를 새 노드로 설정
-그렇지 않으면 리스트를 순회하며 마지막 노드에 새 노드를 추가
removeData 메서드
public void removeData() {
if (this.isEmpty) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node prev = cur;
while (cur.next != null) {
prev = cur;
cur = cur.next;
}
if (cur == this.head) {
this.head = null;
} else {
prev.next = null;
}
}-리스트의 마지막 데이터를 삭제
-리스트가 비어 있으면 메세지를 출력
-리스트를 순회하여 마지막 노드를 찾고, 그 노드를 삭제
findData 메서드
public void findData(int data) {
if (this.isEmpty) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
while (cur != null) {
if (cur.data == data) {
System.out.println("Data exist");
return;
}
cur = cur.next;
}
System.out.println("Data not found!");
}-리스트에서 특정 데이터를 찾음
-리스트가 비어있으면 메세지를 출력
-리스트를 순회하여 데이터를 찾고, 존재하면 메세지를 출력
showData 메서드
public void showData() {
if (this.isEmpty) {
System.out.prinln("List is empty");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}-리스트의 모든 데이터 출력
-리스트가 비어있으면 메세지를 출력
-리스트를 순회하며 각 노드의 데이터를 출력
LinkedList 클래스를 상속받아 기능추가
class LinkedList2 extends LinkedList {
LinkedList2(Node node) {
this.head = node;
}
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.head == null) {
this.head = new Node(data, null);
} else if (beforeData == null) {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
} else {
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data == beforeData) {
if (cur == this.head) {
this.head = new Node(data, this.head);
} else {
pre.next = new Node(data, cur);
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
LinkedList2 myList = new LinkedList2(new Node(1, null));
myList.showData(); // 1
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.showData(); // 1 2 3 4 5
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
}
}기존 LinkedList 를 상속받아 addData 와 removeData 메서드를 재정의(override)
-addData(int data, Integer beforeData) 메서드는 두개의 인자를 받아서, beforeData 값이 null이면 리스트의 맨 뒤에 데이터를 추가하고, 값이 있는 경우 해당 값을 가진 노드 앞에 새로운 데이터를 추가
-removeData(int data) 메서드는 주어진 데이터를 가진 노드를 찾아 삭제하는 기능을 가짐
이중 연결 리스트
class NodeBi {
int data;
NodeBi next;
NodeBi prev;
NodeBi(int data, NodeBi next, NodeBi prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList extends LinkedList {
NodeBi head;
NodeBi tail;
DoublyLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
}
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
public void addData(int data, Integer beforeData) {
if (this.head == null) {
this.head = new NodeBi(data, null, null);
this.tail = this.head;
} else if (beforeData == null) {
this.tail.next = new NodeBi(data, null, this.tail);
this.tail = this.tail.next;
} else {
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == beforeData) {
if (cur == this.head) {
this.head = new NodeBi(data, this.head, null);
this.head.next.prev = this.head;
} else {
pre.next = new NodeBi(data, cur, pre);
cur.prev = pre.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
this.head = cur.next;
this.head.prev = null;
} else if (cur == this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
public void showDataFromTail() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.tail;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.prev;
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
DoublyLinkedList myList = new DoublyLinkedList(new NodeBi(1, null, null));
myList.showData(); // 1
myList.addData(2, null);
myList.addData(3, null);
myList.addData(4, null);
myList.addData(5, null);
myList.showData(); // 1 2 3 4 5
myList.showDataFromTail(); // 5 4 3 2 1
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.showDataFromTail(); // 5 500 4 400 3 300 2 200 1 100
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.showDataFromTail(); // 5 4 3 2 1
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
myList.showDataFromTail(); // List is empty!
}
}NodeBi 클래스
class NodeBi {
int data;
NodeBi next;
NodeBi prev;
NodeBi(int data, NodeBi next, NodeBi, prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
}-NodeBi 클래스는 이중 연결 리스트의 각 노드를 나타내며, data, next, prev 필드를 가짐
-data : 노드가 저장하는 데이터
-next : 다음 노드를 가리키는 포인터
-prev : 이전 노드를 가리키는 포인터
-생성자는 데이터를 초기화하고, 다음 및 이전 노드를 설정
Doubly LinkedList 클래스
class DoublyLinkedList extends LinkedList {
NodeBi head;
NodeBi tail;
DoublyLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
}-DoulbyLinkedList 클래스는 LinkedList 클래스를 상속받아 이중 연결 리스트를 구현
-head : 리스트의 첫 번째 노드를 가리키는 포인터
-tail : 리스트의 마지막 노드를 가리키는 포인터
isEmpty 메서드
public boolean isEmpty() {
return this.head == null;
}-리스트가 비어 있는지 확인하는 메서드로 head가 null이면 리스트가 비어있다고 판단
addData 메서드
public void addData(int data, Integer beforeData) {
if (this.head == null) {
this.head = new NodeBi(data, null, null);
this.tail = this.head;
} else if {
NodeBi cur = this.head;
NOdeBi pre = cur;
while (cur != null) {
if (cur.data == beforeData) {
if (cur == this.head) {
this.head = new NodeBi(data, this.head, null);
this.head.next.prev = this.head;
} else {
pre.next = new NodeBi(data, cur, pre);
cur.prev = pre.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}-리스트가 비어있는 경우 리스트에 데이터를 추가
-beforeData 가 null인 경우 리스트의 맨 끝에 추가
-beforeData 가 특정 값을 가진 노드 앞에 데이터를 추가하는 경우
removeData 메서드
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
this.head = cur.next;
this.head.prev = null;
} else if (cur == this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}-삭제할 노드가 유일한 노드인 경우
-삭제할 노드가 첫번째 노드인 경우
-삭제할 노드가 마지막 노드인 경우
-그 외 일반적인 경우
showData 메서드
public void showData() {
if (ths.isEmpty()) {
System.put.pringln("List is empty") {
return;
}
NideBi cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
Systema.out.println();
}-리스트의 데어터를 순차적으로 출력하는 메서드로, 리스트가 비어있는 경우 이를 출력
showDataFromTail 메서드
public void showDataFromTail() {
if (this. is empty()) {
System.out.println("List is empty") {
return;
}
NodeBi cur = this.tail;
while (cur != null) {
System.out.print(cur.data + " ");
cur cur.prev;
}
System.out.println();
}-리스트의 데이터를 역순으로 출력하는 메서드로 리스트가 비어 있는경우 이를 출력
원형 이중 연결 리스트
class CircularLinkedList {
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
node.next = this.head;
node.prev = this.head;
}
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.head == null) {
NodeBi newNodeBi= new NodeBi(data, null, null);
this.head = newNodeBi;
this.tail = newNodeBi;
} else if (beforeData == null) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.tail = newNodeBi;
} else {
NodeBi cur = this.head;
NodeBi pre = cur;
do {
if (cur.data == beforeData) {
if (cur == this.head) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.head = newNodeBi;
} else {
NodeBi newNodeBi = new NodeBi(data, cur, pre);
pre.next = newNodeBi;
cur.prev = newNodeBi;
}
break;
}
pre = cur;
cur= cur.next;
} while (cur != this.head);
}
}
// 연결 리스트에서 특정 값을 가진 노드 삭제
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List if empty");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
cur.next.prev = this.head.prev;
this.head = cur.next;
this.tail.next = this.head;
} else if (cur == this.tail) {
pre.next = this.tail.next;
this.tail = pre;
this.head.prev = this.tail;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
while (cur.next != this.head) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println(cur.data);
}
}
public class Practice3 {
public static void main(String[] args) {
// Test code
CircularLinkedList myList = new CircularLinkedList(new NodeBi(1, null, null));
myList.addData(2, null);
myList.addData(3, null);
myList.addData(4, null);
myList.addData(5, null);
myList.showData(); // 1 2 3 4 5
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
}
}CircularLinkedList 클래스
class circularLinkedList {
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
node.next = this.head;
node.prev = this.head;
}-circularLinkedList 클래스는 원형 이중 연결 클래스를 구현
-head : 리스트의 첫 번째 노드를 가리키는 포인터
-tail : 리스트의 마지막 노드를 가리키는 포인터
-생성자는 초기 노드를 받아서 설정하며, 리스트의 순환성을 유지하기 위해 head와 tail 을 연결
isEmpty 메서드
public boolean isEmpty() {
return this.head == null;
}-리스트가 비어있는지 확인하는 메서드로, head 가 null 이면 리스트가 비어있다고 판단
addData 메서드
public void addData(int data, Integer beforeData) {
if (this.head == null) {
NodeBi newNodeBi = new NodeBi(data, null, null);
this.head = newNodeBi;
this.tail = newNodeBi;
newNodeBi.next = this.head;
newNodeBi.prev = this.head;
} else if (beforeData == null) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.tail = newNodeBi;
} else {
NodeBi cur = this.head;
NodeBi pre = cur;
do {
if (cur.data == beforeData) {
if (cur == this.head) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.head = newNodeBi;
} else {
NodeBi newNodeBi = new NodeBi(data, cur, pre);
pre.next = newNodeBi;
cur.prev = newNodeBi;
}
break;
}
pre = cur;
cur = cur.next;
} while (cur != this.head);
}
}-리스트가 비어있는 경우 데이터 추가
-beforeData가 null인경우 리스트의 맨 끝에 추가
-beforeData가 특정 값을 가진 노드앞에 데이터를 추가하는 경우
removeData 메서드
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
retrun;
}
NodeBi cur = this.head;
NodeBi pre = cur;
do {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
cur.next.prev = this.head.prev;
this.head = cur.next;
this.tail.next = this.head;
} else if (cr == this.tail) {
pre.next = this.tail.next;
this.tail = pre;
this.head.prev = this.tail;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
} while (cur != this.head);
}-삭제할 노드가 유일한 노드인 경우
-삭제할 노드가 첫 번째 노드인 경우
-삭제할 노드가 마지막 노드인 경우
-그 외 일반적인 경우
showData 메서드
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur =. his.head;
while (cur.next != this.head) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println(cur, data);
}-리스트의 데이터를 순차적으로 출력하는 메서드로, 리스트가 비어있는 경우 이룰 출력
Hello World