Linked lists

Lists

Array와 List의 차이

• Array: RAM에서 연속적인 address에 저장된다. 크기가 고정적이며 프로그램 실행 전에 미리 할당해야 하는 경우가 많다.
• List: 각 요소(Node)가 다른 memory에 위치하며 각 요소는 pointer로 연결된다. 크기를 유동적으로 조절 가능하며 삽입 및 삭제 작업이 자유롭다.

List의 node 구성

• Node는 Linked List와 같은 자료 구조에서 사용되는 각 element를 의미한다.
• Node는 value와 pointer로 구성된다.

Structers (구조체)

user가 정의한 data type이다.

sizeof(Structure)는 구조체 내 멤버들의 크기의 합이 아니다

그 이유는structure를 선언할 때 compiler에 의해 Alignment Rules를 따르기 때문이다.

Data alignment (데이터 정렬)

Structure 내 member의 선언 순소에 따라 sizeof(Structure)의 크기가 달라진다.

• 각 member 변수는 자신의 크기의 배수인 memory address에서 시작한다.
• 전체 structure의 크기는 가장 큰 member 변수 크기의 배수로 맞춰준다.

#include <stdio.h>

struct Student {
    char name[20];
    int id;
    float gpa;
    char major[20];
    char gender[10];
    int grade;
};

struct Inefficient {
    char a;   // 1 byte
    int b;    // 4 byte
    short c;  // 2 byte
};

/// 첫 번째 멤버인 'char a'는 1바이트 크기이지만, 'int b'는 4바이트 정렬을 요구하므로 그 뒤에 padding이 추가되어 'b'는 4바이트 주소에 배치된다.
/// 'short c'는 2바이트 크기이고 2바이트 주소에서 시작할 수 있지만, 가장 큰 멤버인 'int'의 정렬 요구사항에 맞추어 전체 구조체 크기는 12바이트가 된다.

struct Efficient {
    int b;    // 4 byte
    char a;   // 1 byte
    short c;  // 2 byte
};

/// 'int'는 4바이트로 정렬되므로 먼저 배치된다.
/// 'char'는 1바이트로 정렬되며, 'short'는 2바이트 주소에서 시작해야 하므로 'char'과 'short'사이의 memory에는 1바이트 padding이 추가된다.

int main(void) {
    // Declare a struct variable
    Student s1 = { "Salah", 2022071066, 3.5, "Computer Science", "Male", 3 };

    // Print the size of the struct Inefficient
    printf("Size of struct Inefficient: %d bytes\n", (int)sizeof(struct Inefficient));

    // Print the size of the struct Efficient
    printf("Size of struct Efficient: %d bytes\n", (int)sizeof(struct Efficient));

    int temp = 0;
}

Structure를 값으로 복사할 때와 포인터로 복사할 때의 차이 & Structure member에 접근하는 법

구조에 변수를 포인터로 선언하면 주소만 복사하면 되므로 메모리가 절약된다. 구조체를 값으로 복사하면 모든 member의 값을 복사하므로 메모리 비용이 든다.

Ex code

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

struct Student {
    char name[20];
    int age;
    float grade;
};

int main() {
    /////////////////////////////////////////////////////////////////////////////////
    // How to access members
    struct Student s1 = { "Salah", 32, 3.8 }; // Declare and initialize struct variable

    // Access members using the dot operator
    printf("Name: %s\n", s1.name);
    printf("Age: %d\n", s1.age);
    printf("Grade: %.2f\n", s1.grade);
    printf("\n");
    printf("\n");

    // Allocate memory dynamically
    struct Student* s2 = (struct Student*)malloc(sizeof(struct Student));
    if (s2 == NULL) { // 메모리 할당 실패 시 예외 처리
        printf("Memory allocation failed!\n");
        return 1;
    }

    // Assign values using the arrow operator
    strcpy_s(s2->name, sizeof(s2->name), "Virgil");
    s2->age = 33;
    s2->grade = 4.5;

    // Access members using the arrow operator
    printf("Name: %s\n", s2->name);
    printf("Age: %d\n", s2->age);
    printf("Grade: %.2f\n", s2->grade);

    printf("\n");
    printf("\n");

    // Access members using the dot operator 2
    printf("* Name: %s\n", (*s2).name);
    printf("* Age: %d\n", (*s2).age);
    printf("* Grade: %.2f\n", (*s2).grade);

    printf("\n");
    printf("\n");

    // Free allocated memory
    free(s2);

    return 0;
}

 

