연결리스트를 전격 해부해보자!! [번외]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

연결리스트를 전격 해부해보자!! [번외]

 

앞서서 연결리스트에 대해서 포스트를 해보았지만, 흠 내용이 석연치 않았습니다... 불만족스러웠죠. 그래서 내놓은 해결책으로 연결리스트 만드는 코드를 작성하고 전격적으로 코드를 뜯어서 해부했습니다. 

 

다른 내용은 없이 코드에 다 담아 놓았기 때문에 한번 읽어보시면 될것같습니다!!

 

 

//단순 연결리스트 프로그램
//**Post on c**
//code by hazard3_000sung
#include <stdio.h>//표준 입출력 라이브러리
#include <stdlib.h> //문자열 변환, 동적 메모리관리 라이브러리
#include <string.h> //c형식 문자열을 다룰 수 있는 함수+메모리 블럭
 
//연결리스트의 노드 구조 구조체 정의 블록
typedef struct ListNode
{
    char value[5];
    struct ListNode* link; // 리스트노드 구조체의 포인터 변수 생성
}listNode; //본 구조체를 listNode사용
 
//연결리스트의 시작점 노드
 
typedef struct 
{
    listNode* first;
}linkedList_f;
 
//빈 연결리스트를 생성하는 알고리즘 삽입
linkedList_f* createLinkedList_f(void)
{
    linkedList_f* N;//시작노드를 포인터 변수 N생성
    N = (linkedList_f*)malloc(sizeof(linkedList_f));//malloc함수 이용하여 시작노드크기 만큼의 메모리 할당
    N -> first = NULL;//빈 연결리스트이므로 NULL삽입
    return N;//N시작점 반환
}
 
//연결 리스트 메모리를 해제 해주는 알고리즘삽임**
//malloc함수로 동적메모리 할당한 리스트는 프로그램이 종료될때 반환되야되기 때문임
void freeLinkedList_f(linkedList_f* N)
{
    listNode* m;//우선 맨 처음 생성한 리스트노드의 포인터 변수 생성
    while (N -> first != NULL)
    //while반복문으로 시작 노드가 NULL이 아닐때까지 연산 반복
    {
        m = N -> first; //포인터 변수는 시작노드가 가르키는 첫번째 시작점 포인터 변수를 가르킴
        N -> first = N -> first -> link;
        //복잡하네요; 
        //리스트의 시작인 퍼스트노드가 링크 퍼스트 포인터 변수가 가르키는 링크안의 주소를 삽입
        free(m);
        //리스트노드가 할당받았던 메모리를 해제
        m = NULL;
        //리스트노드안의 변수를 NULL로 바꾸고 반복문 종료
    }
}
//연결리스트를 출력하는 알고리즘
void printNode(linkedList_f* N)
{
    listNode* m;//리스트노드의 포인터 변수 m을 선언
    printf("N = {");// 출력시 처음 부분 [출력 예) N = {1,2,3}]
    m  = N -> first;//리스트노드의 포인터 변수인 m에 링크드 리스트 시작점노드가 시작퍼스트노드를 가리키도록 선언
    while(m != NULL)//출력할 결과물이 없을때 까지 출력하는 반복문
    {
        printf("%s", m->value);
        m = m -> link;
        if(m != NULL)printf(",");//출력할 결과물이 나올때까지 콤마를 출력하여 구분
    }
    printf("} \n");
}
 
//연결리스트에 삽입하는 알고리즘
void insertFirstNode(linkedList_f * N, char *a)
{
    //리스트노드의 포인터변수 newnode선언
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    //newnode에 동적 메모리 할당
    strcpy(newNode -> value,a);
    //함수에 a라는 인자에 전달받은 문자열을 value로 복사
    newNode -> link = N -> first;
    N -> first = newNode;
 
}
 
//노드 sec뒤에 새로운 노드 추가 
void insertNode(linkedList_f *N, listNode *sec, char *a)
{
    //newNode 리스트노드 포인터 변수로 선언
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode -> value, a);
    //연결리스트가 NULL일 경우에 
    if(N == NULL)
    {
        //newNode를 첫번째노드로 연결
        newNode -> link = NULL;
        N -> first = newNode;
    }
    //삽입위치를 지정하는 sec값이 null인 경우에만 
    else if(sec == NULL)
    {
        //newNode 를 첫번째 노드로 삽입 함
        //그래야 순서를 맞출 수 있기때문!
        N -> first = newNode;
    }
    else
    {
        newNode -> link = sec -> link;
        sec -> link = newNode;
    }
}
 
//맨 마지막 노드로 삽입하는 알고리즘
//맨 마지막 노드의 링크 값은 null이기 때문에 따로 만들어줌
void insertfinalNode(linkedList_f* N, char* a)
{
    listNode* newNode;
    listNode* second;//마지막 노드를 second로 선언
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode -> value, a);
 
    newNode -> link = NULL;
    if(N -> first == NULL)//현재 리스트가 null인 경우에만
    {
        //newNode를 연결리스트의 시작 노드로 연결
        N -> first = newNode;
        return;
    }
    //현재 연결리스트가 null이 아닌경우에만 
    second = N -> first;
    while(second -> link != NULL){second = second -> link;}
    //newNode를 마지막 노드(second)의 다음 노드로 연결함
    second -> link = newNode;
}
 
int main()
{
    linkedList_f* N;
    //linkedList_f의 포인터 변수로 N을 선언
    N = createLinkedList_f();
    //앞서 null 연결리스트를 만들어주는 구조체를 N에 삽입 후 생성
    printf("1. 빈 연결리스트를 생성합니다. \n");
    printNode(N);
 
    printf("2. 연결리스트에 사과를 삽입하겠습니다. \n");
    insertFirstNode(N, "사과");
    printNode(N);
 
    printf("3. 연결리스트 마지막 부분에 오렌지를 삽입하겠습니다. \n ");
    insertfinalNode(N, "오렌지");
    printNode(N);
 
    printf("4. 연결리스트 사과 앞 부분에 귤을 삽입하겠습니다.\n");
    insertFirstNode(N, "귤");
    printNode(N);
 
    printf("5. 연결리스트에 할당된 메모리를 해제하여 빈 연결리스트로 만들겠습니다. \n");
    freeLinkedList_f(N);
    printNode(N);
 

읽어주셔서 감사합니다!!

 

댓글 / 피드백 모두 환영합니다~~~~

 

연결리스트 리뉴얼 버전 ->

hazarddev.tistory.com/60

[C] 단일 연결리스트 누구나 쉽게 이해하기!(LinkedList)