1. Linked List
- 각 요소들을 연쇄적으로 연결한 선형 자료구조
- ✅ 각 요소마다 이전/다음 노드의 포인터를 보유함
- ✅ Head 포인터: 맨 처음 요소를 가리키는 포인터 (링크드리스트 마다 가지고 있음)
Node
- 각 요소를 표현하는 자료구조
- ✅ 구성: 값, next 포인터 (다음 노드를 가리키는 포인터)
장점
| 구분 | 설명 | 장점 |
| 동적 할당 | 크기가 동적으로 할당됨 | 유연한 메모리 사용 가능 |
| 메모리 비연속적 | 메모리 연속적이지 않고 흩어져 저장됨 ✅ 다른 요소에 독립적으로 존재함 ✅ 각 노드는 next 포인터를 가짐 |
요소 추가/삭제 시 전체 재배치 불필요 |
| 효율적 연산 | 배열처럼 연속된 메모리를 고려하지 않아도 됨 | 삽입/삭제 등의 연산이 효율적임 |
단점
| 구분 | 설명 | 단점 |
| 추가 메모리 비용 | 각 노드가 데이터를 저장할 뿐만 아니라 next 포인터도 가져야 함 | 배열보다 메모리 사용량이 더 많음 |
| 조회 성능 | Random Access 불가능 | 조회 속도가 느림 |
| 복잡성 | 포인터 연산을 통해 연산 수행 (노드 연결/해제 등) | 배열보다 구현과 관리가 복잡함 |
2. 연산
| 연산 | 설명 | 시간복잡도 |
| search | 순차적으로 탐색 (from Head pointer) | O(n) |
| insert | - 첫번째 위치 - 중간 위치 (탐색필요) |
O(1) O(n) |
| delete | - 첫번째 위치 - 중간 위치 (탐색필요) |
O(1) O(n) |
3. 종류
Singly LinkedList
- 각 노드에 값과 next 포인터를 가지는 링크드리스트
Doubly LinkedList
- 각 노드에 값과 prev, next 포인터를 가지는 링크드리스트
- ✅ 빠른 연산 (조회, 삽입, 삭제)
Circularly LinkedList
- 원형 형태의 링크드리스트 (각 노드에 값과 prev, next 포인터를 가짐)
- ✅ 맨 첫번째 노드의 prev: 맨 마지막 노드를 가리킵니다.
- ✅ 맨 마지막 노드의 next: 맨 첫번째 노드를 가리킵니다.
4. 사용 사례
| 종류 | 특징 | 활용 |
| Singly LinkedList | Head, Tail 포인터 보유 | ✅ Stack & Queue ✅ Recursion Algorithm |
| Doubly LinkedList | 연산이 빈번한 경우 (삽입, 삭제) | ✅ 브라우저 앞뒤로 가기 ✅ LRU 캐시, 작업 큐 |
| Circularly LinkedList | 순환하는 경우 | ✅ 오디오 스트리밍 (무한반복) ✅ 프로세스 스케줄링 (순환 관리) ✅ 로드밸런싱 (작업 분배) |
5. 구현
Singly LinkedList
더보기
public class MySinglyLinkedList<V> {
class Node {
final V data;
Node next;
public Node(V data) {
this.data = data;
}
}
private Node head, tail;
private int cnt;
public Node searchByIdx(int idx) {
rangeCheck(idx);
emptyCheck();
Node target = head;
for (int i = 0; i < idx; i++) target = target.next;
return target;
}
public Node searchByVal(V val) {
emptyCheck();
Node target = head;
while (target != null && !target.data.equals(val)) target = target.next;
return target;
}
public void add(int idx, V val) {
rangeCheckForAdd(idx);
if (idx == 0) {
addFirst(val);
return;
} else if (idx == cnt) {
addLast(val);
return;
}
Node newNode = new Node(val);
Node prev = searchByIdx(idx-1);
newNode.next = prev.next;
prev.next = newNode;
cnt++;
}
public void remove(V val) {
emptyCheck();
if (head.data.equals(val)) {
removeFirst();
return;
} else if (tail.data.equals(val)) {
removeLast();
return;
}
Node target = head, prev = null;
while (target != null && !target.data.equals(val)) {
prev = target;
target = target.next;
}
if (target == null) throw new IllegalStateException("Node with the specified val not found");
prev.next = target.next;
cnt--;
}
private void addFirst(V val) {
Node newNode = new Node(val);
if (cnt > 0) {
newNode.next = head;
head = newNode;
} else {
tail = head = newNode;
}
cnt++;
}
private void addLast(V val) {
Node newNode = new Node(val);
if (cnt > 0) {
tail.next = newNode;
tail = tail.next;
} else {
head = tail = newNode;
}
cnt++;
}
private void removeFirst() {
if (cnt > 1) {
head = head.next;
} else {
head = tail = null;
}
cnt--;
}
private void removeLast() {
if (cnt > 1) {
int tailPrevIdx = cnt-2;
Node tailPrev = searchByIdx(tailPrevIdx);
tailPrev.next = null;
tail = tailPrev;
} else {
head = tail = null;
}
cnt--;
}
private void rangeCheck(int idx) {
if (idx < 0 || idx >= cnt) throw new IllegalStateException("out of bounds");
}
private void rangeCheckForAdd(int idx) {
if (idx < 0 || idx > cnt) throw new IllegalStateException("out of bounds");
}
private void emptyCheck() {
if (head == null) throw new IllegalStateException("data not exist");
}
}
Doubly LinkedList
더보기
public class MyDoublyLinkedList2<T> {
class Node {
T data;
Node prev, next;
public Node (T data) {
this.data = data;
}
}
private Node head, tail;
private int cnt;
public Node searchByIdx(int idx) {
rangeCheck(idx);
emptyCheck();
Node target = head;
for (int i = 0; i < idx; i++) target = target.next;
return target;
}
public Node searchByVal(T val) {
emptyCheck();
Node target = head;
while (target != null && !target.data.equals(val)) target = target.next;
return target;
}
public void add(int idx, T val) {
rangeCheckForAdd(idx);
if (idx == 0) {
addFirst(val);
return;
} else if (idx == cnt) {
addLast(val);
return;
}
Node newNode = new Node(val);
Node prev = searchByIdx(idx);
newNode.prev = prev;
newNode.next = prev.next;
prev.next = newNode;
prev.next.prev = newNode;
cnt++;
}
public void remove(T val) {
emptyCheck();
if (head.data.equals(val)) {
removeFirst();
return;
} else if (tail.data.equals(val)) {
removeLast();
return;
}
Node target = searchByVal(val);
if (target == null) throw new IllegalStateException("Node with the specified val not found");
target.prev.next = target.next;
target.next.prev = target.prev;
cnt--;
}
private void addFirst(T val) {
Node newNode = new Node(val);
if (cnt > 0) {
newNode.next = head;
head.prev = newNode;
head = newNode;
} else {
head = tail = newNode;
}
cnt++;
}
private void addLast(T val) {
Node newNode = new Node(val);
if (cnt > 0) {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
} else {
head = tail = newNode;
}
cnt++;
}
private void removeFirst() {
if (cnt > 1) {
head = head.next;
} else {
head = tail = null;
}
cnt--;
}
private void removeLast() {
if (cnt > 1) {
tail = tail.prev;
} else {
head = tail = null;
}
cnt--;
}
private void rangeCheck(int idx) {
if (idx < 0 || idx >= cnt) throw new IllegalStateException();
}
private void rangeCheckForAdd(int idx) {
if (idx < 0 || idx > cnt) throw new IllegalStateException("out of bounds");
}
private void emptyCheck() {
if (head == null) throw new IllegalStateException("data not exist");
}
}
Circularly LinkedList
더보기
public class MyCircularlyLinkedList<T> {
class Node {
final T data;
Node prev, next;
public Node(T data) {
this.data = data;
}
}
private Node head, tail;
private int cnt;
public Node searchByIdx(int idx) {
emptyCheck();
rangeCheck(idx);
Node target = head;
for (int i = 0; i < idx; i++) target = target.next;
return target;
}
public Node searchByVal(T val) {
emptyCheck();
Node target = head;
do {
if (target.data.equals(val)) return target;
target = target.next;
} while (target != head);
throw new IllegalStateException();
}
public void add(int idx, T val) {
rangeCheckForAdd(idx);
if (cnt == 0) {
addFirst(val);
return;
} else if (cnt == idx) {
addLast(val);
return;
}
Node newNode = new Node(val);
Node prev = searchByIdx(idx);
newNode.prev = prev;
newNode.next = prev.next;
prev.next.prev = newNode;
prev.next = newNode;
cnt++;
}
public void remove(T val) {
emptyCheck();
if (head.data.equals(val)) {
removeFirst();
return;
} else if (tail.data.equals(val)) {
removeLast();
return;
}
Node target = searchByVal(val);
if (target == null) throw new IllegalStateException("Node with the specified val not found");
target.prev.next = target.next;
target.next.prev = target.prev;
cnt--;
}
private void addFirst(T val) {
Node newNode = new Node(val);
if (cnt > 0) {
newNode.next = head;
newNode.prev = tail;
head.prev = newNode;
tail.next = newNode;
head = head.prev;
} else {
head = tail = newNode;
head.next = head.prev = head;
}
cnt++;
}
private void addLast(T val) {
Node newNode = new Node(val);
if (cnt > 0) {
newNode.prev = tail;
newNode.next = head;
tail.next = newNode;
head.prev = newNode;
tail = tail.next;
} else {
head = tail = newNode;
head.next = head.prev = head;
}
cnt++;
}
private void removeFirst() {
if (cnt > 1) {
head = head.next;
head.prev = tail;
tail.next = head;
} else {
head = tail = null;
}
cnt--;
}
private void removeLast() {
if (cnt > 1) {
tail = tail.prev;
tail.next = head;
head.prev = tail;
} else {
head = tail = null;
}
cnt--;
}
private void rangeCheck(int idx) {
if (idx < 0 || idx >= cnt) throw new IllegalStateException();
}
private void rangeCheckForAdd(int idx) {
if (idx < 0 || idx > cnt) throw new IllegalStateException();
}
private void emptyCheck() {
if (head == null) throw new IllegalStateException();
}
}
출처
'Data Structure' 카테고리의 다른 글
| [고급 자료구조] Graph: Minimum spanning tree (0) | 2024.02.22 |
|---|---|
| [고급 자료구조] Tree: Union-Find (1) | 2024.02.11 |
| [기초 자료구조] Array (0) | 2023.11.08 |
| [고급 자료구조] Tree: Heap (0) | 2023.10.26 |
| [고급 자료구조] Tree: Trie (0) | 2023.10.26 |