구조체 변수가 값(일반 변수)일 때

• .(dot) operator 사용: s1 자체가 구조체 변수이므로 .연산자로 접근한다.

struct Student s1;
s1.age = 25; // 값에 직접 접근

구조체 변수가 포인터일 때

• ->(arrow) operator: s2는 구조체를 가리키는 포인터이므로 ->연산자로 접근한다.

struct Student* s2 = (struct Student*)malloc(sizeof(struct Student));
s2->age = 30;

Strucure array (구조체 배열)

구조체 배열은 사용자가 정의한 데이터 타입을 배열 형식으로 사용하기 위해 사용된다.

 

구조체 배열은 Static Memory Allocation 또는 Dynamic Memory Allocation 방식으로 사용할 수 있다.

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

struct Student {
    char name[20];
    int age;
    float grade;
};

int main() {
    ////////////////////////////////////////////////////////////////////////////
    // 구조체 배열 - 정적 메모리 할당 (Static Memory Allocation)
    // 선언된 구조체에 array 형식으로 변수명을 설정한 뒤 초기화 해준다.
    struct Student students_static[3] = {
        {"Alice", 20, 3.8},
        {"Bob", 22, 3.5},
        {"Charlie", 21, 3.9}
    };

    // 정적 할당 배열 출력
    printf("Static Memory Allocation:\n");
    for (int i = 0; i < 3; i++) {
        printf("Student %d: Name = %s, Age = %d, Grade = %.2f\n",
               i + 1, students_static[i].name, students_static[i].age, students_static[i].grade);
    }

    ////////////////////////////////////////////////////////////////////////////
    // 구조체 배열 - 동적 메모리 할당 (Dynamic Memory Allocation)
    int n = 3;
    // 동적할당 시 원하는 크기만큼 할당해주면 된다.
    struct Student* students_dynamic = (struct Student*)calloc(n, sizeof(struct Student));

    if (students_dynamic == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }

    // 동적 할당 배열 데이터 입력
    strcpy_s(students_dynamic[0].name, sizeof(students_dynamic[0].name), "Alice"); // 문자열 복사 함수
    students_dynamic[0].age = 20;
    students_dynamic[0].grade = 3.8;

    strcpy_s(students_dynamic[1].name, sizeof(students_dynamic[1].name), "Bob");
    students_dynamic[1].age = 22;
    students_dynamic[1].grade = 3.5;

    strcpy_s(students_dynamic[2].name, sizeof(students_dynamic[2].name), "Charlie");
    students_dynamic[2].age = 21;
    students_dynamic[2].grade = 3.9;

    // 동적 할당 배열 출력
    printf("\nDynamic Memory Allocation:\n");
    for (int i = 0; i < n; i++) {
        printf("Student %d: Name = %s, Age = %d, Grade = %.2f\n",
               i + 1, students_dynamic[i].name, students_dynamic[i].age, students_dynamic[i].grade);
    }

    // 동적 메모리 해제
    free(students_dynamic);

    return 0;
}

Linked lists

각 Node는 자신의 value와 pointer를 가지고 있다. 실제 RAM에서는 memory가 연속적으로 저장된 것이 아니라 pointer를 통해 node들이 연결된다.

Variation of linked lists

Singly linked list

: 오직 다음 node만 가리킬 수 있으며 한 방향으로만 이동할 수 있다.

Doubly linked list

: 이전 node와 다음 node를 가리키는 두 개의 pointer를 가져, 뒤의 node를 접근할 수 있게 돼 접근이 용이하다.

Circular linked list

: 마지막 node가 처음 node를 가리키기 때문에 계속 직진하면 처음 node로 돌아갈 수 있다.

 

※ 오늘의 꿀팁

예외 처리는 중요하다: Device에 구현을 한다면 error 발생 위치릴 찾기 어렵기 때문에, 사소한 것이라도 예외 처리를 철저히 해야 디버깅이 쉬워진다.