C로 구현하는 자료구조 - Linked List

자료구조의 일종인 링크드리스트는 각 노드당 데이터를 저장하는 데이터필드 영역과 다음 노드를 가리키는 노드 포인터 영역으로 구성된 자료구조이다. 비슷한 방식으로 배열이 있지만 배열은 처음부터 메모리를 할당하고 시작하기 때문에, 링크드리스트에 비해 데이터의 삽입이나 삭제가 어렵다. 반면, 링크드리스트는 노드를 데이터를 삽입할 때마다 메모리를 할당하고 데이터를 이어주는 형식이라 배열에 비해 메모리 낭비가 덜 하다는 장점이 있다.

Implementation

structure

typedef struct _node Node;    // 구조체 노드 형명재지정
 
struct _node{         // 데이터를 보관할 노드(자기참조 구조체)
    Node *prev;               // 앞 노드를 가리키는 멤버
    DataType data;            // 데이터 저장 멤버
    Node *next;               // 뒷 노드를 가리키는 멤버
};
 
typedef struct _linkedList{   // 리스트 관리 구조체
    Node *head;               // 헤드포인터 (헤드노드 가리킴)
    Node *cur;                // 특정 작업 시 노드를 가리키기 위한 포인터
    Node *tail;               // 테일포인터 (테일노드 가리킴)
    int length;               // 실제 데이터노드의 갯수
}LinkedList;

LinkedList 구조체는 리스트 관리 구조체로서,

순회를 하기 위한 Head, Tail 노드만을 가리키는 노드 포인터와
현재 노드 가리킴 및 여러 용도로 쓰이는 노드 포인터,
노드의 개수를 저장하는 int형 변수로 이루어져 있다.

initalization

void create(LinkedList * lp) {
    lp->head = (Node *)malloc(sizeof(Node)); //헤드 노드 생성
    assert(lp->head!=NULL);
    lp->tail = (Node *)malloc(sizeof(Node)); //테일 노드 생성
    assert(lp->tail!=NULL);
    /*head node와 tail node를 연결 함*/
    lp->head->prev=lp->head;
    lp->head->next=lp->tail;
    lp->tail->prev=lp->head;
    lp->tail->next=lp->tail;
    lp->cur=NULL; //cur가 NULL pointer로 초기화
    lp->length=0; //데이터 노드의 개수를 0으로 초기화
 
    return ;
}

헤드 노드, 테일 노드를 할당 후, 헤드 노드와 테일 노드를 서로 연결해준다.

push node

Node * makeNode(DataType *dataPtr, Node *prev, Node *next) {
    Node *np;
    np = (Node *)malloc(sizeof(Node)); //새로운 노드 생성
    assert(np!=NULL);
    np->prev = prev;
    np->next = next;
    np->data = *dataPtr;
    if(prev != NULL) {
        prev->next = np;
    }
    if(next != NULL) {
        next->prev = np;
    }
    return np;
}
 
Node * appendFromTail(LinkedList *lp, DataType *dataPtr)  {
    lp->cur = makeNode(dataPtr, lp->tail->prev, lp->tail);  //새로운 노드 생성
    assert(lp->cur!=NULL);
    lp->length++; //데이터개수 1 증가
 
    return lp->cur;
}

양방향 연결 리스트에서 노드를 삽입하는 방법은 두 가지가 있다, 첫 번째는 헤드 노드 앞으로 데이터를 삽입하는 법과 테일 노 드 뒤쪽으로 데이터를 삽입하는 방식이다. 헤드 노드 앞으로 데이터를 삽입하는 방법은 데이터를 다 넣고 출력을 하게 되면 데이터의 순서가 들어온 순서랑 역순이 되므로 여기선, 테일 노 드 뒤로 삽입하는 코드를 썼다. 우선, 첫째로 makeNode 함수를 이용하여 노드를 하나 할당 후, 데이터 개수를 1개 증가시켜준다. makeNode 함수는 malloc을 통해 메모리를 할당 후, 전달인자로 이전 노드, 다음 노드를 가져와 서로 선을 이어주는 함수이다.

remove node

void deleteNode (LinkedList *lp, Node *target) {
    if(target==NULL) {
        return;
    }
    //삭제할 데이터의 앞,뒤 노드를 연결시킴
    target->prev->next=target->next; 
    target->next->prev=target->prev;
    free(target);       // target노드 삭제
    lp->length--;       // 데이터 개수 1 감소
}

void destroy (LinkedList *lp) { 
    while(lp->head->next != lp->tail) { // 데이터 노드가 있다면 해제
        deleteNode(lp,lp->head->next); // head 노드 바로 뒷 노드를 삭제
    }
    free(lp->head); // head 노드 삭제
    free(lp->tail); // tail 노드 삭제
    lp->head = lp->cur = lp->tail = NULL; //모든 포인터를 NULL로 초기화
    lp->length = 0; //데이터개수 0으로 초기화
    return ;
}

노드를 삭제하는 함수, 모든 노드를 삭제하는 함수이다. deleteNode함수는 전달인자로 삭제할 노드 (target)을 받아 target노드의 이전노드와 target노드의 다음노드를 서로 이어준 뒤, target노드를 free함수를 통해 메모리를 해제하는 방식으로 이루어져있다. destory함수는 우선 헤드 노드와 테일 노드를 삭제 한 후, 나머지 데이터노드들을 순차적으로 메모리 해제해주는 방식이다.

sort

void deleteNode (LinkedList *lp, Node *target)
void sortList(LinkedList *lp, int (*compare)(DataType *, DataType *)) {
    Node *tp;
    Node *target;
    DataType temp;  // swap용 임시변수 
 
    lp->cur=lp->head->next;  // 첫 데이터 노드를 가리키게 하고
    while(lp->cur!=lp->tail) {// 맨 뒷 노드까지 검색
        target = lp->cur;
        tp=lp->cur->next; // cur의 다음 노드를 가리키게 함
        while(tp!=lp->tail) {
            if(compare(&target->data, &tp->data) > 0) {
                target = tp;
            }
            tp=tp->next;
        }
        temp = lp->cur->data;
        lp->cur->data = target->data;
        target->data = temp;
 
        lp->cur=lp->cur->next;
    }
    return;
}

변수로는 임시 노드 포인터 tp와 정렬할때 바뀜이 되는 대상 임시 노드 포인터 target, 그리고 Data Swap을 위해 필요한 temp변수가 있다. 링크드리스트 관리 구조체의 cur포인터를 헤드노드 뒷 노드 즉, 첫번째 데이터노드를 가리키게 한 뒤, 반복문을 통해 데이터 끝까지 갈 수 있도록 해준다. 여기서, target노드는 현재 cur포인터로 지정해주고 임시 tp포인터는 cur포인터의 다음 노드를 가리키게 한다. (ex) 45 - 25 - 11 - 5 - 23 의 구조로 이루어져있는 링크드 리스트일때 target을 45, tp를 25로 지정) compare함수를 통해 비교하고 그것이 참이면 서로 swap해준다.

Implementation#

structure#

initalization#

push node#

remove node#

sort#