Chapter 05. 연결 리스트(Linked List) 3

05-1. 원형 연결 리스트(Circular Linked List)

이번에 배울 '원형 연결 리스트'는 Chapter 04에서 배운 단순 연결 리스트에서 약간의 변경만 하면 쉽게 만들 수 있다.

원형 연결 리스트의 이해

단순 연결 리스트에서 마지막 노드는 NULL을 가리켰다.
이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다.

이 원형 리스트에서 머리 부분에 데이터 1이 저장된 노드를 추가하면 다음과 같다.

꼬리 부분에 데이터 1이 저장된 노드를 추가하면 어떻게 될까?

두 연결 리스트 모두 8이 저장된 노드는 1이 저장된 새 노드를 가리키고, 1이 저장된 새 노드는 2가 저장된 노드를 가리킨다.
이러한 특성 때문에 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고도 얘기한다.
두 연결 리스트의 유일한 차이점은 포인터 변수 head가 무엇을 가리키고 있는지 뿐이다.

그렇다면 포인터 변수 tail은 없어도 되는 걸까?
단순 연결 리스트에서는 tail이 없다면 매우 비효율적이기 때문에 tail이 있어야 했다.
하지만, 원형 연결 리스트에서는 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 추가할 수 있다는 점이 장점이다.

변형된 원형 연결 리스트

우리는 이제 포인터 변수 head만 있는 원형 연결 리스트를 생각하는 것이 아닌,
포인터 변수 tail만 있는 변형된 원형 연결 리스트를 주로 다룰 것이다.

한 방향으로 연결되어 있는 리스트기 때문에 머리와 꼬리를 가리키는 포인터 변수를 두지 않고 하나의 포인터 변수를 둔다면 tail 포인터 변수를 사용하는 것이 보다 일반적이라고 인식되고 있다.
새로운 노드를 리스트의 끝에 추가할 때는 tail이 가리키는 곳 뒤에 넣으면 되고 tail->next가 가리키는 것이 첫 번째 노드니 이를 이용하면 리스트의 처음에도 노드를 추가하기 쉽다.
즉, 하나의 포인터 변수로 첫 번째 노드와 마지막 노드를 가리키는 포인터 변수가 각각 존재하게 되는 상황이니 어렵지 않게 머리와 꼬리에 노드를 추가할 수 있는 것이다.

변형된 원형 연결 리스트 구현 1: 헤더파일

이번 원형 연결 리스트를 구현하는데 있어서 LFirst, LNext, LRemove 함수의 역할이 중요하다.
단, 주의할 점은 원형 연결 리스트에서 LNext함수는 무한 반복 호출이 가능해 리스트의 끝에 도달할 경우 첫 번째 노드부터 다시 조회가 시작된다는 점이다.
정렬과 관련이 있는 기능은 제외시키고 데이터를 저장하는 함수는 두 개를 정의할 것이다.
(리스트 머리에 노드 추가, 꼬리에 노드 추가)
원래는 ADT를 먼저 정의하고 헤더파일을 정의해야하지만 이전에 배운 단순 연결 리스트와 큰 차이가 없기 때문에 바로 헤더파일을 정의할 것이다.

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

아까도 설명했듯 변경된 원형 연결 리스트에서는 노드 추가 부분에서 LInsert 함수와 LInsertFront 함수 두 가지로 나누어 정의할 것이다.

변형된 원형 연결 리스트 구현 1: 함수 정의

1) 리스트의 초기화

원형 연결 리스트의 초기화는 단순 연결 리스트의 초기화만큼 간단하다.
아래 코드와 같이 리스트의 멤버를 NULL또는 0으로 초기화하는 것이 전부다.

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

이 함수의 호출을 통해 초기화가 완료된 이후 첫 번째 노드가 추가되는 상황을 그림으로 나타내면 다음과 같다.

새 노드가 추가되었지만 아직 리스트에 추가되지 않았다.
tail이 NULL을 가리킨다는 것은 노드가 하나도 추가되지 않았다는 것을 의미한다.

2) 노드의 삽입

초기화 이후 첫 번째 노드를 추가한 뒤 리스트에 노드를 추가하기 위해서는 tail이 새 노드를 가리켜야 하고, 새 노드도 자기 자신을 가리켜야 한다.
왜냐하면 처음 추가된 노드는 그 자체로 머리이자 꼬리이기 때문이다.
아래는 첫 번째 노드가 리스트에 추가가 완료 되었을 때 그림이다.

