자료구조 - 리스트

< 리스트란? >

리스트는 데이터를 일렬로 저장하는 자료구조
ex)

< 초기 가정 >

전역변수
int n;
node H, T;

< 노드 구조체 >

//노드 구조체
typedef struct node {
    char elem;
    struct node *prev, *next;
} node;

< 리스트 초기화 >

// 리스트 초기화
void initialize() {
    // 동적할당
    H = (node *)malloc(sizeof(node));
    T = (node *)malloc(sizeof(node));
    // 헤더와 트레일러를 연결
    H->next = T;
    T->prev = H;
    H->prev = NULL;
    T->next = NULL;
    // 리스트 크기 0으로 초기화
    n = 0;
}

node **H는 포인터를 가리키는 포인터 (즉, 포인터 자체를 변경할 수 있음)

< 노드 삽입 >

// 삽입
void add(node *list, int r, char e) {
    // 범위 확인
    if (r < 1 || r > n + 1) {
        printf("invalid position\n");
        return;
    }
    //삽입할 위치까지 이동
    node *p = list;
    for (int i = 0; i < r; i++) p = p->next;
    //노드 삽입
    addNodeBefore(p, e);
    //리스트 크기 1증가
    n++;
}
// p 노드 앞에 삽입
void addNodeBefore(node *p, char e) {
    // 새로운 노드 q 만들기
    node *q = (node *)malloc(sizeof(node));
    // 새로운 노드 q 연결
    q->elem = e;
    q->prev = p->prev;
    q->next = p;
    // 기존 노드 p 재연결
    p->prev->next = q;
    p->prev = q;
}

< 노드 삭제 >

// 삭제
void delete(node *H, int r) {
    //범위 확인
    if (r < 1 || r > n) {
        printf("invalid position\n");
        return;
    }
    //삭제할 위치까지 이동
    node *p = H;
    for (int i = 0; i < r; i++) p = p->next;
    // 노드 삭제
    removeNode(p);
    //리스트 크기 1 감소
    n--;
}
// 노드 삭제
void removeNode(node *p) {
    // 삭제할 노드의 양옆 노드를 서로 연결
    if (p->prev != NULL) p->prev->next = p->next;
    if (p->next != NULL) p->next->prev = p->prev;
    // 삭제할 노드 동적할당 해제
    free(p);
}

< 특정 노드 값 get >

// r번째 노드 값 출력
void get(node *H, int r) {
    //범위 확인
    if (r < 1 || r > n) {
        printf("invalid position\n");
        return;
    }
    //출력할 노드 위치까지 이동
    node *p = H;
    for (int i = 0; i < r; i++) p = p->next;
    // 출력
    printf("%c\n", p->elem);
}

< 전체 리스트 출력 (순회)>

// 전체 리스트 출력
void print(node *H) {
    // 트레일러 전까지 리스트를 순회하며 출력
    node *p = H->next;
    while (p != T) {
        printf("%c", p->elem);
        p = p->next;
    }
    printf("\n");
}

< 리스트 동적할당 해제 (재귀 ver)>

void putNode(node *p) {
    if (p != NULL) {
        putNode(p->next);
        free(p);
    }
}

< 리스트 동적할당 해제 (비재귀 ver)>

void freeList(node *H) {
    node *cur = H;
    while (cur != NULL) {
        node *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
}

• main에 scanf(" %c",&mode);라고 써야함
  -> 공백 문자(' ')를 넣는 이유는 버퍼에 남아 있는 공백 문자(특히 개행 문자 \n)를 무시하기 위해서...