Chapter 04. 연결 리스트(Linked List) 2

김민정·2024년 10월 17일

c언어 개발 기술블로그 연결 리스트 코딩

윤성우 열혈 자료구조

목록 보기

4/14

Chapter 03에서 배운 것을 다음과 같이 세 가지로 정리할 수 있다.

추상 자료형에 대한 이해
리스트 자료구조의 특성과 활용
리스트 자료구조의 배열 기반 구현

Chapter 04에서는 '연결'을 기반으로 하는 다른 르시트의 구현방법에 대해 배울 것이다.

04-1. 연결 리스트의 개념적인 이해

Linked List

연결 기반의 리스트를 간단하게 연결 리스트라 한다.
연결 리스트의 구현을 이해하기 위해서는 malloc 함수와 free 함수를 기반으로 하는 메모리의 동적 할당에 대해 이해를 하고 있어야한다.
다음 예제를 통해 연결 리스트에서의 연결이 의미하는 것을 알아보자.

// ArrayRead.c
#include <stdio.h>

int main()
{
    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;
}

> 출력
자연수 입력: 1
자연수 입력: 2
자연수 입력: 3
자연수 입력: 4
자연수 입력: 5
자연수 입력: 0
1 2 3 4 5

위 예제는 0 이하의 값을 입력하기 전까지 입력이 계속되는 간단한 예제이다.
여기서 우린 배열의 단점을 볼 수 있다.
배열은 메모리의 특성이 정적이어서 메모리의 길이를 변경하는 것이 불가능하다.
따라서 배열 길이 10을 넘어서도 0보다 큰 자연수 값을 입력하게 되면 문제가 발생하게 된다.
이렇든 특성이 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다.
그래서 등장한 것이 '동적인 메모리의 구성`이다.
동적인 메모리의 구성에 대해서 다음 예제를 통해 이해해보자.
(분석이 쉽지는 않을 것이다...!)

// LinkedRead.c
#include <stdio.h>
#include <stdlib.h>

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

int main()
{
    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;
        
        tail = newNode;
    }
    printf("\n");

    // 입력 받은 데이터의 출력 과정
    printf("입력 받은 데이터의 전체 출력! \n");
    if(head == NULL)
        printf("저장된 자연수가 없습니다.");
    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
자연수 입력: 1
자연수 입력: 3
자연수 입력: 7
자연수 입력: 0

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

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

위 예제를 이해하기 위해 먼저 정의된 구조체를 살펴보자.

typedef struct _node
{
    int data;				// 데이터를 담을 공간
    struct _node* next;		// 연결 도구
} Node;

위 구조체의 멤버 next는 Node형 구조체 변수의 주소 값을 저장할 수 있는 포인터 변수이다.
위 구조체 변수를 바구니에 비교하자면 구조체의 첫 번째 멤버 data에 값을 저장할 수 있는 것이고 바구니와 바구니를 연결하는 것은 next인 것이다.
이 next 멤버 덕분에 모든 Node형 구조체 변수는 다른 Node형 구조체 변수를 가리킬 수 있게 된다.

따라서 Node형 구조체를 대상으로 필요할 때마다 구조체 변수를 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다는 것이다!
즉, 필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당(malloc함수)해서 이들을 연결한다는 것이다.
이것이 연결 리스트의 기본 원리다.
데이터를 저장하는 곳과 다른 변수를 가리키기 위한 곳을 구분한 것을 아래 그림과 같이 나타낼 수 있따.

연결 리스트에서의 데이터 삽입

위 예제 LinkedRead.c는 연결 리스트의 구현 결과를 나타낸 것이고 이것에 대해 더 자세히 알아보자.

main함수에서 등장하는 포인터 변수의 선언에 대해 알아보자.

Node * head = NULL;		// 리스트의 머리를 가리키는 포인터 변수
Node * tail = NULL;		// 리스트의 꼬리를 가리키는 포인터 변수
Node * cur = NULL;		// 저장된 데이터의 조회에 사용되는 포인터 변수

이 변수 세개는 연결 리스트에서 주요한 역할을 하는 포인터 변수들이다.
head와 tail은 연결을 추가 및 유지하기 위한 것이고, cur은 참조 및 조회를 위한 것이다.
다음 그림들을 통해 이 변수들이 어떻게 작동되는지 자세히 알아보자.