첫 번째 노드 추가 부분은 LInsert 함수와 LInsertFront 함수 모두 동일한 기본 구성을 갖게 된다.

void LInsert~(List * plist, Data data)	// LInsert & LInsertFront 공통 부분
{
	Node * newNode = (Node *)malloc(sizeof(Node));	// 새 노드 생성
    newNode->data = data;							// 새 노드에 데이터 저장
    
    if(plist->tail == NULL)			// 첫 번째 노드
    {
    	plist->tail = newNode;		// tail이 새 노드를 가리키게 함
        newNode->next = newNode;	// 새 노드 자신도 가리키게 함
    }
   	else	// 두 번째 이후 노드
    {
    	....
    }
    
    (plist->numOfData)++;
}

두 번째 이후 노드 추가되는 것에 대해 생각해보자.
아래 그림은 2와 4가 저장된 연결 리스트에 7이 저장된 노드를 리스트의 머리와 꼬리에 각각 추가했을 때 상황이다.

Case	Image
두 번째 이후의 노드 추가
머리에 노드 추가
꼬리에 노드 추가

위 그림의 결과를 얻기 위한 코드를 else문에 작성하면 다음과 같다.

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    
    if(plist->tail == NULL)
    {
    	plist->tail = newNode;
        newNode->next = newNode;
    }
   	else	// 두 번째 이후 노드
    {
    	newNode->next = plist->tail->next;	// 새 노드와 4가 저장된 노드 연결
        plist->tail->next = newNode;		// 2가 저장된 노드와 새 노드 연결
    }
    
    (plist->numOfData)++;
}

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    
    if(plist->tail == NULL)
    {
    	plist->tail = newNode;
        newNode->next = newNode;
    }
   	else	// 두 번째 이후 노드
    {
    	newNode->next = plist->tail->next;
        plist->tail->next = newNode;
        plist->tail = newNode;	// LInsertFront 함수와 유일한 차이점
    }
    
    (plist-<numOfData)++;
}

LInsert 함수를 보면 LInsertFront 함수와 달리 코드 한 줄이 더 추가되어있따.
이는 노드를 꼬리에 추가했을 때와 머리에 추가했을 때 tail이 가리키는 노드가 다르다는 점이다.
아래 그림에서 볼 수 있듯 새 노드를 머리에 추가한 상태에서 연결 방향에 따라 tail만 한 번 이동시키면, 그 결과가 새 노드를 꼬리에 추가한 결과가 된다.

이를 통해 원형 연결 리스트는 머리와 꼬리의 구분이 의미가 없다는 것을 알 수 있다.

3) 데이터 조회

데이터의 조회를 담당하는 LFirst 함수와 LNext 함수를 구현해보자.
이를 위해 구조체 정의한 것을 다시 한번 살펴보자.

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

위 구조체의 멤버 cur과 before의 역할은 단순 연결 리스트의 경우와 동일하다.
즉 before는 cur보다 하나 앞선 노드를 가리켜야 하기 때문에 LFirst 함수가 호출되면 다음 그림과 같이 초기화 되어야 한다.

cur이 가리키는 노드가 곧 머리가 되기 때문에
cur과 before를 초기화하고 LFirst 함수는 cur이 가리키는 노드의 데이터를 반환하면 된다.

int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL)			// 저장된 노드가 없다면
    	return FALSE;
    
    plist->before = plist->tail;	// before가 꼬리를 가리키게
    plist->cur = plist->tail->next;	// cur이 머리를 가리키게
    
    *pdata = plist->cur->data;		// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

LFirst 함수가 호출되면서 cur과 before의 초기화가 이뤄졌기 때문에 LNext 함수가 호출되면 cur과 before가 가리키는 노드를 한 칸씩 다음 노드로 이동시키면 된다.

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)			// 저장된 노드가 없다면
    	return FALSE;
    
    plist->before = plist->cur;		// before가 다음 노드 가리키게
    plist->cur = plist->cur->next;	// cur가 다음 노드 가리키게
    
    *pdata = plist->cur->data;		// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

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

참고로 LNext 함수에는 리스트의 끝을 검사하는 코드가 없다.
무한으로 반복해서 호출이 가능하며 대상이 되는 원형 연결 리스트는 머리와 꼬리가 연결된 관계로 리스트의 마지막까지 조회가 이뤄졌다면 다시 첫 번째 노드에서부터 조회가 시작된다.

