[자료구조] 연결리스트(2) : C언어

 

1. 원형 연결 리스트

 

정의 : 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트

=> 한 노드에서 다른 모든 노드로의 접근이 가능

=> 원형이기 때문에 다른 노드들을 거쳐서 결국 자기자신으로 되돌아 올 수 있음

=> 삭제나 삽입 시에는 항상 선행 노드를 가리키는 포인터가 필요

 

원형 연결 리스트

 

변형된 원형 연결 리스트

 

=> 마지막 노드는 헤드 포인터인 헤드가 가리키고 첫번째 노드는 화살표 연산자를 이용해서 head -> link로 가리킴

=> 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이하다.

 

변형된 연결 리스트

 

1. 원형 연결 리스트의 처음에 삽입

 

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; // (1)
		head->link =  node;	// (2)
	}
	return head;
}

 

(1) head->link가 가리키는 값 (처음엔 10을 가리킴)을 새로들어온 node->link가 가리키게 한다.(그래서 노드 40은 노드 10을 가리키게됨)

(2) 처음 노드 10을 가리키는 노드 30의 link가 새로운 node 40을 가리키게 함

 

2. 리스트의 끝에 삽입

 

원형 연결 리스트의 마지막에 삽입

=> 원형 연결 리스트는 처음과 끝이 불분명(원형이기 때문)

=> 따라서 head의 위치만 새로운 노드로 바꿔주면 새로운 노드가 마지막 노드가 됨(원형 연결리스트에서는 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;	// (1)
		head->link =  node;		    // (2)
		head =  node;		        // (3)
	}
	return head;	
}

 

(1) 처음엔 head가 노드 30이기 때문에 node -> link = head-> link는 노드 30이 가리키는 대상을 node->link가 가리키게 한다는 의미 그래서 새로운 node가 노드 10을 가리키게 됨

(2) head의 link를 node로 할당(그래서 노드 30의 link가 node 40을 가리키게 됨)

(3) head를 새로운 node로 지정함(node 40이 새로운 head가 됨)

 

(1), (2), (3)을 그림으로 표현

 

3. 테스트 프로그램

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct { 	// 노드 타입
	element data;
	struct ListNode *link;
} ListNode;

// 리스트의 항목 출력
void print_list(ListNode* head)
{
	ListNode* p;

	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (  p! = head );
	printf("%d->", p->data); // 마지막 노드
}
// 앞부분 삽입
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;
}
// 뒷부분 삽입
istNode* 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;	
}

int main(void)
{
	ListNode *head = NULL;

	// list = 10->20->30->40
	head = insert_last(head, 20);
	head = insert_last(head, 30);
	head = insert_last(head, 40);
	head = insert_first(head, 10);
	print_list(head);
	return 0;
}

// 결과는 10 -> 20 -> 30 -> 40 ->

 

2. 이중 연결 리스트

 

탄생배경 :

단순 연결 리스트는 후속 노드를 찾기가 쉽지만 선행 노드를 찾기가 어려움

원형 연결 리스트도 거의 전체 노드를 거쳐서 돌아와야 함

 

=> 이중 연결 리스트는 특정 노드에서 양방향으로 자유롭게 이동 가능

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

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

 

특징 :

=> 헤드 포인터와는 다른 헤드 노드(head node)라는 특별한 노드를 추가하여 사용

=> 헤드 포인터는 첫번쨰 노드를 가리키는 포인터

=> 헤드 노드가 존재하면 삽입, 삭제가 간단해지며 헤드 노드는 데이터를 가지고 있지 않음

(그래서 헤드 노드는 가리키는 목적만 가진 노드이다.)

 

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;  // (1)
	newnode->rlink = before->rlink;  // (2)
	before->rlink->llink = newnode;  // (3)
	before->rlink = newnode;  // (4)
}

 

삽입하려는 자리의 왼쪽에 before노드를 지정해 주기 때문에 한개 노드를 삽입해 주기 위해 2개의 기존 노드와의 관계가 필요합니다.

(1) newnode의 링크가 before를 가리키도록 지정합니다.

(2) before의 rlink가 가리키는 대상이 newnode의 rlink가 되도록 합니다.( 그래서 after노드의 llink를 newnode의 rlink가 가리키게 됩니다.)

(3) before의 rlink가 가리키는 노드의 llink가 newnode가 되도록 합니다.(즉 after노드의 llink가 newnode의 rlink를 가리키게 됩니다.)

(4) before 노드의 rlink가 newnode를 가리키게 됩니다.

 

