[Data Structure] Chapter 04: 연결 리스트의 이해와 구현

'연결'을 기반으로 하는 리스트의 기본을 이해하고, 구현해보자.

 

 

연결 리스트의 개념적인 이해

 아래와 같이 메모리가 정적인 배열을 이용해 데이터를 저장하면, 메모리의 길이를 변경하는 것이 불가능하다는 단점이 있다.

#include <stdio.h>

int main(void)
{
    int arr[10];
    int readCount = 0;
    int readData;
    int i;

    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d", &readData);
        if(readData < 1)
            break;
        
        arr[readCount++] = readData;
    }

    for(i=0; i<readCount; i++)
        printf("%d ", arr[i]);

    return 0;
}

자연수 입력: 2
자연수 입력: 4
자연수 입력: 6
자연수 입력: 8
자연수 입력: 0
2 4 6 8

 

 

 이를 해결하고자 연결 리스트의 일부를 구현한 아래 예제를 살펴보자.

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

typedef struct _node	//데이터끼리 연결하는 역할
{
    int data;
    struct _node * next;
} Node;

int main(void)
{
    Node * head = NULL;
    Node * tail = NULL;
    Node * cur = NULL;

    Node * newNode = NULL;
    int readData;

    /***데이터를 입력 받는 과정***/
    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d", &readData);

        if(readData < 1)
            break;

        //노드의 추가 과정
        newNode = (Node*)malloc(sizeof(Node));
        newNode -> data = readData;
        newNode -> next = NULL;

        if(head == NULL)
            head = newNode;
        else
            tail -> next = newNode; //이전 노드의 next가 새 노드와 연결
        
        tail = newNode; //tail을 새 노드와 연결
    }
    printf("\n");

    /***입력 받은 데이터의 출력과정***/
    printf("입력 받은 데이터의 전체출력! \n");
    if(head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
        cur=head;
        printf("%d ", cur->data);   //첫 번째 데이터 출력

        while(cur->next != NULL)
        {
            cur = cur -> next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    /***메모리의 해제과정***/
    if(head == NULL)
    {
        return 0;   //해제할 노드가 존재하지 않는다.
    }
    else
    {
        Node * delNode = head;
        Node * delNextNode = head -> next;

        printf("%d을(를) 삭제합니다. \n", head -> data);
        free(delNode);  //첫 번째 노드 삭제

        while(delNextNode != NULL)  //두 번째 이후 노드 삭제
        {
            delNode = delNextNode;
            delNextNode = delNextNode -> next;

            printf("%d을(를) 삭제합니다.\n", delNode -> data);
            free(delNode);
        }
    }

    return 0;
}

자연수 입력: 2
자연수 입력: 4
자연수 입력: 6
자연수 입력: 8
자연수 입력: 0

입력 받은 데이터의 전체출력!
2 4 6 8

2을(를) 삭제합니다.
4을(를) 삭제합니다.
6을(를) 삭제합니다.
8을(를) 삭제합니다.

 예제 리스트의 형태는 다음과 같이 표현할 수 있다.

노드의 연결

 -> 위와 같이 동적 메모리 할당과 노드의 연결 개념을 이용해서 정적 메모리에서의 한계점을 해결할 수 있다.

 

 이를 조금 변형하여, 다음과 같이 head에서부터 데이터를 저장할 수도 있다.

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

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

int main(void)
{
    Node * head = NULL;
    Node * cur = NULL;

    Node * newNode = NULL;
    int readData;

    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d", &readData);

        if(readData < 1)
            break;

        newNode = (Node*)malloc(sizeof(Node));
        newNode -> data = readData;
        newNode -> next = NULL;

        if(head == NULL)
            head = newNode;
        else
            newNode -> next = head; 

        head = newNode;
    }
    printf("\n");

    printf("입력 받은 데이터의 전체출력! \n");
    if(head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
        cur=head;
        printf("%d ", cur->data);  

        while(cur->next != NULL)
        {
            cur = cur -> next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    if(head == NULL)
    {
        return 0;   
    }
    else
    {
        Node * delNode = head;
        Node * delNextNode = head -> next;

        printf("%d을(를) 삭제합니다. \n", head -> data);
        free(delNode);

        while(delNextNode != NULL)  
        {
            delNode = delNextNode;
            delNextNode = delNextNode -> next;

            printf("%d을(를) 삭제합니다.\n", delNode -> data);
            free(delNode);
        }
    }

    return 0;
}

자연수 입력: 3
자연수 입력: 2
자연수 입력: 7
자연수 입력: 8
자연수 입력: 5
자연수 입력: 0

입력 받은 데이터의 전체출력!
5 8 7 2 3

5을(를) 삭제합니다.
8을(를) 삭제합니다.
7을(를) 삭제합니다.
2을(를) 삭제합니다.
3을(를) 삭제합니다.

 -> 헤드에서부터 저장하는 경우에는 tail이 필요가 없어진다.

 

	head에 데이터 추가	tail에 데이터 추가
장점	포인터 변수 tail이 불필요하다.	저장된 순서가 유지된다.
단점	저장된 순서를 유지하지 않는다.	포인터 변수 tail이 필요하다.

 -> 리스트 자료구조는 저장된 순서를 유지하는 자료구조가 아니며, 포인터 변수 tail을 유지함으로써 생기는 코드는 번거로울 수 있기 때문에 head 데이터 추가 방식이 유리하다. 

 

 

단순 연결 리스트의 ADT와 구현

정렬 기능이 추가된 연결 리스트의 ADT

void ListInit(List * plist);
- 초기화할 리스트의 주소 값을 인자로 전달한다.
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List * plist, LData data);
- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

int LFirst(List * plist, LData * pdata);
- 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
- 데이터의 참조를 위한 초기화가 진행된다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

int LNext(List * plist, LData * pdata);
- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
- 순차적인 참조를 위해서 반복 호출이 가능하다.
- 참조를 새로 시작하려면, 먼저 LFirst 함수를 호출해야 한다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

LData LRemove(List * plist);
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
- 삭제된 데이터는 반환된다.
- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

int LCount(List * plist);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));
- 리스트에 정렬의 기준이 되는 함수를 등록한다.