4) 노드의 삭제

머리와 꼬리가 연결되어 있다는 점을 제외하고는 원형 연결 리스트와 단순 연결 리스트는 그 구조가 동일하기 때문에 삭제 방법이 유사하다.
따라서, 원형 연결 리스트의 삭제를 구현하기 위해 단순 연결 리스트의 삭제과정을 다시 한번 살펴보자.

• 핵심 연산 1) 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
• 핵심 연산 2) 포인터 변수 cur을 한 칸 뒤로 이동시킨다.

원형 연결 리스트의 경우 아래와 같다.

단순 연결 리스트에서는 더미 노드가 있고 원형 연결 리스트에서는 더미 노드가 없기 때문에 삭제의 과정이 상황에 따라 달라질 수 있다.
따라서 다음 두 가지 예외적인 상황을 구분해야 한다.

• 예외적인 상황 1) 삭제할 노드를 tail이 가리키는 경우
• 예외적인 상황 2) 삭제할 노드가 리스트에 홀로 남은 경우

예외적인 상황 1의 경우 tail이 가리키는 노드가 삭제되므로 tail이 다른 노드를 가리키게 해야 한다. 따라서 삭제될 노드의 이전 노드가 tail이 가리키게 만든 다음 노드를 삭제해야한다.

예외적인 상황 2의 경우 마지막 노드까지 삭제를 한 뒤 포인터 변수 tail은 더 이상 가리킬 노드가 존재하지 않기 때문에 NULL을 가리키게 해야 한다.

위 두 경우를 모두 생각해서 코드를 작성하면 다음과 같다.

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
    Data rdata = rpos->data;
    
    if(rpos == plist->tail)						// 예외적인 상황 1) 삭제할 노드를 tail이 가리키는 경우
    {
    	if(plist->tail == plist->tail->next)	// 예외적인 상황 2) 삭제할 노드가 리스트에 홀로 남은 경우
        	plist->tail == NULL;
        else
        	plist->tail = plist->before;
    }
    
    plist->before->next = plist->cur->next;
    plist->cur = plist->before;
    
    free(rpos);
    (plist->numOfData)--;
    return rdata;
}

만약 원형 연결 리스트에서 단순 연결 리스트와 같이 더미 노드를 붙여주면 예외적인 상황 2가지를 고려하지 않고 간단해지지 않을까?
LRemove 함수 뿐만 아니라 노드의 추가 관련 두 함수의 구현도 간단해질 수 있다.
다만 데이터를 순환 참조하는 LNext 함수 구현에 있어서 더미 노드의 처리를 위한 코드를 추가로 삽입해야 한다는 단점이 생긴다.

5) 정리하기

위에 각 기능별 함수 구현이 끝났다.
이 모든 것을 헤더파일, 소스파일로 다시 한번 정리해보자.

// 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 LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    
    if(plist->tail == NULL)
    {
    	plist->tail = newNode;
        newNode->next = newNode;
    }
   	else
    {
    	newNode->next = plist->tail->next;
        plist->tail->next = newNode;
    }
    
    (plist->numOfData)++;
}

// 꼬리에 삽입
void LInsert(List * plist, Data data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    
    if(plist->tail == NULL)
    {
    	plist->tail = newNode;
        newNode->next = newNode;
    }
   	else
    {
    	newNode->next = plist->tail->next;
        plist->tail->next = newNode;
        plist->tail = newNode;
    }
    
    (plist->numOfData)++;
}

// 데이터 조회
// 첫 번째 노드
int LFirst(List * plist, Data * pdata)
{
	if(plist->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)
    	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(plist->tail == plist->tail->next)
        	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;
}

변형된 원형 연결 리스트 구현 3: main 함수 정의

위의 원형 연결 리스트를 테스트하기 위한 main 함수를 작성해보자.
그리고 그 실행 결과도 확인해보자!

// CLinkedListMain.c
#include <stdio.h>
#include "CLinkedList.h"

int main()
{
    // 원형 연결 리스트의 생성 및 초기화
    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-1; 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);
        }
    }
    return 0;
}

> gcc .\CLinkedList.c .\CLinkedListMain.c
> .\a.exe
> 출력
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 
1 3 5

---

05-2. 양방향 연결 리스트

