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

Notice

Recent Posts

Recent Comments

Link

« 2024/12 »
일	월	화	수	목	금	토
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	31

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

'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

SYDev

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

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

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

문제 05-1

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

문제 05-2

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

티스토리툴바