이중 연결 리스트

단순 열결 리스트의 문제점

1. 선행 노드를 찾기가 어렵다

삽입이나 삭제 시에는 반드시 선행 노드가 필요

정의

하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트

장점

링크가 양방향이므로 양방향으로 검색이 가능

단점

공간을 많이 차지하고 코드가 복잡

실제 사용되는 이중연결 리스트의 형태

헤드노드

데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드.
삽입 및 삭제 시, 헤드 포인터의 NULL 여부에 상관없이 프로그램 가능
1. 헤드 포인터와의 구별 필요
2. 공백 상태에서는 헤드 노드만 존재

이중연결리스트의 Struct

typedef int element;
typedef struct DlistNode {
	element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
 } DlistNode;

삽입 연산

// 노드 new_node를 노드 before의 오른쪽에 삽입
void insert_node(DlistNode *before, DlistNode *new_node)
{
	new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node; // new_node->rlink->llink = new_node
    before->rlink = new_node;
}

삭제 연산

// 노드 removed를 삭제
void remove_node(DlistNode *phead_node, DlistNode *removed)
{
	if (removed == phead_node ) // empty list
    	return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

---

연결리스트의 응용 : 다항식

다항식을 컴퓨터로 처리하기 위한 자료구조
하나의 다항식을 하나의 연결리스트로 표현
A=3x^2 + 2x^8 + 1

Struct

typedef struct ListNode {
	int coef;
    int expon;
    struct ListNode *link;
 } ListNode;
 
 ListNode *A, *B;

다항식의 덧셈 구현

1. p.expon == q.expon:

   두 계수를 더해서 0이 아니면 새로운 항을 만들어 결과 다항식 C에 추가. 그리고 p와 q는 모두 다음 항으로 이동

2. p.expon < q.expon:

   q가 지시하는 항을 새로운 항을 복사하여 결과 다항식 C에 추가. 그리고 q만 다음 항으로 이동

3. p.expon > q.expon:

   p가 지시하는 항을 새로운 항으로 복사하여 결과 다항식 C에 추가. 그리고 p만 다음 항으로 이동

Insert

typedef struct ListHeader {
	int length;
   	ListNode *head;
    ListNode *tail;
} ListHeader;

void init(ListHeader *plist) {
	plist->length = 0;
    plist->head = plist->tail = NULL;
}
// coef는 계수, expon는 지수
void insert_node_last(ListHeader *plist, int coef, int expon) {
	ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
    if (temp == NULL )
    	error("메모리 할당 에러");
    temp->coef = coef;
    temp->expon = expon;
    temp->link = NULL;
    if (plist->tail == NULL) {
    	plist->head = plist->tail = temp;
    } else {
    	plist->tail->link = temp;
        plist->tail = temp;
    }
    plist->length++;
}

---

다항식 덧셈

// list3 = list1 + list2
void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3) {
	ListNode *a = plist1->head;
	ListNode *b = plist2->head;
    int sum;
    while (a && b) { 
    	if (a->expon == b->expon) {
        	sum = a->coef + b->coef;
            if (sum != 0)
            	insert_node_last(plist3, sum, a->expon);
            a=a->link; b=b->link;
        } else if (a->expon > b->expon) {
        	insert_node_last(plist3, a->coef, a->expon);
            a=a->link;
        } else {
        	insert_node_last(plist3, b->coef, b->expon);
            b=b->link;
        }
    }
    // a나 b중 하나가 먼저 끝나게 되면 남아있는 항들을 모두 결과 다항식으로 복사
    while (a != NULL) {
    	insert_node_last(plist3, a->coef, a->expon);
        a=a->link;
    }
    while (b != NULL) {
    	insert_node_last(plist3, b->coef, b->expon);
        b=b->link;
    }
}

다항식 출력

void poly_print(ListHeader *plist) {
	ListNode *p = plist->head;
    while (p) {
    	printf("%d %d\n", p->coef, p->expon);
        p=p->link;
    }
}

---