4. Linked List (2) - 활용

Linked List 를 활용한 응용 예제 다뤄보기

---

 

1. Polynomial Representation (다항식의 연결 리스트 표현)

• 다항식은 보통
  P(x) = 3x^14 + 2x^8 + 1
  이런 식으로 표현됨.
• 이를 연결 리스트로 나타내면 각 항(term) 이 하나의 노드로 표현됨.
  (3, 14) → (2, 8) → (1, 0) → NULL
  
  
• 각 노드는 다음과 같은 구조를 가짐:

typedef struct PolyNode {
    int coef;              // 계수 (coefficient)
    int expo;              // 지수 (exponent)
    struct PolyNode *link; // 다음 항 포인터
} PolyNode;

 

예시 다항식

a = 3x^14 + 2x^8 + 1
b = 8x^14 - 3x^10 + 10x^6

// a와 b를 각각 링크드 리스트로 표현하면
a : (3,14) → (2,8) → (1,0)
b : (8,14) → (-3,10) → (10,6)

 

다항식 덧셈 (Polynomial Addition)

두 다항식을 더하는 알고리즘의 핵심은 지수 비교다.

1. a와 b의 노드를 각각 순회하며 지수를 비교
2. 지수가 같으면 계수를 더함
3. 지수가 큰 쪽의 항을 결과 리스트에 복사
4. 한쪽이 끝나면 남은 항들을 그대로 이어 붙임

PolyNode* padd(PolyNode *a, PolyNode *b) {
    PolyNode *rear, *temp, *c;
    rear = (PolyNode*)malloc(sizeof(PolyNode));
    c = rear;

    while (a && b) {
        temp = (PolyNode*)malloc(sizeof(PolyNode));
        if (a->expo == b->expo) {
            temp->expo = a->expo;
            temp->coef = a->coef + b->coef;
            a = a->link; b = b->link;
        } else if (a->expo > b->expo) {
            temp->expo = a->expo;
            temp->coef = a->coef;
            a = a->link;
        } else {
            temp->expo = b->expo;
            temp->coef = b->coef;
            b = b->link;
        }
        rear->link = temp;
        rear = temp;
    }

    // 남은 항 연결
    while (a) { rear->link = a; rear = a; a = a->link; }
    while (b) { rear->link = b; rear = b; b = b->link; }

    rear->link = NULL;
    return c->link;
}

 

예를 들면,

a(x) = 3x^14 + 2x^8 + 1
b(x) = 8x^14 - 3x^10 + 10x^6

// 결과 c(x) = 11x^14 - 3x^10 + 2x^8 + 10x^6 + 1

 

주의사항

연결 리스트로 다항식을 다룰 때, 사용이 끝난 후에는 반드시 노드를 해제해야 함.

void erase(PolyNode *ptr) {
    PolyNode *temp;
    while (ptr != NULL) {
        temp = ptr;
        ptr = ptr->link;
        free(temp);
    }
}

---

2. Available Space List (가용 공간 리스트)

• 연결 리스트는 malloc()을 통해 계속 새로운 노드를 동적 할당함.
• 하지만 노드를 자주 생성/삭제하면 
  → 메모리 단편화(memory fragmentation) 발생
  → 성능 저하 및 메모리 누수(memory leak) 위험이 생김. .

 

• 그래서 한 번에 여러 노드를 미리 만들어두고,
  사용하지 않는 노드를 가용 공간 리스트(available space list) 로 관리할 수 있음.

 

아이디어

• malloc/free 대신 getNode()와 retNode() 함수를 사용
• 가용 공간 리스트(avail)에 “빈 노드들”을 연결 형태로 저장
• 새 노드 필요 → avail에서 하나 pop
• 노드 삭제 → avail로 push

구현예시 

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

Node *avail = NULL; // 가용 리스트 헤드

// 새 노드 가져오기
Node* getNode() {
    Node *p;
    if (avail) {
        p = avail;
        avail = avail->link;
    } else {
        p = (Node*)malloc(sizeof(Node));
    }
    return p;
}

// 노드 반환하기
void retNode(Node *p) {
    p->link = avail;
    avail = p;
}

이 구조를 사용하면 메모리 재활용이 가능하고,
malloc/free 호출을 최소화해 성능을 높일 수 있음.

 

cerase() — 원형 리스트 지우기

원형 리스트는 끝이 NULL이 아니므로
일반적인 while (ptr != NULL) 루프를 사용할 수 없음.
대신 리스트를 순회하면서 각 노드를 avail 리스트에 반환함.

void cerase(Node **last) {
    Node *ptr = (*last)->link; // 첫 노드
    Node *temp;
    (*last)->link = avail;
    avail = ptr;
}

 

이 방식은 노드 개수에 상관없이 일정한 시간(O(1)) 안에
리스트를 지울 수 있음.

---

3. Additional List Operations (추가 리스트 연산)

연결 리스트는 기본 삽입/삭제 외에도 여러 연산이 가능함.

 

(1) 리스트 반전 (Inverting a List)

3개의 포인터(lead, middle, trail)을 사용하여 노드의 방향을 역전시킴.

Node* invert(Node *head) {
    Node *lead = head, *middle = NULL, *trail;
    while (lead != NULL) {
        trail = middle;
        middle = lead;
        lead = lead->link;
        middle->link = trail;
    }
    return middle; // 새로운 head
}

 => 리스트의 순서 뒤집힘.

 

(2) 리스트 연결 (Concatenation)

두 리스트를 하나로 합치는 연산.

Node* concat(Node *A, Node *B) {
    Node *temp = A;
    while (temp->link != NULL)
        temp = temp->link;
    temp->link = B;
    return A;
}

 

(3) 원형 리스트 삽입 (Circular Linked List Insertion)

원형 리스트는 마지막 노드가 처음 노드를 가리킴.
 -> 새 항을 맨 앞에 삽입할 때는 마지막 노드를 알고 있어야 함.

void insertFront(Node **last, int data) {
    Node *newNode = malloc(sizeof(Node));
    newNode->data = data;
    if (*last == NULL) {
        *last = newNode;
        newNode->link = newNode;
    } else {
        newNode->link = (*last)->link;
        (*last)->link = newNode;
    }
}

 

(4) 원형 리스트 길이 구하기

int length(Node *last) {
    if (last == NULL) return 0;
    Node *temp = last->link;
    int count = 0;
    do {
        count++;
        temp = temp->link;
    } while (temp != last->link);
    return count;
}