NO.	Status	Content
0		연결 리스트의 초기상태. 구조체 Node의 포인터 변수 head와 tail이 NULL 가리키고 있는 상황. [코드] `Node * head = NULL;` `Node * tail = NULL;`
1	-	<첫 번째 노드 추가하는 과정.>
1-1		while 반복문이 처음 실행된 상황이며 newNode(새 노드, 바구니 생성)에 입력값 2가 저장되고 newNode의 data부분에 2가 저장. newNode의 next부분은 Null로 저장. [코드] `newNode = (Node *)malloc(sizeof(Node));` `newNode->data = readData;` `newNode->next = NULL;`
1-2		첫 번째 노드이기 때문에 head가 newNode를 가리키게 함. [코드] `if(head == NULL){head = newNode;}`
1-3		첫 번째 노드이기 때문에 tail도 newNode를 가리키게 됨. [코드] `tail = newNode;` +) NULL을 사선으로 표현
2	-	<두 번째 이후의 노드를 추가하는 과정.>
2-1		tail이 가리키는 노드의 뒤에 연결해야 함. 새 노드의 생성 및 초기화 이후 else 구문에 담긴 문장 실행. tail의 next에 새로운 Node인 newNode 연결. [코드] `tail->next = newNode;`
2-2		이 후에도 동일한 방법으로 newNode를 새롭게 할당하고 tail의 next 부분을 새 노드인 newNode에 연결.

연결 리스트에서의 데이터 조회

삽입만큼이나 이해하기 쉬운 것이 조회다.
조회는 cur라는 포인터 변수를 사용할 것이다.

No.	Status	Content
1		조회부분 코드에서 else 부분 중 `cur = head;` 코드 실행되면 연결 리스트 중 첫 번째 노드 가리킴. 따라서, cur를 이용한 첫 번째 데이터 출력 가능.
2		else 구문 안에 있는 while문 작동하면서 `cur = cur->next;` 코드를 통해 그림과 같이 모든 노드를 가리키며 이동 가능.

연결 리스트에서의 데이터 삭제

삭제 코드는 삽입이나 조회보다는 살짝 어려울 순 있다. 하지만 찬찬히 살펴보도록 하자.

No.	Status	Content
1		head가 가리키는 노드의 삭제를 위해 `Node * delNode = head;` `Node * delNextNode = head->next;` 위와 같이 포인터 변수 두 개를 추가로 선언했다. delNode(dN)는 삭제할 노드를 가리키고, delNextNode(dNN)은 삭제될 노드가 가리키는 다음 노드의 주소값을 저장. 둘을 구분지어 놓는 이유는 삭제될 노드가 가리키는 다음 노드의 주소 값을 별도로 저장되지 않을 경우 다음 노드와 삭제된 노드 앞 노드와의 연결이 끊어지기 때문.
2		`free(delNode);` 코드를 통해 첫 번째 노드를 삭제. (head가 다음 노드를 가리키는 것이 원칙이나 삭제 과정만을 보여주기 위해 생략됨.) `delNode = delNextNode;` `delNextNode = delNextNode->next;` 위 코드를 통해 오른쪽으로 노드 가리킴 이동.
3		이동한 delNode과 free 함수의 호출을 통해 마지막 노드를 소멸할 때까지 계속 진행.

정리하기

LinkedRead.c를 통해 연결리스트를 100% 구현하고 이해했다고 말할 수는 없다.
그 이유는 대표적으로 두 가지가 있다.

연결 리스트의 ADT를 정의하지 않았다.
삽입, 삭제, 조회의 기능이 별도의 함수로 구분되어 있지 않았다.

연결리스트와 관련된 코드를 모조리 main 함수에 넣은거기 때문에 필요할 때마다 가져다 쓸 수 없는 것이다.
자료구조는 다음 세 가지 순서를 지키는 것이 자료구조를 이해하고 구현하는데 있어 중요하다.

자료구조의 ADT 정의
정의한 ADT 구현
구현이 완료된 자료구조의 활용

04-2. 단순 연결 리스트의 ADT와 구현

처음으로 배울 연결 리스트는 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 단순 연결 리스트다.

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