양방향 연결 리스트(Doubly Linked List) 또는 이중 연결 리스트라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트다.
즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조다.

양방향 연결 리스트의 이해

양방향 연결 리스트의 유형 몇 가지를 그림을 통해서 소개하고자 한다.
가장 기본이 되는 모델을 다음 그림과 같다.

하나의 노드가 자신의 왼쪽과 오른쪽 노드를 동시에 가리키는 구조가 양방향 연결 리스트다.
때문에 양방향 연결 리스트의 노드를 표현하는 구조체는 다음과 같이 정의된다.

typedef struct _node
{
	Data data;				// typedef int Data
    struct _node * next;	// 오른쪽 노드를 가리키는 포인터 변수
    struct _node * prev;	// 왼쪽 노드를 가리키는 포인터 변수
} Node;

그리고 다음 그림과 같이 더미 노드가 추가된 양방향 연결 리스트도 존재하는데, 더미 노드의 이점은 단순 연결 리스트에서 보인 바와 같다.

그리고 다음 그림과 같이 양방향 연결 리스트면서 원형 연결 리스트의 구조를 동시에 지니는 리스트도 존재한다.

하지만 지금 보인 이 세 가지 모델이 양방향 연결 리스트의 전부는 아니다.
이들 모두 꼬리를 가리키는 포인터 변수 tail이 없었으나 필요하면 추가할 수 있고, 또 두 번째로 소개한 양방향 연결 리스트의 경우, 더미 노드가 앞에만 존재하는 형태이지만 필요에 따라서 뒤에도 더미 노드를 둘 수 있다.

그렇다면 양방향 연결 리스트는 다른 연결 리스트에 비해 구현하기 어려울까?
생각보다 많이 복잡하지 않다는 것을 이제부터 배울 예정이다!
양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현되던 거싱 오히려 단순하게 구현되는 부분도 있다.
그 예시로 LNext 함수를 살펴보자.

// CLinkedList.c (원형 연결 리스트의 LNext 함수)
int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)
    	return FALSE;
    
    plist->before = plist->cur;
    plist->cur = plist->cur->next;
    
    *pdata = plist->cur->data;
    return TRUE;
}

// DBLinkedList.c 예정 (양방향 연결 리스트의 LNext 함수)
int LNext(List * plist, Data * pdata)
{
	if(plist->cur->next == NULL)
    	return FALSE;
    
    plist->cur = plist->cur->next;
    *pdata = plist->cur->data;
    
    return TRUE;
}

위의 두 LNext 함수는 매우 유사하다.
LNext 함수는 두 번째 노드 이후의 데이터를 조회하는데 사용되는 함수이기 때문에 리스트의 구조에 따라 크게 달라지지 않는다.
양방향 연결 리스트가 더 복잡해보였지만 오히려 원형 연결 리스트에서 한 문장이 더 추가되어 있다.
포인터 변수 before에 대한 코드다.
이 포인터 변수는 리스트가 한 방향으로만 조회가 가능하기 때문에 사용된 (삭제 과정에서 필요했다.) 멤버이다.
하지만 양방향 연결 리스트에서는 양방향으로 얼마든지 조회가 가능하기 때문에 포인터 변수 before가 불필요하고, 이 포인터 변수를 유지하기 위한 다른 곳곳에 쓰인 문장들도 불필요해진다.
이렇듯 양방향으로 노드를 연결하는 것에는 큰 이점이 있다.
(물론 노드를 양방향으로 연결하기 위해 몇몇 추가되는 문장이 있지만 마냥 더 복잡해지거나 구현하기 어렵다는 고정 관념을 버리자!)

양방향 연결 리스트 구현 1: 헤더파일의 정의

총 두 가지 형태로 양방향 연결 리스트를 구현해 볼 것이다.
1) 양방향 연결 리스트
2) 더미 기반 양방향 연결 리스트 (연습 문제 2번)

그 중 배워 볼 첫 번째 양방향 연결 리스트는 아래 그림과 같다.

그리고 이러한 양방향 연결 리스트의 ADT를 구현한 헤더파일은 다음과 같다.

// 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 ListInsert(List * plist, Data data);

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

#endif

여기서 처음보는 함수는 LPrevious 함수일 것이다.
이 함수에 대한 설명은 소스파일의 구현 파트에서 알아보자.

양방향 연결 리스트 구현 2: 소스파일의 정의

