헤드 삽입을 통한 리스트 생성

머리에서부터 데이터를 입력받아 새로운 노드를 앞쪽에 추가하는 방식이다. 이 방법은 입력 순서와 출력 순서가 반대가 된다.

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

typedef int DataType;
typedef struct ListNode {
    DataType value;
    struct ListNode *next;
} ListNode, *List;

void create_head_insert(List &head) {
    head = (List)malloc(sizeof(ListNode));
    head->next = NULL;

    DataType input;
    scanf("%d", &input);

    ListNode *new_node;
    while (input != 9999) {
        new_node = (List)malloc(sizeof(ListNode));
        new_node->value = input;
        new_node->next = head->next;
        head->next = new_node;
        scanf("%d", &input);
    }
}

void display_list(List head) {
    head = head->next;
    while (head != NULL) {
        printf("%3d", head->value);
        head = head->next;
    }
    printf("\n");
}

int main() {
    List list;
    create_head_insert(list);
    display_list(list);
    return 0;
}

테일 삽입을 통한 리스트 생성

꼬리 포인터를 유지하여 항상 마지막 위치를 가리키도록 한다. 입력 순서와 출력 순서가 동일하다.

void create_tail_insert(List &head) {
    head = (List)malloc(sizeof(ListNode));
    head->next = NULL;

    DataType input;
    scanf("%d", &input);

    ListNode *new_node, *tail = head;
    while (input != 9999) {
        new_node = (List)malloc(sizeof(ListNode));
        new_node->value = input;
        tail->next = new_node;
        tail = new_node;
        scanf("%d", &input);
    }
    tail->next = NULL;
}

위치 기반 및 값 기반 검색

연결 리스트에서 특정 위치나 값을 가진 노드를 찾는다. 유효성 검사 필수.

List search_by_position(List head, int index) {
    if (index < 0) return NULL;

    List current = head->next;
    int pos = 0;
    while (current != NULL && pos < index) {
        current = current->next;
        pos++;
    }
    return current;
}

List search_by_value(List head, DataType target) {
    List current = head->next;
    while (current != NULL) {
        if (current->value == target) return current;
        current = current->next;
    }
    return NULL;
}

지정 위치에 요소 삽입

기존의 위치 탐색 함수를 활용해 특정 위치에 새 노드를 삽입한다. 인덱스는 1부터 시작.

bool insert_at_position(List head, int pos, DataType val) {
    List prev = search_by_position(head, pos - 1);
    if (prev == NULL) return false;

    List new_node = (List)malloc(sizeof(ListNode));
    new_node->value = val;
    new_node->next = prev->next;
    prev->next = new_node;
    return true;
}