Notice
Recent Posts
Recent Comments
Link
«   2025/11   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30
Tags more
Archives
Today
Total
관리 메뉴

SYDev

[Data Structure] Chapter 05: 원형, 양방향 연결 리스트 본문

Data Structure & Algorithm/Data Structure

[Data Structure] Chapter 05: 원형, 양방향 연결 리스트

시데브 2023. 8. 12. 12:49
단순 연결 리스트의 개념을 확장한 원형, 양방향 연결 리스트를 구현해보자.

 

자료구조를 구현할 때, 먼저 그림으로 그려보고 구조를 파악하는 것이 상당히 도움이 되었다.

 

 

원형 연결 리스트(Circular Linked List)

  • 원형 연결 리스트의 기본 구조와 내부 함수는 다음과 같이 도식화할 수 있다.

원형 연결 리스트의 구조

 

 파일명: CLinkedList.h

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node * next;
} Node;

typedef struct _CLL
{
    Node * tail;
    Node * cur;
    Node * before;
    int numOfData;
}   CList;

typedef CList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);  //꼬리에 노드 추가
void LInsertFront(List * plist, Data data); //머리에 노드 추가

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);

Data LRemove(List * plist);
int LCount(List * plist);


#endif

 

 파일명: CLinkedList.c

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


void ListInit(List * plist)
{
    plist -> tail = NULL;
    plist -> cur = NULL;
    plist -> before = NULL;
    plist -> numOfData = 0;
}

void LInsert(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;

    if(plist -> tail == NULL)
    {
        newNode -> next = newNode;
        plist -> tail = newNode;
    }
    else
    {
        newNode -> next = plist -> tail -> next;
        plist -> tail -> next = newNode;
        plist -> tail = newNode;
    }
    (plist -> numOfData)++;
}