기능적으로 무엇인가를 변경하거나 추가하지 않는다면 ADT를 변경할 이유는 없다.
그래서 Chapter 03에서 정의한 리스트 ADT를 그대로 적용해도 되지만 연결 리스트 정렬 관련 기능을 추가하기 위해서 해당 부분 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)); [신규 ✨]
- 리스트에 정렬의 기준이 되는 함수를 등록.

여기서 우리는 새 노드를 추가할 때 리스트의 머리와 꼬리 중 어디에 저장할 것인지 정해야한다.
두 가지 방법 모두 장단점이 있다.
머리에 추가할 경우의 장단점은 다음과 같다.

장점 : 포인터 변수 tail이 불필요.
단점 : 저장된 순서를 유지하지 않음.

꼬리에 추가할 경우의 장단점은 다음과 같다.

장점 : 저장된 순서가 유지.
단점 : 포인터 변수 tail이 필요.

단순 연결 리스트의 구현을 배울 땐 머리에 추가하는 경우가 선호된다.
그 이유는 포인터 변수 tail을 유지하기 위해서 넣어야할 부가적인 코드가 번거롭게 느껴질 수 있고, 리스트 자료구조는 저장된 순서를 유지해야하는 자료구조가 아니기 때문이다.

다시 돌아와서 연결 리스트이 정렬기준을 지정하기 위해 추가된 ADT는 SetSortRule함수이다.
SetSortRule 함수의 선언 및 정의를 이해하기 위해서는 '함수 포인터'에 대한 이해가 필요하다.
정렬의 기준이란 것이 정수를 대상으로 보면 수의 크기가 전부이지만, 경우에 따라서는 알파벳의 순서나 이름과 같은 문자열 길이의 길고 짧음이 대상이 될 수도 있다.
함수의 두 번째 매개변수 선언을 보면 반환형이 int고 LData형 인자 두 개 전달받는 함수의 주소 값을 두 번째 인자로 전달받는다.
따라서 다음과 같이 정의된 함수의 주소 값이 SetSortRule 함수의 두 번째 인자로 전달 가능한 경우이다.

int WhoIsPrecede(LData d1, LData d2)	// typedef int LData;
{
	if(d1 < d2)
    	return 0;	// d1이 정렬 순서상 앞선다.
    else
    	return 1;	// d2가 정렬 순서상 앞서거나 같다.
}

그리고 SetSortRule의 두 번째 인자로 전달되는 함수는 위 함수의 정의에서 보이듯이
매개변수 d1에 전달되는 인자가 정렬 순서상 앞서서 head에 더 가까워야하는 경우 0을 반환하고,
매개변수 d2에 전달되는 인자가 정렬 순서상 앞서거나 같은 경우에는 1을 반환한다.
이렇든 반환 값이 어떻게 되고 그것이 어떤 의미를 갖는지는 연결 리스트를 구현하는 사람이 결정하는 부분이다.
이렇게 반환되는 값을 가지고 SetSortRule함수가 어떻게 활용되고 연결 리스트 내부적으로 어떤 의미를 지니는지 천천히 알아가보자.

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

LinkedRead.c 예제에서는 첫 노드의 추가, 삭제 및 조회하는 방법이 두 번째 노드 이후의 추가, 삭제 및 조회하는 방법에 차이가 있다.
이러한 차이없이 일관된 형태로 구성하기 위해 더미 노드(Dummy Node)를 사용하게 된다.
우선 포인터 변수 tail이 사라지고 더미 노드가 추가되어 왼쪽 그림에서 오른쪽 그림과 같이 연결 리스트 형태를 생각해 볼 수 있다.

노드를 머리에서부터 채우기로 했기 때문에 tail 포인터 변수가 필요 없는 것이고, 더미 노드라는 빈 노드를 미리 넣어두어 처음 추가되는 노드가 구조상 두 번째 노드가 되어 노드 추가, 삭제 및 조회의 과정을 일관된 형태로 만들어 준다.

정렬 기능이 추가된 연결 리스트 2: 구조체와 헤더파일의 정의

정렬 기능이 추가된 연결 리스트의 ADT를 정의했다면 연결 리스트의 구조체와 헤더파일을 정의해보자.
노드는 초반에 설정했던 Node 구조체와 동일하다.

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

