4. Linked List (3) - 복잡한 구조 표현

Linked List의 복잡한 구조 표현

---

1.  Equivalence Classes (동치 클래스)

집합 S의 원소들 사이에 “같다(Equivalent)”는 관계를 정의하면,
그 관계를 기준으로 서로 연결된 원소들의 묶음을 동치 클래스(Equivalence Class) 라고 함.

용어	의미
Reflexive	자기 자신과 동치
Symmetric	a ≡ b → b ≡ a
Transitive	a ≡ b, b ≡ c → a ≡ c
결과	동치 관계에 따라 집합이 여러 클래스(리스트)로 분리됨

 

예를 들어,
S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
관계쌍이 다음과 같을 때:

0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8 ≡ 9,
7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, 11 ≡ 0

 

결과적으로 다음 세 개의 클래스가 만들어짐:

{0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9, 10}

 

 

“연결성(Connectivity)”

• a ≡ b 이고 b ≡ c 라면, a, b, c는 모두 같은 그룹에 속함.
• 즉, 그래프에서 연결된 정점의 집합과 동일한 개념임.
• 이 관계를 효율적으로 표현하려면 연결 리스트를 사용하는 것이 공간 효율적임.

 

아이디어

typedef struct node {
    int data;
    struct node* link;
} Node;

Node* seq[MAX];  // 각 원소의 연결 리스트 헤더 저장
int out[MAX];    // 각 원소가 출력(탐색)되었는지 표시

1. 입력으로 관계쌍 <i, j>를 받음
2. i 리스트의 끝에 j를 추가 → i와 j가 연결됨
3. BFS 혹은 DFS 방식으로 연결된 모든 노드를 탐색하며 같은 클래스에 속한 원소들을 출력

예시

입력 쌍: (0,4), (3,1), (6,10), (8,9), (7,4), (6,8), (3,5), (2,11), (11,0)

탐색 순서:

시작: 0  
→ 11 연결  
→ 4 연결  
→ 7 연결  
→ 2 연결

 

결과: {0, 11, 4, 7, 2}

 

이후 아직 방문되지 않은 1부터 다시 탐색
→ {1, 3, 5} → {6, 8, 9, 10}

 

이렇게 세 개의 동치 클래스 완성!

---

2. Sparse Matrices (희소 행렬)

희소 행렬(Sparse Matrix)은 대부분의 원소가 0인 행렬임.
일반 2D 배열로 저장하면 불필요한 메모리 낭비가 크기 때문에,
0이 아닌 원소만 저장하는 구조가 필요함.

 

기본 구조 == Cross-linked List (교차 연결 리스트)

각 원소를 노드로 저장하며, 노드는 “행(row)”과 “열(column)” 방향으로 모두 연결됨.

typedef struct term {
    int row, col, value;
    struct term *right;  // 같은 행의 다음 원소
    struct term *down;   // 같은 열의 다음 원소
} Term;

추가로 Header Node가 존재함.

 

노드 종류	설명
Header Node	각 행과 열을 관리하는 노드 (원형 연결 리스트 구조)
Entry Node	실제 값이 있는 원소 (value ≠ 0) 저장 노드

 

각 행과 열은 원형 연결 리스트로 표현되고, 모든 헤더 노드는 next 포인터로 연결됨.

Header1 → Header2 → Header3 → ... → HeaderN → (다시 Header1)

 

행 방향으로 right 포인터, 열 방향으로 down 포인터가 이어짐.

 

이 구조를 사용하면

• 전치(Transpose), 덧셈(Addition), 곱셈(Multiplication) 등 효율적으로 수행 가능
• 메모리 낭비 없이 0이 아닌 데이터만 저장 가능.

예시

5×4 희소 행렬 예시:

2 0 0 0
4 0 0 3
0 0 0 0
8 0 0 1
0 0 6 0

이 행렬을 연결 리스트로 표현하면 각 원소는 (row, col, value) 로 저장되고
행과 열 방향으로 서로 교차 연결됨.

---

3. Doubly Linked List (이중 연결 리스트)

단일 연결 리스트는 한 방향으로만 이동 가능하지만,
이중 연결 리스트(Doubly Linked List) 는
양방향 탐색이 가능한 구조임.

typedef struct node {
    struct node *llink;
    int data;
    struct node *rlink;
} Node;

 

 

동작 개념

포인터	의미
llink	이전 노드 주소
rlink	다음 노드 주소

 

이중 연결 리스트는
ptr->llink->rlink == ptr 이고
ptr->rlink->llink == ptr 를 항상 만족함.
즉, 앞뒤로 모두 이동 가능한 구조임.

 

노드 삽입 (dinsert)

→ node의 오른쪽에 newnode 삽입. 양쪽 링크를 모두 갱신해야 함.

void dinsert(Node *node, Node *newnode) {
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rlink->llink = newnode;
    node->rlink = newnode;
}

 

 노드 삭제 (ddelete)

→ 삭제할 노드의 양쪽 포인터를 서로 연결하고, 해당 노드를 메모리에서 해제함.

void ddelete(Node *node, Node *deleted) {
    if (node == deleted)
        printf("Deletion of header node not permitted.\n");
    else {
        deleted->llink->rlink = deleted->rlink;
        deleted->rlink->llink = deleted->llink;
        free(deleted);
    }
}

 

원형 이중 연결 리스트 (Circular Doubly Linked List)

마지막 노드의 rlink가 첫 번째 노드를, 첫 노드의 llink가 마지막 노드를 가리키면

원형 이중 연결 리스트가 됨.

 

이 구조는 끝이 없는 순환 구조를 갖고 있어 스케줄링, 버퍼 관리 등에서 많이 활용됨.