void LInsertFront(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;

    if(plist -> tail == NULL)
    {
        newNode -> next = newNode;
        plist -> tail = newNode;
    }
    else
    {
        newNode -> next = plist -> tail -> next;
        plist -> tail -> next = newNode;
    }
    (plist -> numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if(plist -> tail == NULL)   //tail이 NULL이 아니면 비어있을 수가 없는 구조
        return FALSE;
    
    plist -> before = plist -> tail;
    plist -> cur = plist -> tail -> next;

    *pdata = plist -> cur -> data;
    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
    if(plist -> tail == NULL)   //tail이 NULL이 아니면 비어있을 수가 없는 구조
        return FALSE;

    plist -> before = plist -> cur;
    plist -> cur = plist -> cur -> next;

    *pdata = plist -> cur -> data;
    return TRUE;
}

Data LRemove(List * plist)
{
    Node * rpos = plist -> cur;
    Data rdata = rpos -> data;

    if(rpos == plist -> tail)
    {
        if(rpos -> next = rpos)
        {
            plist -> tail = NULL;
        }
        else

            plist->tail = plist->before;        
    }
    plist->before->next = plist->cur->next;
    plist->cur = plist->before;

    free(rpos);
    (plist -> numOfData)--;

    return rdata;
}

int LCount(List * plist)
{
    return plist -> numOfData;
}

 

 파일명: CLinkedListMain.c

#include <stdio.h>
#include "CLinkedList.h"

int main(void)
{
	// List의 생성 및 초기화 /////////////////////////////
	List list;
	int data, i, nodeNum;
	ListInit(&list);

	// 5개의 데이터 저장 /////////////////////////////
	LInsert(&list, 3);  
	LInsert(&list, 4);  
	LInsert(&list, 5);
	LInsertFront(&list, 2);
	LInsertFront(&list, 1);

	// 리스트에 저장된 데이터를 연속 3회 출력 /////////////////////////
	if(LFirst(&list, &data))   
	{
		printf("%d ", data);
		
		for(i=0; i<LCount(&list)*3-1; i++)	//원형 연결 리스트라서 가능한 구조
		{
			if(LNext(&list, &data))
				printf("%d ", data);
		}
	}
	printf("\n");

	// 2배수를 모두 찾아서 삭제 //////////////////////////
	nodeNum = LCount(&list);
	
	if(nodeNum != 0)
	{
		LFirst(&list, &data);
		if(data%2 == 0)
			LRemove(&list);

		for(i=0; i<nodeNum; i++)
		{
			LNext(&list, &data);
			if(data%2 == 0)
				LRemove(&list);
		}
	}

	// 전체 데이터 1회 출력 ////////////////////////
	if(LFirst(&list, &data))   
	{
		printf("%d ", data);
		
		for(i=0; i<LCount(&list)-1; i++)	//원형 연결 리스트라서 가능한 구조
		{
			if(LNext(&list, &data))
				printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 
1 3 5

 

문제 05-1

  • 직원 정보를 등록할 수 있다. 직원 정보는 사번과 이름으로 구성
  • 직원은 등록된 순서대로 당직을 선다.
  • 직원의 이름과 하나의 숫자를 이용해서 당직자를 확인

 파일명: Employee.h

#ifndef __EMPLOYEE_H__
#define __EMPLOYEE_H__

typedef struct __employee
{
    char name[30];
    int num;
} Employee;

#endif

 

 파일명: WhoDuty.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CLinkedList.h"
#include "Employee.h"

void WhoIsOnDuty(List * plist, char * name, int day);

int main(void)
{
	// List의 생성 및 초기화 /////////////////////////////
	List list;
	ListInit(&list);
	int i;
	Data data;

	data = (Employee*)malloc(sizeof(Employee));
	strcpy(data->name,"상영");
	data->num = 1;
	LInsert(&list, data);

	data = (Employee*)malloc(sizeof(Employee));
	strcpy(data->name,"민수");
	data->num = 2;
	LInsert(&list, data);

	data = (Employee*)malloc(sizeof(Employee));
	strcpy(data->name,"현규");
	data->num = 3;
	LInsert(&list, data);

	data = (Employee*)malloc(sizeof(Employee));
	strcpy(data->name,"상호");
	data->num = 4;
	LInsert(&list, data);	

	//민수가 당직을 하고 7일 뒤 당직
	WhoIsOnDuty(&list, "민수", 10);

	//상호가 당직을 하고 3일 뒤 당직
	WhoIsOnDuty(&list, "상호", 3);

	printf("\n\n");

	return 0;
}

void WhoIsOnDuty(List * plist, char * name, int day)
{	
	Employee * pemp = (Employee*)malloc(sizeof(Employee));
	LFirst(plist, &pemp);
	while(1)
	{
		if(strcmp(pemp->name , name) == 0)
			break;
		else
			LNext(plist, &pemp);
	}

	Employee * pemp1 = pemp;

	for(int i=0; i<day; i++)
	{
		LNext(plist, &pemp);
		printf("%s ",pemp -> name);
	}

	printf("\n");
	printf("%s가 당직을 선 후로 %d일 뒤 당직: %s \n", pemp1->name, day, pemp->name);
}
현규 상호 상영 민수 현규 상호 상영 민수 현규 상호 
민수가 당직을 선 후로 10일 뒤 당직: 상호 
상영 민수 현규 
상호가 당직을 선 후로 3일 뒤 당직: 현규

 나머지 헤더파일과 함수구현 파일은, 헤더파일에 Employee.h 헤더파일 선언문 추가에 typedef Data 변경을 제외하고 동일하다.

 

 

양방향 연결 리스트(Doubly Linked List)

  • 원형 연결 리스트의 기본 구조와 내부 함수는 다음과 같이 도식화할 수 있다.

양방향 연결 리스트 구조

파일명: DBLinkedList.h

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node * next;
    struct _node * prev;
} Node;

typedef struct _DLinkedList
{
    Node * head;
    Node * cur;
    int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data); 

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);

int LCount(List * plist);

#endif

 

 파일명: DBLinkedList.c

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


void ListInit(List * plist)
{
    plist -> head = NULL;
    plist -> numOfData = 0;
}

void LInsert(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;

    if(plist -> head == NULL)
    {
        newNode -> prev = NULL;
        newNode -> next = NULL;
        plist -> head = newNode;
    }
    else
    {
        newNode -> next = plist -> head;
        plist -> head -> prev = newNode;
        plist -> head = newNode;
        newNode -> prev = NULL;
    }
    (plist -> numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if(plist -> head == NULL)   
        return FALSE;
    
    plist -> cur = plist -> head;
    *pdata = plist -> cur -> data;
    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
    if(plist -> cur -> next == NULL)  
        return FALSE;
    else
    {
        plist->cur = plist->cur->next;
        *pdata = plist->cur->data;
        return TRUE;
    }
}

int LPrevious(List * plist, Data * pdata)
{
    if(plist -> cur -> prev == NULL)  
        return FALSE;
    else
    {
        plist->cur = plist->cur->prev;
        *pdata = plist->cur->data;
        return TRUE;
    }
}

int LCount(List * plist)
{
    return plist -> numOfData;
}

 

 파일명: DBLinkedListMain.c

#include <stdio.h>
#include "DBLinkedList.h"

int main(void)
{
	List list;
	int data;
	ListInit(&list);

	LInsert(&list, 1);  
	LInsert(&list, 2);  
	LInsert(&list, 3);
	LInsert(&list, 4);  
	LInsert(&list, 5);  
	LInsert(&list, 6);
	LInsert(&list, 7);  
	LInsert(&list, 8);  

	if(LFirst(&list, &data))   
	{
		printf("%d ", data);
		
		while(LNext(&list, &data))
			printf("%d ", data);
		
		while(LPrevious(&list, &data))
			printf("%d ", data);
		printf("\n\n");
	}

	return 0;
}
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8

 

문제 05-2

  • head와 tail에 dummy node가 있는 양방향 연결 리스트를 구현해보자.
  • 똑같이 그림 그려서 구현했지만, 이번에는 생략하겠다.

 

 파일명: DBDLinkedList.h

#ifndef __DBD_LINKED_LIST_H__
#define __DBD_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node * next;
    struct _node * prev;
} Node;

typedef struct _dbDLinkedList
{
    Node * head;
    Node * tail;
    Node * cur;
    int numOfData;
} DBDLinkedList;

typedef DBDLinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data); 

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);