• 마지막 줄의 정렬 함수를 제외하고는 지난 Chapter의 배열 기반 리스트 ADT와 동일하다.

 

더미 노드(Dummy Node) 기반의 단순 연결 리스트

• 앞서 정의한 단순 연결 리스트는 헤드가 첫 번째 노드를 가리키면서, 노드를 추가, 삭제 그리고 조회하는 방법에 있어서 첫 번째 노드와 두 번째 이후의 노드 사이에 차이가 생긴다.
• 더미 노드를 이용하여 이런 문제를 해결할 수 있다.

 

 다음 형태의 연결 리스트를 구현해보자.

더미 노드가 추가된 형태의 연결 리스트

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

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

int main(void)
{
    Node * head = (Node*)malloc(sizeof(Node));
    Node * tail = head;
    Node * cur = NULL;

    Node * newNode = NULL;
    int readData;

    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d", &readData);

        if(readData < 1)
            break;

        newNode = (Node*)malloc(sizeof(Node));
        newNode -> data = readData;
        newNode -> next = NULL;

        tail -> next = newNode;
        tail = newNode;
    }
    printf("\n");

    printf("입력 받은 데이터의 전체출력! \n");
    if(head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
        cur=head;

        while(cur->next != NULL)
        {
            cur = cur -> next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    if(head == NULL)
    {
        return 0;  
    }
    else
    {
        Node * delNode = head;
        Node * dummy = head;
        Node * delNextNode = head -> next;

        while(delNextNode != NULL)  //두 번째 이후 노드 삭제
        {
            delNode = delNextNode;
            delNextNode = delNextNode -> next;

            printf("%d을(를) 삭제합니다.\n", delNode -> data);
            free(delNode);
        }
        free(dummy);
    }

    return 0;
}

-> 서적에서는 dummy head를 따로 메모리 해제하지 않는데, 그럴 경우에는 메모리 누수가 발생하기 때문에 데이터를 모두 해제하고 더미도 할당된 메모리를 따로 해제해주는 것이 맞다고 판단됨.

자연수 입력: 2
자연수 입력: 4
자연수 입력: 6
자연수 입력: 8
자연수 입력: 0

입력 받은 데이터의 전체출력!
2 4 6 8

2을(를) 삭제합니다.
4을(를) 삭제합니다.
6을(를) 삭제합니다.
8을(를) 삭제합니다.

 

정렬 기능이 추가된 연결 리스트의 구현

 파일명: DLinkedList.h

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int LData;

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

typedef struct _linkedList
{
    Node * head;
    Node * cur;
    Node * before;
    int numOfData;
    int(*comp)(LData d1, LData d2);
}   LinkedList;

typedef LinkedList List;

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

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

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

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));