그 다음 연결 리스트의 구현에 필요한 다음 두 포인터 변수들을 별도의 구조체로 묶지 않고 그냥 main 함수의 지역변수로 선언하거나 나쁜 방법으로는 전역변수로 선언하기도 한다.
전역변수로 선언하는 것은 나쁜 습관이다.
프로그램을 구현하는데 있어서 리스트 자료구조가 하나만 사용되지 않고 배열도 하나가 아닌 다수의 배열이 필요하다.
따라서 다수의 리스트가 필요한 상황에서 head와 cur과 같은 포인터 변수를 전역 변수로 선언하게 된다면 아래와 같이 리스트의 세트를 필요할 때마다 만들어서 사용해야하기 때문에 불편하다.

#include <stdio.h>
Node * headOne, * curOne;		// 리스트 한 세트
....
Node * headTwo, * curTwo;		// 리스트 두 세트
....
Node * headThree, * curThree;	// 리스트 세 세트
....

int main()
{
	....
    return 0;
}

따라서 head와 cur과 같은 포인터 변수를 묶어서 다음과 같이 연결 리스트를 의미하는 구조체를 별도로 정의해야 한다.

typedef struct _linkedList
{
	Node * head;						// 더미 노드를 가리키는 멤버
    Node * cur;							// 참조 및 삭제를 돕는 멤버
    Node * before;						// 삭제를 돕는 멤버
    int numOfData;						// 저장된 데이터의 수를 기록하기 위한 멤버
    int (*comp)(LData d1, LData d2);	// 정렬의 기준을 등록하기 위한 멤버
} LinkedList;

위 구조체는 Chapter 03에서 정의한 ArrayList와 그 성격이 동일하다.
ArrayList는 배열 기반 리스트라면, LinkedList는 연결 기반 리스트다.
준비는 다 끝났다!
이제 더미 노드 기반의 정렬 삽입도 되고, 정렬 삽입의 기준도 바꿀 수 있는 연결 리스트를 위한 헤더파일을 구현해보자.

// 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

위 헤더파일에 선언된 함수는 Chapter 03의 배열 기반 리스트의 헤더파일과 LinkedList 구조체 정의, SetSortRule 함수의 선언이 추가되었다는 것 말고는 거의 비슷하다.

정렬 기능이 추가된 연결 리스트 3: 더미 노드(Dummy Node) 기반의 단순 연결 리스트 구현

다음은 구현한 헤더파일을 바탕으로 더미 노드 기반의 단순 연결 리스트 함수들을 구현할 것이다.

1) 리스트 초기화

우리는 위에서 LinkedList라는 구조체를 선언했다.

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

위 구조체의 변수가 선언되면 이를 대상으로 초기화를 진행해야 하는데, 이때 호출되는 함수는 다음과 같다.

void ListInit(List * plist)
{
	plist->head = (Node *)malloc(sizeof(Node));		// 더미 노드 생성
    plist->head->next = NULL;
    plist->comp = NULL;
    plist->numOfData = 0;
}

이 코드를 그림으로 나타내면 다음과 같다.

여기서 중요한 점은 더미 노드가 존재한다는 것이다.
그리고 그림에는 표현되지 않았지만 리스트의 멤버 comp이 NULL로, 멤버 numOfData가 0으로 초기화된 점도 기억하자.

2) 노드 삽입

리스트 초기화 이후 노드를 추가하기 위해 호출되는 함수는 다음과 같다.

void LInsert(List * plist, LData data)
{
	if(plist->comp == NULL)		// 정렬 기준이 마련되지 않았다면
    	FInsert(plist, data);	// 머리에 노드 추가
    else						// 정렬 기준이 마련됐다면
    	SInsert(plist, data);	// 정렬기준에 근거하여 노드 추가
}

위 함수에서 볼 수 있듯 노드의 추가는 리스트의 멤버 comp에 어떤 것이 저장되어 있느냐에 따라 FInsert 또는 SInsert 함수를 통해 진행된다.
이 두 함수들도 마저 정의해보자.

우선, comp가 NULL일 때 호출되는 FInsert 함수이다.

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)++;							// 저장된 노드의 수 +1
}

위 함수는 포인터 변수 head가 가리키고 있는 더미 노드에서 새 노드로 재지정하는 과정을 담고 있다.
if...else 구문이 없어 모든 노드의 추가과정이 일관된다는 것을 보여주고 이것이 바로 더미 노드가 주는 이점이다.
이해를 돕기 위한 예시로 리스트에 이미 4와 6이 들어있다.
그리고 새 노드의 값으로 2를 삽입하려고 한다.
첫 두줄의 코드가 실행되며 새 노드가 추가되어 아래 그림과 같은 형태가 된다.

