단순 연결 리스트(2/2)

단순 연결 리스트

리스트의 ADT와 구현

리스트의 구현

데이터 조회

데이터 조회로 쓰이는 함수는 LFirst와 LNext이다.

LFirst함수는 다음과 같다.

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

위 함수가 호출됬을 때의 6, 7번째 줄을 그림으로 나타내면 다음과 같다.

그리고 마지막으로 9번째 줄을 통해 첫 번째 데이터가 반환된다.

여기서 before을 cur보다 하나 앞선 노드를 가리키게 한 이유는 삭제와 관련되어 있으니 일단은 before가 cur보다 하나 앞선 노드를 가리킨다는 사실에 주목하자. 그리고 이 관계는 이어서 소개하는 LNext함수가 호출되어도 유지되어야 한다.

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

LNext함수와 LFirst함수는 많이 비슷해 보이지만 6, 7번째 줄이 다르다. 이 문장이 실행됬을 때의 그림은 다음과 같다.

이와 같이 cur이 마지막 노드를 가리킬 때까지 LNext함수가 계속 호출되면, cur과 before가 한 칸씩 다음 노드로 이동을 하니 cur을 이용해 모든 데이터를 참조 할 수 있다.

노드의 삭제

LRemove함수의 기능은 바로 이전에 호출된 LFirst 혹은 LNext함수가 반환한 데이터를 삭제하는 것이다.

LRemvoe가 호출됬다고 가정했을 때 그림으로 나타내면 다음과 같다.

여기서 주의해야 할 점은 cur의 위치가 재조명 됬다는 것이다. 4가 저장된 노드가 지워졌다고 해도 cur의 위치를 6으로 지정해서는 안 된다. 6으로 지정할 경우 6까지 참조가 되었다는 의미이기 때문이다. 그리고 'before도 한칸 뒤로 옮겨야 되지 않나?'라고 생각할 수 있지만 LFirst나 LNext가 호출될 경우 before은 cur보다 다시 한 칸 뒤로 밀려날 것이기 때문에 상관없다. 그리고 한 칸 뒤로 옮기는 것은 코드를 매우 복잡하게 만들기 때문에 권하지 않는다.

LData LRemove(List * plist)
{
    Node * rpos = plist->cur; //삭제할 노드의 위치를 또 다른 포인터 변수에 저장
    LData rdata = rpos->data; //현재 참조하고 있는 데이터를 저장
 
    plist->before->next = plist->cur->next; //삭제할 노드의 다음 노드를 삭제하기 전 노드와 연결
    plist->cur = plist->before;    //cur의 위치를 before로 이동
 
    free(rpos); //노드 소멸
    (plist->numOfData)--;    //데이터 감소
    return rdata;
}

하나로 묶기

이때까지 설명한 코드들을 하나로 묶어 보겠다.

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;    //cur의 위치를 기억하기 위한 포인터 변수
    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

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;
    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)++;
}
 
 
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;    //before은 더미 노드를 가리킴
    plist->cur = plist->head->next;    //cur은 첫 번째 노드를 가리킴
 
    *pdata = plist->cur->data;    //첫 번째 데이터를 전달
    return TRUE;
}
 
int LNext(List * plist, LData * pdata)
{
    if(plist->cur->next == NULL)
        return FALSE;
 
    plist->before = plist->cur; //cur이 가리키던 노드를 before가 가리킴
    plist->cur = plist->cur->next;    //cur은 그 다음 노드를 가리킴
 
    *pdata = plist->cur->data;    //cur이 가리키는 노드의 데이터 전달
    return TRUE;
}
 
LData LRemove(List * plist)
{
    Node * rpos = plist->cur; //삭제할 노드의 위치를 또 다른 포인터 변수에 저장
    LData rdata = rpos->data; //현재 참조하고 있는 데이터를 저장
 
    plist->before->next = plist->cur->next; //삭제할 노드의 다음 노드를 삭제하기 전 노드와 연결
    plist->cur = plist->before;    //cur의 위치를 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; //정렬기준을 정의한 함수를 헤디파일에서 정의한 함수 포인터에 저장
}

DLinkedListMain.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(void)
{
    // List의 생성 및 초기화  ////////////
    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("현재 데이터의 수: %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;
}

-----------------------------------------

이 글은 열혈 자료구조를 보고 정리한 글입니다.