Linked List II(Doubly linked list)

안효빈·2024년 6월 19일

자료구조

목록 보기

6/10

1. 이중 연결 리스트

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

이중 연결 리스트의 장단점은 다음과 같다

장점: 양방향 검색이 가능함
단점: 공간을 많이 차지해 코드가 복잡해짐

이중 연결 리스트는 이렇게 생겼다.

head node라는 특별한 노드가 존재한다. 삽입과 삭제 연산을 용이하게 해준다.

헤드포인터: 첫 번째 노드를 가리키는 포인터
헤드노드: 데이터를 가지고 있지 않는 특별한 노드

이중 연결 리스트의 노드는 왼쪽 링크필드, 데이터 필드, 오른쪽 링크필드로 구성되어 있고, 링크필드는 포인터로 이뤄진다.

이중 연결 리스트에서 임의의 노드를 가리키는 포인터를 p라 하면, 다음의 관계가 항상 성립한다.

p = p->llink->rlink = p->rlink->llink

노드의 구조를 구조체를 이용하여 정의하면,llink는 선행노드를, rlink는 후속 노드를 가리킨다.

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

삽입 연산
링크 필드의 값을 바꾸면 된다. 새로 만들어진 노드의 링크를 먼저 바꾸면 된다.

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 노드의 다음 노드의 llink 포인터를 newnode로 설정
    before->rlink = newnode;
}

삭제 연산

void ddelete(DListNode* head, DListNode* removed)
{
	if(removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

전체 프로그램
main()의 head는 포인터가 아닌 구조체 변수임을 유의해야 한다. 헤더 노드의 링크필드들이 자기 자신을 가리키도록 초기화를 해야 한다.

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

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

//이중 연결 리스트를 초기화
void init(DListNode* phead)
{
	phead->llink = phead;
    phead->rlink = phead;
}

//이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
	DListNode* p;
    for(p = phead->rlink; p != phead; p = p->rlink){
    	printf("<-| |%d| |->", p->data);
    }
    printf("\n");
}

//새로운 데이터를 노드 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);
}

//이중 연결 리스트 테스트 프로그램
int main(void)
{
	DListNode* head = (DListNode *)malloc(sizeof(DListNode));
    init(head);
    printf("추가 단계\n");
    for(int i = 0; i < 5; i++){
    	//헤드 노드의 오른쪽에 삽입
        dinsert(head, i);
        print_dlist(head);
    }
    printf("\n삭제 단계\n");
    for(int i = 0; i < 5; i++){
    	print_dlist(head);
        ddelete(head, head->rlink);
    }
    free(head);
    return 0;
}

2. 예제: mp3재생 프로그램 만들기

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

typedef char element[100];
typedef struct DListNode{
	element data;
    struct DListNode* llink;
    struct DListNode* rlink;
} DListNode;

DListNode* current;

//이중 연결 리스트를 초기화
void init(DListNode* phead)
{
	phead->llink = phead;
    phead->rlink = phead;
}

//이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
	DListNode* p;
    for( p = phead->rlink; p != phead; p = p->rlink){
    	if(p == current)
        	printf("<-| #%s# |->", p->data);
        else
        	printf("<-| %s |-> ", p->data);
    }
    printf("\n");
}

//노드 newnode를 노드 before의 오른쪽에 삽입한다.
void dinsert(DListNode *before, element data)
{
	DListNode *newnode  = (DListNode *)malloc(sizeof(DListNode));
    strcpy(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);
}

//이중 연결 리스트 테스트 프로그램
int main(void)
{
	char ch;
    DListNode* head = (DListNode *)malloc(sizeof(DListNode));
    init(head);
    
    dinsert(head, "Mamamia");
    dinsert(head, "Dancing Queen");
    dinsert(head, "Fernando");
    
    current = head->rlink;
    print_dlist(head);
    
    do{
    	printf("\n명령어를 입력하시오(<, >, q): ");
        ch = getchar();
        if(ch == '<'){
        	current = current->llink;
            if(current == head)
            	current = current->llink;
        }
        else if(ch == '>'){
        	current = current->rlink;
            if(current == head)
            	current = current->rlink;
        }
        print_dlist(head);
        getchar();
    } while (ch != 'q');
}

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

