차례로 연결된 노드를 표현해주는 자료구조
이미지 출처: https://freestrokes.tistory.com/84
노드: 값과 다음 노드의 주소를 가리키는 포인터로 구성된다
Head 노드가 가리키는 노드가 첫번째 노드
노드의 포인터가 null이면 그 노드는 마지막 노드
데이터 삽입, 삭제가 많이 요구되는 상황
데이터 조회가 많이 요구되는 상황
public class SingleLinkedList {
private Node head;
private int size;
SingleLinkedList() {
head = new Node();
size = 0;
}
private class Node {
public Node next;
private Object data;
public Node(Object data) {
this.data = data;
this.next = null;
}
public Node() {}
}
// 첫번째 노드에 새 노드 연결
public void add2Head(Object data) {
Node newNode = new Node(data);
newNode.next = head.next;
head.next = newNode;
size++;
}
// 마지막 노드에 새 노드 연결
public void add2Tail(Object data) {
Node newNode = new Node(data);
Node now = head;
// 데이터 순회
while (now.next != null) {
now = now.next;
}
now.next = newNode;
size++;
}
// 특정 위치에 새 노드 삽입
public void insert(int idx, Object data) {
int i = 1;
Node newNode = new Node(data);
Node now = head;
while (i < idx) {
now = now.next;
i++;
}
newNode.next = now.next;
now.next = newNode;
}
// 특정 위치 노드 삭제
public Object delete(int idx) {
int i = 1;
Object data;
Node now = head;
Node removedNode;
while (i < idx) {
now = now.next;
i++;
}
removedNode = now.next;
now.next = removedNode.next;
data = removedNode.data;
removedNode = null;
System.out.println(idx + "번째 데이터, "+ data + " 삭제됐습니당 ");
return data;
}
// 연결리스트 전체 출력
public void printNodes() {
Node now = head;
if (head.next == null) {
System.out.println("저장된 데이터가 없습니다.");
}
while (now.next != null) {
System.out.println(now.next.data);
now = now.next;
}
}
}