1) 리스트의 초기화

양방향 연결 리스트의 초기화를 담당하는 ListInit 함수의 정의를 위해 다음 구조체를 보자.

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

위 구조체에서 주목해야 할 것은, 데이터의 조회의 목적으로 선언된 멤버 cur이 하나라는 것이다.
단순 연결 리스트에 있던 before가 없다.
따라서 ListInit 함수는 다음과 같이 간단히 정의된다.

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

조회에 사용되는 멤버 cur은 LFirst 함수가 호출됨에 동시에 초기화되기 때문에 리스트를 초기화 하는 단계에서 굳이 하지 않아도 된다.

2) 노드의 삽입

양방향 연결 리스트의 LInsert 함수는 리스트의 머리에 새 노드를 추가하는 방식으로 구현할 것이다.
따라서 head → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 1의 형태로 저장된다.
머리에 추가되는 새로운 노드 및 데이터의 저장과 관련해서 다음 두 가지 상황을 고려하면 된다.

1. 첫 번째 노드 추가.

   

   연결 리스트가 텅 빈 상황에서 연결 리스트의 포인터 변수 head에는 NULL이 저장되어 있다.
   새 노드의 next와 prev를 NULL로 초기화 하고, 새 노드를 head가 가리키게 한다.
   코드로 구현하면 아래와 같다.

   void LInsert(List * plist, Data data)
   {
     Node * newNode = (Node *)malloc(sizeof(Node));
     newNode->data = data;
     
     // 아래 문장에서 plist->head == NULL
     newNode->next = plist->head;
     newNode->prev = NULL;
     plist->head = newNode;	// 포인터 변수 head가 새 노드를 가리키기
     
     (plist->numOfData)++;
   }

2. 두 번째 이후 노드 추가.

   

   첫 번째 노드가 추가된 상황에서 두 번째 노드를 추가하기 위해 가장 먼저 할 일은 "새 노드를 생성하고, 이 새 노드와 head가 가리키는 노드가 서로를 가리키게 한다"는 것이다.

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

   

   이 과정은 newNode->next = plist->head;와 plist->head->prev = newNode; 문장으로 구현할 수 있다.
   이제 head가 새 노드를 가리키게 하고 새 노드의 prev에 NULL을 채워서 다음 그림과 같이 만들면 두 번째 이후 노드 추가도 끝이 난다.

   

   이 과정은 newNode->prev = NULL;과 plist->head = newnode; 문장으로 구현할 수 있다.

   위 1, 2번 케이스 모든 내용을 정리하면 아래와 같다.

   void LInsert(List * plist, Data data)
   {
   	Node * newNode = (Node *)malloc(sizeof(Node));
   	newNode->data = data;
   
   	// 첫 번째 노드일 경우 plist->head == NULL
   	newNode->next = plist->head;
     	if(plist->head != NULL)	// 두 번째 이후 노드 추가
     		plist->head->prev = newNode;
         
   	newNode->prev = NULL;
   	plist->head = newNode;
   
   	(plist->numOfData)++;
   }

3) 데이터 조회

양방향 연결 리스트에서 데이터 조회는 세 가지 함수로 이루어져 있다.
LFirst와 LNext 함수는 단방향 연결 리스트와 거의 차이가 없다. (오히려 간단해졌다.)
before라는 구조체 멤버가 없어졌기 때문에 코드를 정리하면 아래와 같다.

int LFirst(List * plist, Data * pdata)
{
	if(plist->head == NULL)
    	return FALSE;
    
    plist->cur = plist->head;	// cur이 첫 번째 노드를 가리키게
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->cur->next == NULL)
    	return FALSE;
    
    plist->cur = plist->cur->next;	// cur을 오른쪽으로 이동
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

int LPrevious(List * plist, Data * pdata)
{
	if(plist->cur->prev == NULL)
    	return FALSE;
    
    plist->cur = plist->cur->prev;	// cur을 왼쪽으로 이동
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

LPrevious 함수는 LNext 함수의 반대방향으로 데이터를 조회하기 때문에 구조체 Node의 멤버 next가 아닌 prev를 사용해서 cur을 이동시켰다.

+) 데이터 삭제