Data LRemove(List * plist);
int LCount(List * plist);

#endif

 

 파일명: DBDLinkedList.c

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


void ListInit(List * plist)
{
    plist -> head = (Node*)malloc(sizeof(Node));
    plist -> tail = (Node*)malloc(sizeof(Node));

    plist -> head -> next = plist -> tail;
    plist -> tail -> prev = plist -> head;

    plist -> numOfData = 0;
}

void LInsert(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;

    plist -> tail -> prev -> next = newNode;
    newNode -> prev = plist -> tail -> prev;

    plist -> tail -> prev = newNode;
    newNode -> next = plist -> tail;

    (plist -> numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if(plist -> head -> next == plist -> tail)   
        return FALSE;
    
    plist -> cur = plist -> head -> next;
    *pdata = plist -> cur -> data;
    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
    if(plist -> cur -> next == plist -> tail)  
        return FALSE;

    plist -> cur = plist -> cur -> next;
    *pdata = plist->cur->data;
    return TRUE;
}

Data LRemove(List * plist)  //연속 호출 불가능!!
{
    Node * rpos = plist -> cur;
    Data rdata = rpos -> data;

    rpos -> next -> prev = rpos -> prev;
    rpos -> prev -> next = rpos -> next;

    plist -> cur = rpos -> prev;

    free(rpos);
    (plist -> numOfData)--;
    return rdata;
}

int LCount(List * plist)
{
    return plist -> numOfData;
}

 

 파일명: DBDLinkedListMain.c

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

int main(void)
{
	List list;
	int data;
	ListInit(&list);

	LInsert(&list, 1);  
	LInsert(&list, 2);  
	LInsert(&list, 3);
	LInsert(&list, 4);  
	LInsert(&list, 5);  
	LInsert(&list, 6);
	LInsert(&list, 7);  
	LInsert(&list, 8);  

	if(LFirst(&list, &data))   
	{
		printf("%d ", data);
		
		while(LNext(&list, &data))
			printf("%d ", data);

		printf("\n\n");
	}

	if(LFirst(&list, &data))
	{
		if(data%2 == 0)
			LRemove(&list);
		
		while(LNext(&list, &data))
		{
			if(data%2==0)
				LRemove(&list);
		}
	}

	if(LFirst(&list, &data))
	{
		printf("%d ", data);

		while(LNext(&list, &data))
			printf("%d ", data);

		printf("\n\n");
	}

	free(list.head);
	free(list.tail);

	return 0;
}
1 2 3 4 5 6 7 8 

1 3 5 7

 

참고자료

  • 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11
728x90
반응형

'Data Structure & Algorithm > Data Structure' 카테고리의 다른 글

[Data Structure] Chapter 07: 큐(Queue)  (0) 2023.08.16
[Data Structure] Chapter 06: 스택(Stack)  (0) 2023.08.15
[Data Structure] Chapter 04: 연결 리스트의 이해와 구현  (0) 2023.08.11
[Data Structure] Chapter 03: 추상 자료형과 배열 기반 리스트  (0) 2023.08.09
C언어에서의 구조체와 typedef  (0) 2023.08.08
'Data Structure & Algorithm/Data Structure' Related Articles more