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

단순 연결 리스트

단순 연결리스트란 한 쪽 방향으로만 연결 조회 삭제 등이 가능한 자료구조를 말한다. 보통 자료를 저장하는 도구로는 배열이 대표적이지만 배열은 크기가 정적이기 때문에 처음에 선언한 크기보다 더 많은 양을 저장하기 어렵다. 그래서 동적으로 저장 가능한 연결 리스트가 나온 것이다. 

연결 리스트의 ADT와 구현

연결 리스트의 ADT정의

● 리스트 초기화

● 데이터 저장

● 데이터 조회

● 데이터 삭제

● 리스트 정렬

이제 이 5개의 기능을 함수로 제시만 하고 구현하지 않으면 된다. 

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

연결리스트이 구조체와 헤더파일 정의

노드를 표현한 구조체

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;

위 변수들을 main 함수의 지역변수나 전역변수로 선언하지 않은 이유는 코드의 복잡성을 줄이기 위해서이다.

연결 리스트의 구현

리스트의 초기화

방법은 LinkedList라고 정의한 구조체를 초기화해주면 된다.

void ListInit(List * plist)
{
    plist->head = (Node*)malloc(sizeof(Node));   //더미(텅빈) 노드를 생성
    plist->head->next = NULL;    //첫 번째 노드가 없으므로 NULL로 초기화
    plist->comp = NULL;        //아직 정렬의 기준을 정하지 않았기 때문에 NULL로 초기화
    plist->numOfData = 0;
}

여기서 더미 노드를 생성하는 이유는 삽입, 삭제 를 구현하는 과정에서 코드를 좀 더 간결하게 만들어 주기 위함이다. 

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

위 그림에는 표현되지 않았지만 리스트의 멤버 comp가 NULL, numOfData가 0으로 초기화 됬다.

노드의 추가

노드의 추가를 위한 함수는 다음과 같다.

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

 여기서 comp에 어떤 기준의 정렬이 저장되냐에 따라 FInsert나 SInser가 호출된다. 

FInser함수는 다음과 같다.

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

여기서 포인터 변수 head가 NUL이 아닌, 더미 노드를 가리키고 있다는 사실을 잊지 말아야 한다.

그럼 연결리스트에 4와 6이 저장된 상태에서 위의 함수를 FInsert(plist, 2); 같이 호출되었다고 가정해보았을 때의 그림은 아래와 같다.

이제 SInsert함수를 설명할 차례이다. SInsrt함수를 정의하기 전에 comp를 초기화 할 SetSortRule이라는 함수를 정의해 보겠다.

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;
    newNode->data = data;
 
    while(pred->next != NULL &&
        plist->comp(data, pred->next->data) != 0) //comp가 0을 반환하면 첫 인자가 head에 더 가까워야 함
    {                                             //comp가 1을 반환하면 두번째 인자가 head에 더 가까워야 함
        pred = pred->next;
    }
 
    newNode->next = pred->next;
    pred->next = newNode;
 
    (plist->numOfData)++;
}

이 함수의 결과를 그림으로 나타내면 아래와 같다.

아래 WhoIsPrecede함수는 정렬 기준을 정의한 함수이다. 

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

위 함수는 오름차순을 기준으로 정의한 함수이다. 자신이 정렬 기준을 바꾸고 싶다면 얼마든지 새롭게 정의해도 상관없다.(단, comp의 등록될 반환값을 생각하면서 정의)

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

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