이 형태의 양방향 연결 리스트의 LRemove 함수를 정의하려면,
1) 첫 번째 노드를 삭제하는 경우
2) 마지막 노드를 삭제하는 경우
3) 그 이외의 노드를 삭제하는 경우
를 각각 별도로 구분해야하기 때문에 따로 구현하지 않을 예정이다.
대신 양방향 연결 리스트가 아니라면 구현하기 힘든 함수인 int LPrevious(List * plist, Data * pdata); 함수를 위에서 정의했다.
이 함수는 LFirst 또는 LNext 함수가 호출된 이후에 어디서든 호출이 가능하며,
LNext 함수가 오른쪽 노드로 이동해서 그 노드의 데이터를 참조하는 함수라면,
이 함수는 그와 반대인 왼쪽 노드로 이동해서 그 노드의 데이터를 참조한다.

4) 정리하기

위에서 구현한 헤더파일, 소스파일을 정리해보자.

// 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 ListInsert(List * plist, Data data);

int LFirst(List * plist, Data * data);
int LNext(List * plist, Data * data);
int LPrevious(List * plist, Data * data);
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;

	// 첫 번째 노드일 경우 plist->head == NULL
	newNode->next = plist->head;
  	if(plist->head != NULL)	// 두 번째 이후 노드 추가
  		plist->head->prev = newNode;
      
	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if(plist->head == NULL)
    	return FALSE;
    
    plist->cur = plist->head;	// cur이 첫 번째 노드를 가리키게
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->cur->next == NULL)
    	return FALSE;
    
    plist->cur = plist->cur->next;	// cur을 오른쪽으로 이동
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

int LPrevious(List * plist, Data * pdata)
{
	if(plist->cur->prev == NULL)
    	return FALSE;
    
    plist->cur = plist->cur->prev;	// cur을 왼쪽으로 이동
    *pdata = plist->cur->data;	// cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

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

양방향 연결 리스트 구현 3: 실행 파일의 정의

구현한 양방향 연결 리스트의 작동과 LPrevious 함수의 기능을 확인할 수 있는 실행 파일은 다음과 같다.

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

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

    // 8개의 데이터 저장
    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 \n", data);

        // 오른쪽 노드로 이동하며 데이터 조회
        while(LNext(&list, &data))
            printf("%d \n", data);
        
        // 왼쪽 노드로 이동하며 데이터 조회
        while(LPrevious(&list, &data))
            printf("%d \n", data);
        
        printf("\n\n");
    }

    return 0;
}

> gcc .\DBLinkedList.c .\DBLinkedListMain.c
> .\a.exe
> 출력
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 

LPrevious 함수는 LNext 함수와 반대 방향의 노드로 이동하면서 데이터를 반환한다.
따라서 LNext 함수와 마찬가지로 더 이상 참조할 노드가 없을 땐 0을 반환하도록 구현되어 있기 때문에 while 문이 사용되었다.

[추가] 더미 기반 양방향 연결 리스트

이번에는 더미 기반의 양방향 연결 리스트를 구현할 차례다.
이 연결 리스트의 특징은 다음과 같다.

• 양방향 연결 리스트다.
• 더미 노드가 리스트의 앞과 뒤에 각각 존재한다.
• 포인터 변수 head와 tail이 있어서 리스트의 앞과 뒤를 각각 가리킨다.

이번에는 포인터 변수가 head 뿐만 아니라 tail도 있다는 점에 유의해야한다.

더미 기반 양방향 연결 리스트 구현 1: 헤더 파일의 정의

첫번째로 구조체와 더미 기반 양방향 연결 리스트를 구현하기 위해 필요한 함수에 대해 정리 되어있는 헤더파일을 작성해보자.

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

더미 기반 양방향 연결 리스트 구현 2: 소스 파일의 정의

1) 리스트의 초기화

우선 그림으로 이해하고 코드르 작성해보자.
아래 그림은 리스트가 생성되고 초기화가 완료된 직후의 모습이다.

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

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

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

	plist->numOfData = 0;
}

2) 노드의 삽입

더미 기반 양방향 연결 리스트는 리스트의 머리와 꼬리에 각각 더미 노드가 존재하기 때문에 추가의 방법에 있어서 경우의 수가 나뉘지 않는다.
그래서 데이터 2가 저장되어 있는 노드가 있는 상태에서 새 노드에 데이터 4를 추가한다고 생각했을 때를 고려하면 일련의 과정이 필요하다는 것을 알 수 있다.

