[시스템프로그래밍] 연결리스트, Linked list

함수에서 공통적으로 포인터를 활용해 Linked list의 모든 정보를 넘겨주는 것을 방지하였다.

pHead는 항상 첫 노드를 가리키고 있으며, 한 노드는 자신의 뒤에 뒤따르는 노드를 포인터로 가리키고 있다.

이런 방식으로 입력되는 데이터를 계속 공간을 확장하여 저장하는 방식이다.

// 20201014_Linked_List.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <stdio.h>
#include<stdlib.h>

//일반적으로 연결리스트를 접근하려면 반드시 첫 노드를 통해야 한다.
typedef struct node {
    int data;                   //저장하는 겂
    struct node* pNext;         //다음 노드를 가리킨다.
} Node;

//Function:printLL()
//input: Linked List (헤드포인터)
//output: None

void printLL(Node* pHead) {
    Node* ptr = pHead;
    int i = 0;
    while (ptr != NULL) {
        printf("[%d] value : %d\n", i++,ptr->data);
        ptr = ptr->pNext;
    }
}

//Function:createNode()     힙영역에서 노드 공간을 할당받아 입력받은 값으로 data설정, pNext는 NULL로 설정
//input: value 
//output: pointer to the created node
Node* createNode(int val) {
    Node* ptr;
    ptr = (Node*)malloc(sizeof(Node));
    ptr->data = val;
    ptr->pNext = NULL;
    return ptr;
}

//Function:addHead()     힙영역에서 노드 공간을 할당받아 입력받은 값으로 data설정, pNext는 NULL로 설정
//input: Linked List, Node
//output: None
//side effect: input node is added to the head of the linked list

//함수에서는 포인터를 복사에서 함수 내부에서 활용하는 것이지만 우리는 이런 동작을 원하는 것이 아니다.
//따라서 (포인터)를 포인터로 지명해서 실제 공간에 데이터를 변화시킨다.
void addHead(Node** ppHead, Node* pNewNode) {
    //pHead 포인터가 가리키는 값에 pNewNode->Next를 담아준다.
    pNewNode->pNext = *ppHead;    //#1
    //이후 pHead를 pNewNode로 변경해준다.
    *ppHead = pNewNode;
}


//이건 내가 만들어본 함수
//굳이 이중 포인터 대신에
//바로 pHead의 주소값을 인자로 받아와
//pNewNode->pNext를 연결해서
//pHead에 다시 담아준다.
//1. (pNewNode) -> (phead)를 만들어준다.
//2. pHead를 1로 치환
//3. 끝!
void addHead_my_way(Node* & pHead, Node* pNewNode) {
    //pHead 포인터가 가리키는 값에 pNewNode->Next를 담아준다.
    pNewNode->pNext = pHead;    //#1
    //이후 pHead를 pNewNode로 변경해준다.
    pHead = pNewNode;
}


//Function: countLL()
//input: Linked List pointer
//output: the number of nodes in the linked list
int countLL(Node* pHead) {
    int i = 1;
    Node* ptr = pHead;
    while (ptr != NULL) {
        i++;
        printf("value = %d\n", ptr->data);
        ptr = ptr->pNext;
    }
    return i;
}








int main()
{
    Node n1, n2;
    //약속, 빈 연결리스트는 헤드포인터 값을 NULL로 한다.
    Node* pHead=NULL;        //linked list의 첫 노드 (Head)를 가리키기 위한 포인터 변수
    //node를 동적으로 할당하는 동작 구현
    //이때 할당되는 공간은 heap영역이다.
    //heap은 동적 할당에 활용된다.
    //pHead = createNode(23);
    //pHead->pNext = createNode(23);

    for (int i = 0; i < 1000; i++) {
        //실제 포인터의 주소값을 전달한다.
        addHead(&pHead, createNode(rand()));
    }
    
    //addHead_my_way(pHead, createNode(17));
    
    ///////////////////
    //1교시 내용
    /*n1.data = 17;
    n1.pNext = &n2;
    n2.data = 23;
    n2.pNext = NULL;

    pHead = &n1;*/

    //포인터를 static으로 생성하는 예제를 진행하였다.
    /////////////////////////

    printLL(pHead);

    printf("the number of nodes = %d\n", countLL(pHead));

    return 0;
}