그 다음 두줄의 코드가 실행되어 아래 그림과 같이 기존 리스트에 새 노드를 넣게 된다.

그 다음으로 comp가 NULL이 아닐 때 호출되는 SInsert 함수에 대해 알아볼 차례다.
이 함수는 SetSortRule 함수까지 학습하고 난 다음 설명을 이해가겠다.
(그래도 궁금한 사람은 여기로 👉)

3) 데이터 조회

조회 관련한 함수는 LFirst 함수와 LNext 함수이다.
이 두 함수의 구조는 ArrayList의 LFisrt 함수와 LNext 함수와 거의 동일하다.

int LFirst(List * plist, LData * pdata)
{
	if(plist->head->next == NULL)	// 더미 노드가 NULL을 가리킨다면
    	return FALSE;				// 반환할 데이터가 없음
    
    plist->before = plist->head;	// before은 더미 노드를 가리키게 함
    plist->cur = plist->head->next;	// cur은 첫 번째 노드를 가리키게 함
    
    *pdata = plist->cur->data;		// 첫 번째 노드의 데이터 전달
    return TRUE;
}

위 함수의 핵심이 되는 문장은 plist->before = plist->head;와 plist->cur = plist->head->next;이다.
2, 4, 6, 8이 저장된 리스트에서 LFirst 함수가 호출되고, 이 두 문장이 실행되면 아래 그림과 같이 된다.

그리고 그 다음 문장을 통해서 첫 번째 데이터가 전달(반환)된다.
왜 before이란 구조체 멤버를 둬서 cur보다 하나 앞선 노드를 가리키게 할까?
이는 뒤에서 배울 '노드의 삭제'와 관련이 있다.

그 다음은 LNext 함수이다.

int LNext(List * plist, LData * pdata)
{
	if(plist->cur->next == NULL)	// cur이 NULL을 가리킨다면,
    	return FALSE;				// 반환할 데이터 없음
    
    plist->before = plist->cur;		// cur이 가리키던 것을 before가 가리킴
    plist->cur = plist->cur->next;	// cur은 그 다음 노드 가리킴
    
    *pdata = plist->cur->data;		// cur이 가리키는 노드의 데이터 전달
    return TRUE;
}

위 함수의 핵심이 되는 문장은 LFirst 함수와 비슷하게 plist->before = plist->cur;과 plist->cur = plist->cur->next;이다.
아래 그림에서 보듯 cur과 before가 가리키는 대상이 하나씩 오른쪽으로 이동하게 된다.

그리고 그 다음 문장을 통해 다음 노드의 데이터가 전달(반환)된다.

4) 노드의 삭제

연결 리스트에서 데이터의 추가만큼이나 주의해야하는 것이 삭제다.
LRemove함수의 기능은 바로 이전에 호출된 LFirst 혹은 LNext 함수가 반환한 데이터를 삭제하는 점에 집중해야한다.
만약 아래 그림과 같은 상황에서 LRemove 함수가 호출되었다고 생각해보자.

위와 같은 상황은 LNext 함수의 호출을 통해 4가 반환된 이후다. 따라서 LRemove 함수의 호출시 소멸시켜야 하는 노드는 현재 cur이 가리키는 4가 저장된 노드다.
따라서 삭제의 결과는 다음과 같아야한다.

위 그림에서 주목할 점은 cur의 위치가 재조정되었다는 것이다.
4가 지워지면서 이전 노드인 2를 가리켜야한다(왼쪽으로 한칸 이동해야한다). 그리고 동시에 before 노드도 왼쪽으로 한칸 이동해야하는데 LFirst 또는 LNext 함수가 호출되면 before는 cur보다 하나 왼쪽의 노드를 가리키게 되므로 굳이 before 위치까지 재조정할 필요는 없다.

설명으로 토대로 LRemove 함수를 구현하면 다음과 같다.

