[1주차 TIL] KnockOn Bootcamp - 연결리스트

🔍 연결 리스트와 리버싱의 관계

💣 왜 리버싱을 할 때 연결 리스트를 알아야 할까?

리버스 엔지니어링 대상이 되는 프로그램(특히 게임, 운영체제, 드라이버 등)은 내부적으로 데이터를 아래처럼 저장하는 경우가 많다

• 실시간으로 변하는 유저 정보 (ex. 체력, 아이템 목록 등) → 연결 리스트 구조
• 객체 관리 시스템 (ex. 몬스터 리스트, 오브젝트 리스트 등) → 연결 리스트 또는 트리
• 윈도우의 메시지 처리 시스템 (메시지 큐 등) → 이중 연결 리스트 사용

👉 이 구조를 모르면:

• 메모리 덤프를 분석할 때 포인터가 왜 연결되어 있는지 파악 못함
• 구조체 간 관계 추적이 어려움
• 동적 구조 탐지가 힘들어 Cheat Engine이나 x64dbg로도 정보 찾기 힘듦

📦 연결 리스트 요약 

종류	설명	특징
단일 연결 리스트	다음 노드를 가리키는 포인터만 있음	메모리 사용 적음, 삽입 삭제 O(n)
이중 연결 리스트	이전, 다음 포인터 모두 있음	양방향 탐색 가능
원형 연결 리스트	마지막 노드가 첫 노드 가리킴	순환 구조, 특정 알고리즘에 유리

 

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

typedef struct dnode {
    int data;
    struct dnode* prev;
    struct dnode* next;
} DNode;

DNode* create_node(int data);
void append_node(DNode** head, int data);
void insert_node(DNode** head, int data, int index);
void delete_node(DNode** head, int index);
void print_forward(DNode* head);
void print_backward(DNode* tail);

#include "doubly_linked_list.h"

DNode* create_node(int data) {
    DNode* node = (DNode*)malloc(sizeof(DNode));
    node->data = data;
    node->prev = node->next = NULL;
    return node;
}

void append_node(DNode** head, int data) {
    DNode* node = create_node(data);
    if (!(*head)) {
        *head = node;
        return;
    }
    DNode* tail = *head;
    while (tail->next) tail = tail->next;
    tail->next = node;
    node->prev = tail;
}

void insert_node(DNode** head, int data, int index) {
    if (index == 0) {
        DNode* node = create_node(data);
        node->next = *head;
        if (*head) (*head)->prev = node;
        *head = node;
        return;
    }
    DNode* cur = *head;
    for (int i = 0; cur && i < index - 1; i++) cur = cur->next;
    if (!cur) return;
    DNode* node = create_node(data);
    node->next = cur->next;
    node->prev = cur;
    if (cur->next) cur->next->prev = node;
    cur->next = node;
}

void delete_node(DNode** head, int index) {
    DNode* cur = *head;
    if (!cur) return;
    if (index == 0) {
        *head = cur->next;
        if (*head) (*head)->prev = NULL;
        free(cur);
        return;
    }
    for (int i = 0; cur && i < index; i++) cur = cur->next;
    if (!cur) return;
    if (cur->prev) cur->prev->next = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    free(cur);
}

void print_forward(DNode* head) {
    while (head) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void print_backward(DNode* tail) {
    while (tail) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("NULL\n");
}

#include "doubly_linked_list.h"

int main() {
    DNode* head = NULL;
    append_node(&head, 10);
    append_node(&head, 20);
    append_node(&head, 30);
    insert_node(&head, 15, 1);
    delete_node(&head, 2);

    printf("정방향 출력: ");
    print_forward(head);

    printf("역방향 출력: ");
    DNode* tail = head;
    while (tail && tail->next) tail = tail->next;
    print_backward(tail);

    return 0;
}