Data Structure - 1

연결 리스트

연결 리스트란? 데이터 필드와 링크 필드가 하나씩 존재하여 서로의 데이터들을 순차적으로 연결해 가는 리스트 형태이다.

이 데이터 구조는 C언어 기준으로 구조체와 포인터를 사용합니다.
코드적인 구현에서 사용되는 함수들은 다음과 같습니다.

• init() : 리스트 초기화
• insert(pos, item) : pos 위치에 새로운 요소 item을 삽입
• delete(pos) : pos 위치에 있는 요소를 삭제
• get_entry(pos) : pos 위치에 있는 요소를 반환
• is_empty() : 리스트가 비어있는지를 검사
• is_full() : 리스트가 가득 차 있는지를 검사
• find(item) : 리스트에 요소 item이 있는지를 살핀다.
• replace(pos, item) : pos 위치를 새로운 요소 item으로 변경
• size() : 리스트안의 요소의 개수를 반환

다음으로 직접 코드를 구현해 보겠습니다.

연결 리스트 구현 - C

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 리스트의 헤드 포인터
Node* head = NULL;

// 노드 추가 함수 (리스트 맨 앞에 삽입)
void insert(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        return;
    }
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

// 노드 삭제 함수 (값으로 삭제)
void delete(int value) {
    Node* current = head;
    Node* previous = NULL;

    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) {
        printf("값 %d 를 가진 노드를 찾을 수 없습니다.\n", value);
        return;
    }

    if (previous == NULL) {
        head = current->next;  // 첫 번째 노드 삭제
    } else {
        previous->next = current->next;
    }

    free(current);
    printf("값 %d 삭제 완료.\n", value);
}

// 리스트 출력 함수
void display() {
    Node* current = head;
    printf("리스트: ");
    while (current != NULL) {
        printf("%d → ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 메모리 해제 함수
void freeList() {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    head = NULL;
}

// 테스트용 main 함수
int main() {
    
}

순환 - 재귀호출

재귀호출이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하는 형태이다.

이러한 구조는 즉, 어떠한 조건이 될때까지 자기 자신의 함수를 호출하여 반복적인 또는 규칙적인 일을 수행할 때 많이 사용합니다.
→ 이때 재귀호출에 사용되는 함수를 재귀함수라고 말합니다.
대표적인 예시로 팩토리얼(!)이 있습니다.

팩토리얼 계산 문제 - C

팩토리얼 계산 방법 : $n! → n \times (n-1) \times (n-2) \times \ldots \times 1$

#include <stdio.h>

int fac(n){
	if(n == 1) return 1;
	else return n * fac(n-1);
}

int main(){
	int n;
	scanf("%d",&n);
	
	printf("%d! = %d",n,fac(n);
}

이 재귀호출의 코드는 어디에 사용하는지에 따라 달라집니다!!!
특정 값을 알고 싶을 때 이전에 구했던 값이나 알고 있는 값을 공식을 이용해 규칙적인 연산을 필요로 하는 수학적인 개념에서 많이 사용됩니다.