Linked List

정의 (Singly Linked List)

Linked List 노드들은, reference field 로 연결된 독립 객체들이다.

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

보통 첫번째 노드(head)를 써서 list 전체를 나타낸다.
Linked List 노드 = 값 + (다음 노드로 연결되는) reference field

Time Complexity

1. 접근: O(N) 시간 (head 부터 차례로 탐색해야 해서)
2. 삽입: (삽입할 직전 요소 안다면) O(1) 시간
3. 삭제: O(N) 시간 (prev 노드 찾아야 하므로)

고전 문제

• 직접 구현하는 문제 (접근/삽입/삭제)
• Linked List에 Cycle 이 있는지 없는지 확인하는 문제: https://leetcode.com/problems/linked-list-cycle

정의 (Doubly Linked List)

class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

Time Complexity

1. 접근: O(N) 시간
2. 삽입: O(1) 시간
3. 삭제: O(1) 시간 (prev 노드 안 찾아도 되므로)

배열과의 비교

배열: 인덱스로 요소에 자주 접근해야 할 때
Linked List: 노드를 자주 삽입/삭제해야 할 때