삽입 연산의 과정을 그림으로 표현

 

삭제 연산 코드

 

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

 

(1) removed의 rlink가 가리키는 값을 removed의 llink가 가리키는 노드의 rlink가 할당하게 합니다.(before의 rlink가 after의 llink를 가리키게 됩니다.)

(2) removed의 llink가 가리키는 노드를 removed의 rlink가 가리키는 노드의 llink가 가리키도록 지정합니다.(그래서 after의 llink가 before의 rlink를 가리키게 됩니다.)

 

삭제연산의 과정을 그림으로 표현

 

3. 연결 리스트로 구현한 스택

 

연결리스트로 스택 구현(linked stack)

=> 크기가 제한되지 않음

 

 

노드 정의 코드

 

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

typedef struct {
	StackNode* top;
} LinkedStackType;

 

*top은 인덱스 번호를 나타내는 정수에서 노드를 가리키는 포인터로 변경

 

1. 삽입 연산

 

연결된 스택은 단순 연결 리스트에서 맨 앞에서 삽입하는 것과 동일

=> 헤드 포인터가 top이라는 이름으로 불리는 것만 차이가 있음

 

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

 

(2) 새로운 노드에 값 저장

(3) top이 가리키는 노드를 새로운 노드인 temp의 link도 가리키게 함

(4) top을 temp로 지정

 

삽입 연산 그림

 

2. 삭제 연산

 

top의 값을 top->link로 변경

기존의 top이 가리키던 노드를 해제

top 포인터가 NULL이면 스택은 공백 상태

 

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

 

(1) top노드가 가리키는 노드를 temp 노드가 가리키게 함

(2) 값 반환을 위한 삭제할 노드의 값 저장

(3) top노드의 link가 가리키는 노드를 top노드로 할당(그림 기준으로 C노드를 가리키는 top->link에 top을 대입시켜 top이 C노드가 되도록 합니다.)

(4) 삭제할 노드였던 D노드를 메모리 해제

(5) 삭제한 노드의 값 리턴

 

 

4. 연결 리스트로 구현한 큐

 

연결 리스트로 구현한 큐(linked Queue)

=> 연결된 큐는 길이의 제한이 없으며 링크 필드를 사용하기 때문에 노드 수에 따라 더 많은 공간을 ㅊ차지

=> 단순 연결 리스트에 2개의 포인터를 추가(front, rear)

*공백 상태인 경우에는 front == NULL && rear == NULL

 

연결리스트로 구현된 큐

 

연결된 큐 정의

 

typedef int element; // 요소의 타입
typedef struct QueueNode { // 큐의 노드의 타입
    element data;
    struct QueueNode *link;
} QueueNode;

typedef struct { // 큐 ADT 구현
		QueueNode *front, *rear;
} LinkedQueueType;

삽입 연산 순서

 

=> 새로운 노드를 생성하고 해당 노드에 데이터를 저장

=> 연결 리스트의 마지막에 노드를 추가(rear 포인터가 새로운 노드를 가리킴)

 

 

삽입 연산 코드

 

void enqueue(LinkedQueueType *q, element data) {
	QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    temp->data = data; // (1)
    temp->link = NULL; // (2)
    if (is_empty(q)) {
        q->front = temp;
        q->rear = temp;
    }
 	else {
	q->rear->link = temp; // (3)
        q->rear = temp; // (4)
    }
}

 

(1) 데이터 저장

(2) 새로운 노드 temp의 link에 NULL값 부여

(3) 마지막 노드인 rear 노드의 link가 새로운 노드인 temp를 가리키게 함(그림에서 D노드의 link가 E노드를 가리키게 됩니다.)

(4) 마지막 노드를 가리키는 rear포인터가 새로운 노드인 temp를 가리키게 함(마지막 노드는 새로운 노드인 temp가 됩니다.)

 

삽입 연산을 그림으로 표현

삭제 연산

 

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

 

(1) 첫번째 노드를 가리키는 front포인터가 temp를 가리키도록 함

(3) 삭제할 노드의 데이터를 반환을 위해 저장

(4) front포인터가 가리키는 노드의 link가 가리키는 노드로 front포인터를 재정의(그림기준으로 front가 A노드에서 B노드를 가리키게 됩니다.)

 

삭제 함수를 나타낸 그림

 

마무리

 

원형 연결리스트와 이중 연결 리스트, 연결 리스트로 구현한 스택, 연결 리스트로 구현한 큐까지 알아보았습니다.

 

다음 포스팅에서는 트리를 다루는 포스트를 올려보겠습니다.