연결 리스트로 스택을 구현하면 크기가 제한되지 않는 장점이 있다.
top은 노드를 가리키는 포인터로 사용된다.

LinkedStackType 구조체 선언

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

typedef struct{
	StackNode *top;
} LinkedStackType;

삽입과 삭제 구현
삽입 연산에서는 먼저 노드를 만들고, 이 노드를 첫 번째 노드로 삽입한다.
즉, top의 값을 temp->link에 복사한 다음, temp를 top에 복사하면 된다.
삭제 연산에서는 top의 값을 top->link로 바꾸고, 기존의 top이 가리키는 노드의 동적 메모리를 해제하면 된다.
전체 프로그램

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

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

typedef struct{
	StackNode *top;
}LinkedStackType;

//초기화 함수
void init(LinkedStackType *s)
{ 
	s->top = NULL;
}

//공백 상태 검출 함수
int is_empty(LinkedStackType *s)
{
	return (s->top == NULL);
}

//포화 상태 검출 함수
int is_full(LinkedStackType *s)
{
	return 0;
}

//삽입 함수
void push(LinkedStackType *s, element item)
{
	StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    temp->data = item;
    temp->link = s->top;
    s->top = temp;
}
void print_stack(LinkedStackType *s)
{
	for(StackNode *p = s->top; p != NULL; p = p->link)
    	printf("%d->", p->data);
    printf("NULL \n");
}

//삭제 함수
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;
    }
}

//피크 함수
element peek(LinkedStackType *s)
{
	if(is_empty(s)){
    	fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else{
    	return s->top->data;
    }
}

//주 함수
int main(void)
{
	LinkedStackType s;
    init(&s);
    push(&s, 1); print_stack(&s);
    push(&s, 2); print_stack(&s);
    push(&s, 3); print_stack(&s);
    push(&s); print_stack(&s);
    push(&s); print_stack(&s);
    push(&s); print_stack(&s);
    return 0;
}

4. 연결리스트로 큐 구현

연결리스트로 구현된 큐는 배열로 구현된 큐에 비해 크기가 제한되지 않는다는 장점을 갖고 있다. 다만, 코드가 더 복잡하고 메모리 공간을 많이 사용하는 단점이 있다.

다음은 연결리스트로 구현된 큐의 포인터들이다.

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 모두 새로운 노드를 가리키도록 해야 한다. 아니라면 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의 링크값으로 대입한다.

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;
    }
}

연결된 큐 프로그램
연결 리스트의 경우, 메모리 할당과정에서 오류가 있지 않는 한 포화상태는 없다고 본다. 따라서 포화 상태 검출 함수 is_full()은 항상 0을 반환한다.

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

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

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

//큐 초기화 함수
void init(LinkedQueueType *q)
{
	q->front = q->rear = 0;
}

//공백 상태 검출 함수
int is_empty(LinkedQueueType *q)
{
	return(q->front == NULL);
}

//포화 상태 검출 함수
int is_full(LinkedQueueType *q)
{
	return 0;
}

//삽입 함수
void enqueue(LinkdedQueueType *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;
    }
}

//삭제 함수
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;
    }
}

void print_queue(LinkedQueueType *q)
{
	QueueNode *p;
    for(p = q->front; p != NULL; p = p->link)
    	printf("%d->", p->data);
    printf("NULL\n");
}

//연결된 큐 테스트 함수
int main(void)
{
	LinkedQueueType queue;
    
    init(&queue);
    
    enqueue(&queue, 1); print_queue(&queue);
    enqueue(&queue, 2); print_queue(&queue);
    enqueue(&queue, 3); print_queue(&queue);
    enqueue(&queue); print_queue(&queue);
    enqueue(&queue); print_queue(&queue);
    enqueue(&queue); print_queue(&queue);
    return 0;
}

안효빈

피넛버터

이전 포스트

Linked list II(Circular linked list)

다음 포스트