Chap 04. 연결 리스트2 (동적 할당 기반 리스트)

배열 기반의 리스트는 인덱스 값 기준으로 데이터의 참조가 쉽지만 크기가 초기에 정해져있다는 단점이 있다.

동적 할당 기반의 리스트는 크기의 변경이 가능하다. 

 

문제 04-1 [연결 리스트 관련 코드에 익숙해지기] 

연결 리스트는 새로 삽입되는 노드를 tail에 추가한다.

하지만 여기서는 head에 추가되도록 해본다.

 

#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("enter number: ");
        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");

    if(head == NULL)
    {
        printf("empty list\n");
    }
    else
    {
        cur = head;
        printf("%d ", cur->data);

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

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

        free(delNode);

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

 

---

연결 리스트에 새로운 노드를 추가하는 방법에는 두가지가 있다.

 

리스트의 첫 부분을 가르키는 head에 추가

- 장점: 포인터 변수 tail이 필요없다

- 단점: 저장된 순서를 유지하지 않는다 

 

리스트의 끝을 가르키는 tail에 추가

- 저장된 순서가 유지된다 

- 포인터 변수 tail이 필요하다 

 

---

dummy node

노드를 추가하는 다음 코드를 보면 

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

head == NULL 일때, 즉 첫번째 노드를 추가할때와 그 이후 노드를 추가할때의 코드가 다르다.

따라서 이를 해결하는 방법으로 dummy node를 추가하는 방법이있다.

 

dummy node를 리스트의 맨앞에 넣어놓으면, 처음에 추가되는 노드가 dummy node의 다음 노드, 즉 두번째 노드가 되므로 위의 문제가 해결된다. 

 

 

문제 04-2 [더미 노드를 적용했을 때의 코드변화 확인하기]

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

    // dummy node
    Node *dummy = (Node*)malloc(sizeof(Node));
    head = dummy;
    tail = dummy; //

    while(1)
    {
        printf("enter number: ");
        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");

    // 출력
    if(tail == head)
    {
        printf("empty list\n");
    }
    else
    {
        cur = head;

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

    // 메모리 해제
    if(head == NULL)
    {
        return 0;
    }
    else
    {
        Node *delNode = head;
        Node *delNextNode = head->next;

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

코드를 보면 처음에 head와 tail이 더미노드를 가르키도록 되어있고, 

그 이후에 노드의 추가, 삭제 할때를 보면 이전과 다르게 첫번째 노드와 그 이후 노드들의 구분이 사라졌다. 

이것이 더미 노드를 리스트의 첫 부분에 추가하는 이유다.

 

---

더미노드 기반의 단순 연결 리스트

이 연결리스트는 리스트의 첫 부분에 더미노드가 있고, 새로운 노드를 리스트의 앞에 추가하도록 구현했다. 

 

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

 

DLinkedList.c 

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

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

// header에 없음, 즉 리스트 사용자가 임의로 호출할수 없는 함수
void FInsert(List *plist, LData data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    // data가 저장된 새로운 노드가 다른 노드 가르키도록함
    newNode->next = plist->head->next;
    // dummy node가 새노드 가르키도록함
    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)
{
    // dummy node가 아무 노드도 가르키고 있지 않다면
    if(plist->head->next == NULL)
        return FALSE;

    // before가 더미노드 가르키도록 하고
    plist->before = plist->head;
    // cur은 첫 노드 가르키도록 함
    plist->cur = plist->head->next;

    // 첫 노드의 데이터 참조
    *pdata = plist->cur->data;
    return TRUE;
}

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

    // before는 cur를 가르키고
    plist->before = plist->cur;
    // cur은 다음을 가르킴
    plist->cur = plist->cur->next;

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

LData LRemove(List *plist)
{
    // 지워야할 노드
    Node *rpos = plist->cur;
    LData rdata = rpos->data;

    // 소멸 대상을 리스트에서 제거
    // before이 cur의 다음 노드를 가르키도록 함으로서 cur 노드가 리스트에서 제외됨
    plist->before->next = plist->cur->next;
    // cur은 before을 가르키도록 함 (한칸 좌측 이동)
    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;
}

// 정렬기준 있을시 삽입
void SInsert(List *plist, LData data)
{
    // 새 노드 생성
    Node *newNode = (Node*)malloc(sizeof(Node));
    // pred는 더미 노드 가르킴
    Node *pred = plist->head;
    newNode->data = data;

    // pred가 마지막 노드를 가르키지 않고 && comp 함수가 0을 리턴하지 않는다면
    // (새 노드가 들어갈 자리 찾지못했다면) pred를 다음노드로 이동 시킨다
    while(pred->next != NULL && plist->comp(data, pred->next->data) != 0)
    {
        pred = pred->next;
    }

    newNode->next = pred->next; // 새 노드의 오른쪽을 연결
    pred->next = newNode; // 새 노드의 왼쪽을 연결
    (plist->numOfData)++;
}

 

또한 위의 SetSortRule 함수에 두번째 매개변수로 전달될 정렬의 기준을 알리는 함수는 메인함수가 있는 소스파일에 존재해야 한다.

이유는 정렬기준은 리스트 자료구조의 사용자가 임의로 정의할수 있도록 하기 위해서다. 

// 오름차순 정렬
// 정렬기준은 리스트의 사용자가 정할수있도록 메인함수가 있는 소스파일에 있어야함
int WhoIsPrecede(int d1, int d2)
{
    if(d1 < d2) // d1이 정렬순서상 앞선다
        return 0;
    else
        return 1;
}

 

---

문제 04-4 [정렬의 기준으로 활용되는 함수의 정의]

 

int OrderForPoint(Point *p1, Point *p2)
{
    if(p1->xpos == p2->xpos)
    {
        if(p1->ypos < p2->ypos) return 0;
        else return 1;
    }
    if(p1->xpos < p2->xpos) return 0;
    else return 1;
}