1. Linked List 란?
- 선형 자료구조 입니다.
- 각 요소들을 연쇄적으로 연결
- 포인터 사용
Head
- 맨 처음 요소를 가리키는 포인터
- 링크드리스트마다 가지고 있습니다.
Node
- 각 요소를 의미하는 자료구조 입니다.
구성
- 값
- 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 | prev, next 포인터 보유 - 양방향 탐색 - 연산이 빈번한 경우 (삽입, 삭제) |
브라우저 앞뒤로 가기 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 (0) | 2024.02.11 |
| [기초 자료구조] Array (0) | 2023.11.08 |
| [고급 자료구조] Tree: Trie (0) | 2023.10.26 |
| [자료구조] Graph (0) | 2023.10.26 |