#endif

 

 파일명: DLinked.c

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


void ListInit(List * plist)
{
    plist -> head = (Node*)malloc(sizeof(Node));
    plist -> head -> next = NULL;
    plist -> comp = NULL;
    plist -> numOfData = 0;
}

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

    newNode -> next = plist -> head -> next;
    plist -> head -> next = newNode;

    (plist -> numOfData)++;
}

void SInsert(List * plist, LData data)
{
    //TBD
}

void LInsert(List * plist, LData data)
{
    if(plist -> comp == NULL)
        FInsert(plist, data);
    else
        SInsert(plist, data);
}

int LFirst(List * plist, LData * pdata)
{
    if(plist -> head -> next == NULL)
        return FALSE;
    
    plist -> before = plist -> head;
    plist -> cur = plist -> head -> next;

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

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

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

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

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

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

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

    return rdata;
}

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

void SetSortRule(List * plist, int(*comp)(LData d1, LData d2))
{
    //TBD
}

 연결 리스트의 함수는 다음 구조로 구현되었다.

FInsert 함수의 구조

LFirst 함수의 구조

LNext 함수의 구조

LRemove 함수의 구조

 

 파일명: DLinkedListMain.c

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

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

	// 5개의 데이터 저장 /////////////////////////////
	LInsert(&list, 11);  LInsert(&list, 11);
	LInsert(&list, 22);  LInsert(&list, 22);
	LInsert(&list, 33);

	// 저장된 데이터의 전체 출력 /////////////////////////
	printf("현재 데이터의 수: %d \n", LCount(&list));

	if(LFirst(&list, &data))    // 첫 번째 데이터 조회
	{
		printf("%d ", data);
		
		while(LNext(&list, &data))    // 두 번째 이후의 데이터 조회
			printf("%d ", data);
	}
	printf("\n\n");

	// 숫자 22을 검색하여 모두 삭제 //////////////////////////
	if(LFirst(&list, &data))
	{
		if(data == 22)
			LRemove(&list);
		
		while(LNext(&list, &data))
		{
			if(data == 22)
				LRemove(&list);
		}
	}

	// 삭제 후 남아있는 데이터 전체 출력 ////////////////////////
	printf("현재 데이터의 수: %d \n", LCount(&list));

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

현재 데이터의 수: 5 
33 22 22 11 11 

현재 데이터의 수: 3 
33 11 11

 

문제 04-3

Point.h, Point.c, PointListMain.c 파일을 디렉토리에 포함시키고, ArrayList.h 파일의 LData 선언을 Point 자료형으로 바꾸고 헤더파일 선언문만 추가해주면 된다.

 

 

연결 리스트의 정렵 삽입의 구현

연결 리스트의 정렬기준이 되는 함수를 등록하는 SetSortRule 함수