LData LRemove(List * plist)
{
	Node * rpos = plist->cur;	// 소멸 대상의 주소 값을 rpos에 저장
    LData rdata = rpos->data;	// 소멸 대상의 데이터를 rdata에 저장
    
    plist->before->next = plist->cur->next;		// 소멸 대상을 리스트에서 제거. (before의 다음을 cur의 다음으로 가리키도록)
    plist->cur = plist->before;					// cur이 가리키는 위치 앞으로 한칸 이동하기
    
    free(rpos);				// 리스트에 제거된 노드 소멸
    (plist->numOfData)--;	// 저장된 데이터의 수 하나 감소
    return rdata;			// 제거된 노드의 데이터 반환
}

위 코드의 과정들을 그림으로 정리하면 아래와 같다.

이렇게 되면 리스트에서 노드 하나가 삭제된 것이다.
나머지 세 문장에 의해서 삭제된 노드를 반영하기 위한 데이터의 수 하나 감소, 제거된 노드에 저장된 값을 반환 작업이 이뤄진다.

5) 데이터 전체 수 조회

데이터 전체 수 조회는 Chapter 03 ArrayList에서 한 것과 동일하다.

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

6) 정렬 기준 등록

이 부분을 노드의 삽입 함수 중 SInsert 함수와 함께 이따가 배워볼 예정이다.
(그래도 궁금한 사람은 여기로 👉)

7) 정리하기

위에서 구현한 함수들을 하나로 정리해보자.

#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)
{
    // 뒤에 설명 예정
}

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))
{
	// 뒤에 설명 예정
}

위에서 구현한 연결 리스트를 기반으로 작성된 main 함수 및 실행 결과는 아래와 같다.

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

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

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

    // 저장된 데이터의 전체 출력
    printf("Current Number of data: %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("Now Number of data: %d\n", LCount(&list));

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

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

> gcc .\DLinkedList.c .\DLinkedListMain.c
> .\a.exe
> 출력
Current Number of data: 5
33 22 22 11 11 

Now Number of data: 3
33 11 11

04-3. 연결 리스트의 정렬 삽입의 구현

정렬에 관한 부분을 마저 구현해보자!

연결 리스트에서의 정렬기준 설정과 관련된 부분

연결 리스트에서 정렬기준의 설정과 관련 있는 부분으 다음 세 가지와 같다.

연결 리스트의 정렬기준이 되는 함수를 등록하는 SetSortRule 함수
SetSortRule 함수를 통해서 전달된 함수정보를 저장하기 위한 LinkedList의 멤버 comp
comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수

위에서 언급한 세 가지를 하나의 문장으로 정리하면 다음과 같다.
"SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다."

따라서 SetSortRule 함수는 리스트의 멤버 comp를 초기화 하는 함수이므로 다음과 같이 간단하게 정의된다.

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

이어서 SInsert 함수를 구현해보자.

void SInsert(List *plist, LData data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));	// 새 노드 생성
    Node * pred = plist->head;						// pred = 더미 노드
    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)++;			// 저장된 데이터의 수 +1
}

위 함수의 반복문에서 보듯 comp에 등록된 함수의 호출결과를 기반으로 새 노드가 추가될 위치를 찾는다.
이해를 돕기 위해 그림과 같이 살펴보자.
다음과 같이 2, 4, 6이 저장된 리스트가 있다.

오름차순으로 데이터가 저장된 것을 확인할 수 있는데 숫자 5를 삽입하려고 한다.
SInsert(&slist, 5);문장이 실행되면서 SInsert 함수가 실행된다.
함수의 첫 세문장이 실행되고 새 노드에 5가 저장된다.
그리고 모든 노드를 차례대로 가리키기 위해 선언된 포인터 변수 pred는 더미 노드를 가리키게 된다.

포인터 변수 pred가 더미 노드를 가리키는 이유는 지금 우리가 배우고 있는 연결 리스트가 단순(한방향) 연결 리스트이기 때문에 더미 노드부터 차례대로 오른쪽으로 가야하기 때문이다.

다음 이번 정렬의 핵심인 while문이다.
SInsert 함수의 while문은 두 가지 반복 조건을 가지고 있다.

반복 조건 1: pred->next != NULL
: pred가 리스트의 마지막 노드를 가리키는지 묻기 위함
반복 조건 2: plist->comp(data, pred->next->data) != 0
: 새 데이터와 pred의 다음 노드에 저장된 데이터이 우선순위 비교를 위한 함수 호출

