연결리스트
2023. 2. 18. 00:32ㆍ자료구조/선형자료구조
+ List와 ArrayList 차이?
: List(=인터페이스; 클래스 내 모든 메서드가 추상메서드인 클래스), ArrayList(=클래스)
ex)
List list1 = new ArrayList(); (O)
List list2 = new LinkedList(); (O)
ex)
ArrayList list3 = new ArrayList(); (O)
ArrayList list4 = new LinkedList(); (X)
< 구현 >
1. 단순 연결리스트 - 노드 추가/삭제 시, 맨 뒤에 동작
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;
}
// 연결 리스트의 맨 뒤에 data 추가
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data, null);
}
}
// 연결 리스트의 맨 뒤의 데이터 삭제
public void removeData() {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
Node current = this.head;
Node prev = current;
while (current.next != null) {
prev = current;
current = current.next;
}
if (current == 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 current = this.head;
while (current != null) {
if (current.data == data) {
System.out.println("Data exist.");
return;
}
current = current.next;
}
System.out.println("Data not found.");
}
// 연결 리스트의 모든 데이터 출력
public void printData() {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
Node current = this.head;
while (current!= null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class linkList {
public static void main(String[] args) {
LinkedList myList = new LinkedList(new Node(1, null));
myList.printData();
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.printData();
myList.findData(3);
myList.findData(100);
myList.removeData();
myList.removeData();
myList.removeData();
myList.printData();
myList.removeData();
myList.removeData();
myList.removeData();
}
}
2. 단순 연결리스트 - 중간에 노드 추가/삭제
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 current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data, null);
} else {
Node current = this.head;
Node pre = current;
while (current != null) {
if (current.data == beforeData) {
if (current == this.head) {
this.head = new Node(data, this.head); // 앞에 추가
} else {
pre.next = new Node(data, current);
}
break;
}
pre = current;
current = current.next;
}
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
Node current = this.head;
Node pre = current;
while(current != null) {
if (current.data == data) {
if (current == this.head) {
this.head = current.next;
} else {
pre.next = current.next;
}
break;
}
pre = current;
current = current.next;
}
}
}
3. 양방향 연결 리스트
class NodeBi {
int data;
NodeBi next;
NodeBi pre;
NodeBi(int data, NodeBi next, NodeBi pre) {
this.data = data;
this.next = next;
this.pre = pre;
}
}
class DoublyLinkedList extends LinkedList {
NodeBi head;
NodeBi tail;
DoublyLinkedList(NodeBi head, NodeBi tail) {
this.head = head;
this.tail = tail;
}
// isEmpty()?
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 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 (beforeData == null) {
this.tail.next = new NodeBi(data, null, this.tail);
this.tail = this.tail.next;
} else {
NodeBi current = this.head;
NodeBi pre = current;
while (current != null) {
if (current.data == beforeData) {
if (current == this.head) {
this.head = new NodeBi(data, this.head, null);
this.head.next.pre = this.head;
} else {
pre.next = new NodeBi(data, current, pre.next);
current.pre = pre.next;
}
break;
}
pre = current;
current = current.next;
}
}
}
// removeData
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
NodeBi current = this.head;
NodeBi pre = current;
while (current != null) {
if (current.data == data) {
if (current == this.head && current == this.tail) { // data가 한 개
this.head = null;
this.tail = null;
} else if (current == this.head) { // 맨 앞 노드 삭제
this.head = current.next;
this.head.pre = null;
} else if (current == this.tail) { // 맨 뒤 노드 삭제
this.tail = current.pre;
this.tail.next = null;
} else {
pre.next = current.next;
current.next.pre = pre;
}
break;
}
pre = current;
current = current.next;
}
}
// 앞에서부터 출력
public void printDataFromStart() {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
NodeBi current = this.head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// 뒤에서부터 출력
public void printDataFromEnd() {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
NodeBi current = this.tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.pre;
}
System.out.println();
}
}
4. 원형 연결 리스트
class CircularLinkedList {
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
node.next = this.head;
node.pre = this.head;
}
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// data추가
// before_data가 null: 가장 뒤에 추가
// before_data 값이 있음: 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.isEmpty()) {
NodeBi newNode = new NodeBi(data, null, null);
this.head = newNode;
this.tail = newNode;
newNode.pre = newNode;
newNode.next = newNode;
} else if (beforeData == null) {
NodeBi newNode = new NodeBi(data, this.head, this.tail);
this.tail.next = newNode;
this.tail = newNode;
this.head.pre = newNode;
} else {
NodeBi current = this.head;
NodeBi pre = current;
do {
if (current.data == beforeData) {
if (current.next == this.head) { // 노드가 한 개 일 때
NodeBi newNode = new NodeBi(data, this.head, this.tail);
this.tail.next = newNode;
this.head.pre = newNode;
this.head = newNode;
} else {
NodeBi newNode = new NodeBi(data, current, pre);
pre.next = newNode;
current.pre = newNode;
}
break;
}
pre = current;
current = current.next;
} while (current.next != this.head);
}
}
// 연결리스트에서 특정 값을 가진 노드 삭제
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
NodeBi current = this.head;
NodeBi pre = current;
while (current != null) {
if (current.data == data) {
if (current == this.head && current == this.tail) { // 노드가 한 개일 때,
this.head = null;
this.tail = null;
} else if (current == this.head) { // 삭제하려는 노드가 맨 앞일 때,
this.tail.next = this.head.next;
current.next.pre = this.tail;
this.head = current.next;
} else if (current == this.tail) { // 삭제하려는 노드가 맨 뒤일 때,
current.pre.next = this.head;
this.head.pre = this.tail.pre;
this.tail = current.pre;
} else {
pre.next = current.next;
current.next.pre = pre;
}
break;
}
pre = current;
current = current.next;
}
}
// showData
public void printData() {
if (this.isEmpty()) {
System.out.println("List is empty.");
return;
}
NodeBi current = this.head;
while (current.next != this.head) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println(current.data);
}
}