[자료구조] 단일 연결 리스트(Singly Linked List) 입력, 출력함수 구현 - C

단일 연결리스트를 사용하기 위해 우선 구조체를 정의해준다.

 

typedef struct _node
{
    int data;
    struct _node *link;
} Node;

 

 

그리고 값을 입력하면 그 값을 연결리스트에 넣어주는 함수를 작성하겠다.

함수는 아래의 경우로 나눠질 것이다.

• 연결리스트에 아무 값도 들어있지 않은 상태(NULL 상태)
• 연결리스트에 값이 들어있는 상태

 

위 조건을 참고하여 AddNode함수를 작성해보겠다.

void AddNode(Node **head, int val) // main에서 head를 가져오므로 더블포인터(**) 사용!
{
    Node *newnode = (Node *)malloc(sizeof(Node)); // 새로운 노드 생성!
    newnode->data = val; // 값 넣기
    newnode->link = *head; // newnode를 head가 가리키던 노드에 연결
    *head = newnode; // head가 newnode를 가리키게 설정
    return;
}

 

매개변수로 연결리스트의 head 와 추가할 값(val)을 받는다.

새로운 노드를 newnode로 생성하여, newnode의 data에 val을 넣는다.

 

head가 NULL인 상황을 따로 가정해주지 않은 이유는 어짜피 head가 NULL이라면 newnode의 link가 null이 되고, head에 newnode를 가리키게 하여 문제가 발생하지 않기 때문에 따로 가정해줄 필요가 없다.

 

그리고 여기서 중요한 점은 head를 더블 포인터(**)를 사용하여 참조했다는 점이다.

그 이유는 main 함수에 있다. 

main을 작성하겠다.

int main(void)
{
    int sel = 0;
    Node *head = (Node *)malloc(sizeof(Node)); // **** 중요 ****
    head = NULL;

    while (1)
    {
        printf("1.추가\t2.삭제\t3.출력\t4.거꾸로\t5.종료\n");
        printf("메뉴 선택 : ");
        scanf("%d", &sel);
        if (sel == 1) // 1. 추가를 선택한 경우
        {
            int n = 0;
            printf("추가할 값을 입력하세요 : ");
            scanf("%d", &n);
            AddNode(&head, n);
        }
        else if (sel == 2) // 2. 삭제를 선택한 경우
        {
        }
        else if (sel == 3) // 3. 출력을 선택한 경우
        {
        }
        else if (sel == 4) // 4. 거꾸로를 선택한 경우
        {
        }
        else // 5번, 그리고 이외의 수를 선택한 경우
        {
            break;
        }
    }
}

 

 

위 코드에서는 1번을 선택한 경우에 값을 추가하게 설계했다.

 

그리고 1번을 선택하면, 추가할 값을 입력받고, 그 값을 가지고 AddNode를 호출한다.

그리고 상단에는 head를 Node 포인터로 선언한 것을 확인할 수 있다.

 

head는 연결 리스트의 첫번째 노드를 가리키기 위해 생성한 변수이다.

그래서 포인터 변수로 생성하여 주소값을 저장하는 것이다.

 

그리고 head를 main에서 포인터 변수로 선언하였기 때문에, main 밖에서 이 head에 접근하려면 더블 포인터(**)가 사용되어야 하는 것이다.

 

 

위 함수와 main 을 사용하여 추가를 실행해보겠다.(출력함수는 아래에 첨부하겠다.)

 

1과 2를 입력고 나서 출력을 선택하니 2 -> 1 -> 과 같이 출력되었다.

그리고 계속해서 선택하는 화면이 나오게끔 작동한다.

 

 

이제 위처럼 연결 리스트를 출력하는 함수를 작성하겠다. (코딩 스타일에 따라 형식이 달라질 수 있으니 참고만 하기 바란다.)

void ShowNode(Node **head)
{
    Node *temp = (Node *)malloc(sizeof(Node));
    temp = *head; // main의 head 주소값을 temp에 넣는다. -> temp의 변경에 따라 head도 변경시키기 위함
    while (temp != NULL) // temp == NULL이면 비어있는 연결리스트 or 마지막 노드인 것
    {
        printf("%d -> ", temp->data); // 출력
        temp = temp->link; // 다음 노드로 이동
    }
    printf("\n");
    free(temp);
    return;
}

 

ShowNode도 main에서 head를 받아와서 시작한다.

temp라는 임시 포인터 변수를 하나 생성한다.

(head는 연결 리스트의 머리 부분을 고정적으로 가리켜야한다. 그렇지 않으면 시작 주소값을 기억하지 못해 데이터의 주소값을 잃어버릴 수 있다.) 

 

그리고 temp에 head의 주소값을 넣는다.

temp가 main에 있는 head값도 같이 변경시킬 수 있게된다.

 

temp 가 만약 0이라면 보여줄 노드가 없으므로 공백 문자만 출력한다.

temp가 0이 아니라면, temp의 data를 출력하고, temp의 위치를 한칸 옮기고를 반복한다.

 

마지막에 임의로 동적할당한 temp를 해제해준다.