따라서 위 조건들을 한 문장으로 정리하자면 다음과 같다.
"pred가 마지막 노드를 가리키는 것도 아니고, 새 데이터가 들어갈 자리도 아직 찾지 못했다면 pred를 다음 노드로 이동시킨다."

반복 조건2를 더 자세히 살펴보자면 comp에 등록된 함수가 반환하는 값의 종류에 따라 정렬이 달라진다.

comp가 0을 반환
: 첫 번째 인자인 data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우
comp가 1을 반환
: 두 번째 인자인 pred->next->data가 정렬 순서상 앞서서 head에 더 가가워야 하는 경우

따라서 우리는 5를 넣어야하기 때문에 4가 5보다 앞서야하므로 0이 반환되면서 그 위치가 정해진다.
아래 그림과 같이 pred가 4에서 멈추게 된다.

반복문을 지나서 다음 세 문장을 통해 4와 6사이에 새 노드가 삽입되고 그 값을 반환한다.

정렬의 기준을 설정하기 위한 함수의 정의

마지막으로 SetSortRule 함수의 인자가 될 수 있는 함수를 정의하는 일만 남았다.
이 함수를 정의하는데 있어 필요한 정보 두 가지는 다음과 같다.

두 개의 인자를 전달받도록 함수를 정의한다.
첫 번째 인자의 정렬 우선순위가 높으면 0을, 그렇지 않으면 1을 반환한다.

이 두 가지만 만족한다면 어떤 함수건 SetSortRule 함수의 인자가 될 수 있다.
위 두 조건을 만족하는 함수는 다음과 같다.

int WhoIsPrecede(int d1, int d2)	// typedef int LData;
{
	if(d1 < d2)
    	return 0;	// d1이 정렬 순서상 앞선다.
    else
    	return 1;	// d2가 정렬 순서상 앞서거나 같다.
}

이 함수는 오름차순을 위한 함수로 d1과 d2의 대소관계를 바꾸면 내림차순을 위한 함수로 바꿀 수 있다.
그렇다면 정렬의 기준인 WhoISPrecede 함수는 어디에 위치해야 할까?
이 함수는 main함수가 있는 파일에 지정해야 한다.
프로그래머가 연결 리스트의 정렬 기준을 결정할수 있도록 유연성을 부여하기 위함이다!

따라서 총 정리된 단순 연결 리스트의 함수 구현 코드와 main 함수 코드는 다음과 같다.

DLinkedList.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)
{
	Node * newNode = (Node *)malloc(sizeof(Node));	// 새 노드 생성
    Node * pred = plist->head;						// pred = 더미 노드
    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)++;			// 저장된 데이터의 수 +1
}

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))
{
	plist->comp = comp;
}

DLinkedListSortMain.c

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

int WhoIsPrecede(int d1, int d2)
{
	if(d1 < d2)
    	return 0;	// d1이 정렬 순서상 앞선다.
    else
    	return 1;	// d2가 정렬 순서상 앞서거나 같다.
}

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

    // 정렬 기준 등록
    SetSortRule(&list, WhoIsPrecede);

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

    // 저장된 데이터의 전체 출력
    printf("Current Number of data: %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("Now Number of data: %d\n", LCount(&list));

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

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

> gcc .\DLinkedList.c .\DLinkedListSortMain.c
> .\a.exe
> 출력
Current Number of data: 5
11 11 22 22 33 

Now Number of data: 3
11 11 33

`<Review>`

와... Chapter 04-2에서 LFirst 함수 구현할 때 if(plist->head->next == NULL)에서 ==이 아니라 =으로 오타내서 오류 잡느라 30분은 날린거 같다 후^^

생각보다 파이썬으로 연결리스트를 구현했을 때에 비해 디테일하지만서도 심플하게 하지만 코드는 엄청 길게 구현이 된다는 것을 알게 되었다.

이렇게 정리하는게 단순히 책 내용 배껴서 정리하는 걸로 볼 수 있겠지만
나중에 기억이 안나거나 헷갈렸던 부분을 내가 언제든 편하게 볼 수 있도록 정리하는 것이라고 생각한다.

앞으로도 화이티잉~!
내년안에 취업 가보자구우~!

김민정

백엔드 코린이😁

이전 포스트

Chapter 03. 연결 리스트(Linked List) 1

다음 포스트