[CS과목/자료구조] 07 연결 리스트 2

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

7.1 원형 연결 리스트

 원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 즉 마지막 노드의 링크 필드가 NULL이 아니라 첫 번째 노드 주소가 되는 리스트이다. 원형 연결 리스트가 특히 유용한 경우는 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다는 것이다. 원형 연결 리스트에서 헤드 포인터가 마지막 노드를 가리키고, 첫 번째 노드는 head->link가 가리키고 있으므로, 리스트의 처음과 끝에 노드를 삽입할 수 있다.

 

원형 리스트의 처음에 삽입

ListNode* insert_first(ListNode* head, element data)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head; // 변경된 헤드 포인터를 반환한다.
}

 

원형 리스트의 끝에 삽입

ListNode* insert_last(ListNode* head, element data)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

 

 원형 리스트는 마지막 노드의 링크가 NULL이 아니기 때문에 리스트의 끝에 도달했는지를 검사하려면 헤드 포인터와 비교하여야 한다. 이를 위해 do-while 루프를 사용한다.

 

7.3 이중 연결 리스트

 단순 연결 리스트에서는 어떤노드에서 후속 노드를 찾기 쉽지만, 선행 노드를 찾으려면 구조상 어렵다. 이중 연결 리스트는 이러한 문제점을 해결하기 위하여 만들어진 자료구조이다. 이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다. 링크가 양방향이므로 양방향 검색이 가능해진다. 단점으로는 공간을 많이 차지하고 코드가 복잡해진다. 

 이중 연결 리스트에는 헤드 노드(head node)라는 특별한 노드를 추가하는 경우가 많다. 헤드 포인터와는 구별하여야 한다. 헤드 포인터는 리스트의 첫 번째 노드를 가리키는 포인터이고, 헤드 노드는 데이터를 가지고 있지 않는 특별한 노드를 추가하는 것이다. 헤드 노드가 존재하게 되면 삽입, 삭제 알고리즘이 간편해진다.

 이중 연결 리스트를 구현해보자. 먼저 노드의 구조를 정의해야 한다. 이중 연결 리스트에서의 노드는 3개의 필드(왼쪽 링크 필드, 데이터 필드, 오린쪽 링크 필드)로 이루어져 있다. 링크 필드는 포인터로 이루어진다. 노드의 왼쪽 링크 필드 llink는 바로 선행 노드를 가리키며, 오른쪽 링크 필드 rlink는 후속 노드를 가리킨다.

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

 

삽입 연산

 새로 만들어진 노드의 링크는 아무런 정보다 가지고 있지 않기 때문에 먼저 변경하여도 안전하다.

// 새로운 데이터를 노드 before의 오른쪽 삽입한다.
void dinsert(DListNode* before, element data)
{
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}

 

삭제 연산

// 노드 removed를 삭제한다.
void ddelete(DListNode* head, DListNode* removed)
{
    if (removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

 

7.5 연결 리스트로 구현한 스택

 연결 리스트를 이용하여 만든 스택을 연결된 스택(linked stack)이라고 한다. 연결 리스트를 이용하여 스택을 만들게 되면 크기가 제한되지 않는단ㄴ 장점이 있다. 동적 메모리 할당만 할 수 있으면 스택에 새로운 요소를 삽입할 수 있다. 반면에 연결 리스트를 이용한 스택은 동적 메모리 할당이나 해제를 해야 하므로 삽입이나 삭제 시간은 더 걸린다.

 연결된 스택은 기본적으로 연결 리스트이기 때문에 다음과 같이 노드를 정의한다. 노드는 우리가 저장하고 싶은 데이터 필드와 다음 노드를 가리키기 위한 포인터가 들어 있는 링크 필드로 구성된다. 또한 top은 더이상 정수가 아니고 노드를 가리키는 포인터로 선언된다.

typedef int element;

typedef struct StackNode {
    element data;
    struct StackNode *link;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedStackType;

 

삽입 연산

 연결된 스택은 개념적으로 단순 연결 리스트에서 매 앞에 데이터를 삽입하는 것과 동일하다. 삽입 연산에서는 먼저 동적 메모리 할당으로 노드를 만들고 이 노드를 첫 번째 노드로 삽입한다.

// 삽입 함수
void push(LinkedStackType *s, element item)
{
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    temp->data = item;
    temp->link = s->top;
    s->top = temp;
}

 

삭제 연산

 삭제 연산에서는 top의 값을 top->link로 바꾸고 기존의 top이 가리키는 노드를 동적 메모리 해제하면 된다. 연결된 스택에서 공백상태는 연결 리스트와 마찬가지로 top 포인터가 NULL인 경우이다.

// 삭제 함수
element pop(LinkedStackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        int data = temp->data;
        s->top = s->top->link;
        free(temp);
        return data;
    }
}

 

7.6 연결 리스트로 구현한 큐

  연결 리스트로 만들어진 큐를 연결된 큐(linked queue)라고 한다. 연결 리스트로 구현된 큐는 배열로 규현된 큐에 비하여 크기가 제한되지 않는다는 장점을 지니고 있다. 반면 배열로 규현된 큐에 비하여 코드가 약간 더 복잡해지고, 링크 필드 때문에 메모리 공간을 더 많이 사용한다. 기본적인 구조는 단순 연결 리스트에다가 2개의 포인터를 추가한 것과 같다. front 포인터는 삭제와 관련되며 rear 포인터는 삽입과 관련된다. 이는 일반적인 큐와는 반대이다. front는 연결 리스트의 맨 앞에 있는 요소를 가리키며, rear는 맨 뒤에 있는 요소를 가리킨다. 큐에 요소가 없는 경우에는 front와 rear는 NULL값이 된다.

 

연결된 큐 정의

typedef int element;
typedef struct QueueNode {
    element data;
    struct QueueNode *link;
} QueueNode;

typedef struct {
    QueueNode *front, *rear;
} LinkedQueueType;

 

삽입 연산

 삽입 연산은 먼저 동적 메모리 할당을 통하여 새로운 노드를 생성한 다음, 데이터를 저장하고 연결 리스트의 끝에 새로운 노드를 추가하면 된다. 만약 큐가 공백상태이면(즉 front와 rear가 모두 NULL이면) front와 rear 모두 새로운 노드를 가리키도록 해야 한다. 기존의 노드가 있는 경우라면 rear가 가리키고 있는 노드의 링크 필드와 rear를 새로운 노드를 가리키도록 변경하면 된다.

// 삽입 함수
void enqueue(LinkedQueueType *q, element data)
{
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->link = NULL;
    if (is_empty(q)) {
        q->front = temp;
        q->rear = temp;
    }
    else {
        q->rear->link = temp; // 순서가 중요
        q->rear = temp;
    }
}

 

삭제 연산

 삭제 연산은 연결 리스트의 처음에서 노드를 꺼내오면 된다. 삭제 연산은 먼저 큐가 공백상태인가를 검사하여야 한다. 공백상태가 아니라면 front가 가리키는 노드를 temp가 가리키도록 하고 front는 front의 링크값으로 대입한다. 그런 다음 temp가 가리키는 노드로부터 데이터를 꺼내오고 동적 메모리 해제를 통하여 이 노드를 삭제하면 된다.

// 삭제 함수
element dequeue(LinkedQueueType *q)
{
    QueueNode *temp =q-> front;
    element data;
    if (is_empty(q)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        data = temp->data;
        q->front = q->front->link;
        if (q->front == NULL)
            q->rear = NULL;
        free(temp);
        return data;
    }
}