1. 새 노드를 생성하고 데이터를 저장한다.
2. 새 노드와 새 노드의 왼쪽에 위치할 노드가 서로를 가리키게 한다.
3. 새 노드와 새 노드의 오른쪽에 위치할 노드가 서로를 가리키게 한다.

이를 코드로 구현하면 다음과 같다.

void LInsert(List * plist, Data data) 
{
	// 1 단계
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	
    // 2 단계
	newNode->prev = plist->tail->prev;
	plist->tail->prev->next = newNode;
	
    // 3 단계
	newNode->next = plist->tail;
	plist->tail->prev = newNode;

	(plist->numOfData)++;
}

3) 데이터의 조회

더미 기반 양방향 연결 리스트 데이터 조회 함수는 LFirst와 LNext만으로 이루어져 있다.
조회는 비교적 단순하기 때문에 코드를 바로 보자.

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

4) 데이터의 삭제

삭제를 구현하기 위해서는 아래 그림을 예시로 2가 저장된 노드를 삭제한다고 가정하고 살펴보자.

①화살표와 ④화살표는 삭제를 위해서 다른 위치를 가리켜야 하는 화살표다.
②화살표와 ③화살표는 삭제할 노드에서 나오는 포인터 변수이기 때문에 신경쓰지 않아도 된다.
①화살표를 삭제될 노드의 다음 노드에, ④화살표를 삭제될 노드의 이전 노드에 연결하기만 하면 된다.
삭제된 이후의 모습은 다음과 같다.

이를 코드로 구현하면 다음과 같다.

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data remv = rpos->data;
	
	plist->cur->prev->next = plist->cur->next;	// 1번 화살표 가리키는 곳 변경
	plist->cur->next->prev = plist->cur->prev;	// 4번 화살표 가리키는 곳 변경

	plist->cur = plist->cur->prev;    // cur 위치를 재조정

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

5) 정리하기

위에서 설명한 소스코드를 하나로 정리하면 다음과 같다.

// 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->prev = NULL;
	plist->head->next = plist->tail;

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

	plist->numOfData = 0;
}

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

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

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

	(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 remv = rpos->data;

	plist->cur->prev->next = plist->cur->next;
	plist->cur->next->prev = plist->cur->prev;

	plist->cur = plist->cur->prev;

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

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

더미 기반 양방향 연결 리스트 구현 3: 실행 파일의 정의

위에서 구현한 헤더 파일과 소스 파일을 확인할 수 있는 실행 파일은 다음과 같다.

// DBDLinkedListMain.c
#include <stdio.h>
#include "DBDLinkedList.h"

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

	// 8개의 데이터 저장
	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");
	}

	// 2의 배수 전부 삭제
	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");
	}

	return 0;
}

> gcc .\DBDLinkedList.c .\DBDLinkedListMain.c
> .\a.exe
> 출력
1 2 3 4 5 6 7 8 
1 3 5 7

꼬리에 노드를 추가하기 때문에 1부터 8까지 데이터다 오름차순으로 잘 연결된 것을 확인할 수 있고
2의 배수들만 삭제된 것을 알 수 있다.

---

<Review>

우선 이번 Chapter에 대한 리뷰를 먼저 하자면
python으로 구현할 때 보다 한번 더 해서 그런지 머리속으로 생각하긴 어렵지 않았다.
(앞으로도 c언어로 공부하는 자료구조의 리뷰 서론은 항상 이 말일 것이다.)

다만 구현된 예제들을 바탕으로 새로운 유형의 연결 리스트를 구현해보라 했을 때 선뜻 코드로 작성하는 것이 익숙하지 않는다...
코드를 계속 따라 쳐도 이를 아직 익숙하지 않는 것은 더 공부하고 많이 코드를 쳐보라는 것인가?!
앞으로도 더 정진해야겠다~!

추가로 사담...
이번주엔 일이 정말 많았다...
아버지 사무실 일도 도와드리면서 SSAFY도 준비하면서
친구 결혼식 축가도 준비하면서
2onC라는 활동하고 있는 댄스팀의 새로운 비디오 촬영도 준비하면서 ㅋㅋㅋㅋㅋ
당장 19시간 뒤에 C언어 스터디가 있는데 아직 Chapter 하나를 더 해야한다 후...
그래도 해야지!!!

이렇게나마 덕분에 코딩을 손에 놓지 않고 할 수 있게 된거 같다.
잘했다 과거의 나자신!