• 첫 번째로 전달받은 plist의 정렬 기준을 두 번째로 전달받은 comp가 가리키는 함수의 정렬 기준으로 맞춘다.

void SetSortRule(List * plist, int(*comp)(LData d1, LData d2))
{
    plist -> comp = comp;
}

 

comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수

• while 반복문을 이용해 새로 주어진 데이터가 정렬 기준에 맞는 위치로 이동하게 한다.

SInsert 함수의 구조

void SInsert(List * plist, LData data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    Node * pred = plist -> head;    
    newNode -> data = data;

    while(pred -> next != NULL && plist -> comp(data, pred-> next -> data) != 0)
    {
        pred = pred -> next;
    }

    newNode -> next = pred -> next;
    pred -> next = newNode;

    (plist -> numOfData)++;
}

 

정렬기준이 되는 comp가 가리키는 함수

• 두 개의 인자를 전달받도록 함수를 정의
• 첫 번째 인자의 정렬 우선순위가 높으면 0, 그렇지 않으면 1을 반환
• 상황에 따라 변경 가능
• 정렬 기준의 유연성을 부여하기 위해 main 파일에 위치해야 한다.

int WhoIsPreced(int d1, int d2)
{
	if(d1<d2)
		return FALSE;
	else
		return TRUE;
}

 

정렬 기준을 적용한 main 함수

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

int WhoIsPreced(int d1, int d2)	//정렬의 기준이 되는 함수
{
	if(d1<d2)
		return FALSE;
	else
		return TRUE;
}

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

	SetSortRule(&list, WhoIsPreced);	//정렬 기준 설정

	LInsert(&list, 11);  LInsert(&list, 11);
	LInsert(&list, 22);  LInsert(&list, 22);
	LInsert(&list, 33);

	printf("현재 데이터의 수: %d \n", LCount(&list));

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

	if(LFirst(&list, &data))
	{
		if(data == 22)
			LRemove(&list);
		
		while(LNext(&list, &data))
		{
			if(data == 22)
				LRemove(&list);
		}
	}

	printf("현재 데이터의 수: %d \n", LCount(&list));

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

현재 데이터의 수: 5 
11 11 22 22 33 

현재 데이터의 수: 3 
11 11 33

 

문제 04-4

• 다음과 같이 문제 04-3에서 정렬기준이 되는 함수 WhoIsPreced의 내용만 바꿔주면 된다.

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
#include "Point.h"

int WhoIsPreced(Point * d1, Point * d2)
{
	if(d1 -> xpos < d2 -> xpos)
		return FALSE;
	else if(d1 -> xpos == d2 -> xpos && d1 -> ypos < d2 -> ypos)
		return FALSE;
	else
		return TRUE;
}

int main(void)
{
    List list;
    Point compPos;
    Point * ppos;

    ListInit(&list);

    SetSortRule(&list, WhoIsPreced);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 2);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 2);
    LInsert(&list, ppos);

    printf("현재 데이터의 수: %d \n", LCount(&list));

    if(LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while(LNext(&list, &ppos))
            ShowPointPos(ppos);
    }

    printf("\n");

    /*** xpos가 2인 모든 데이터 삭제 ***/
    compPos.xpos = 2;
    compPos.ypos = 0;

    if(LFirst(&list, &ppos))
    {
        if(PointComp(ppos, &compPos)==1)
        {
            ppos=LRemove(&list);
            free(ppos);
        }

        while(LNext(&list, &ppos))
        {
            if(PointComp(ppos, &compPos)==1)
            {
                ppos=LRemove(&list);
                free(ppos);
            }
        }
    }

    /***삭제 후 남은 데이터 전체 출력***/
    printf("현재 데이터의 수: %d \n", LCount(&list));

    if(LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);
        
        while(LNext(&list, &ppos))
            ShowPointPos(ppos);
    }
    printf("\n");

    return 0;
}

 

 

 

 

 

---

참고자료

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