Singly Linked List

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

struct node {
    int data;
    struct node *next;
};

static struct node *node_at(struct node *head, size_t index, size_t *steps) {
    *steps = 0;
    while (head != NULL && *steps < index) {
        head = head->next;
        ++*steps;
    }
    return head;
}

int main(void) {
    struct node third = {30, NULL};
    struct node second = {20, &third};
    struct node first = {10, &second};
    size_t steps = 0;
    struct node *found = node_at(&first, 2, &steps);
    assert(found == &third && steps == 2);
    printf("인덱스 2: %d, 이동: %zu\n", found->data, steps);

    struct node added = {15, first.next};
    first.next = &added;
    for (struct node *p = &first; p != NULL; p = p->next) {
        printf("%d%s", p->data, p->next == NULL ? "\n" : " -> ");
    }
    struct node *removed = first.next;
    first.next = removed->next;
    removed->next = NULL;
    assert(first.next == &second);
    printf("삭제 후 첫 노드의 다음 값: %d\n", first.next->data);

    found = node_at(&first, 3, &steps);
    printf("범위 밖: %s, 이동: %zu\n", found == NULL ? "없음" : "있음", steps);
    assert(found == NULL && steps == 3);
    found = node_at(NULL, 0, &steps);
    assert(found == NULL && steps == 0);
    return 0;
}

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

struct Node {
    int data;
    struct Node *next;
};

static bool insert_sorted(struct Node **head, int value,
                          void *(*allocate)(size_t)) {
    struct Node *new_node = allocate(sizeof *new_node);
    if (new_node == NULL) {
        return false;
    }
    new_node->data = value;

    struct Node *prev = NULL;
    struct Node *cur = *head;
    while (cur != NULL && cur->data < value) {
        prev = cur;
        cur = cur->next;
    }

    new_node->next = cur;
    if (prev == NULL) {
        *head = new_node;
    } else {
        prev->next = new_node;
    }
    return true;
}

static void *fail_allocate(size_t size) {
    (void)size;
    return NULL;
}

static void clear(struct Node **head) {
    while (*head != NULL) {
        struct Node *removed = *head;
        *head = removed->next;
        free(removed);
    }
}

static void add(struct Node **head, int value) {
    if (!insert_sorted(head, value, malloc)) {
        fputs("allocation failed\n", stderr);
        clear(head);
        exit(EXIT_FAILURE);
    }
}

static void check_and_print(const char *label, const struct Node *head,
                            const int *expected, size_t count) {
    printf("%s: ", label);
    for (size_t i = 0; i < count; ++i) {
        assert(head != NULL && head->data == expected[i]);
        printf("%d%s", head->data, i + 1 == count ? "\n" : " -> ");
        head = head->next;
    }
    assert(head == NULL);
}

int main(void) {
    struct Node *head = NULL;
    add(&head, 1);
    check_and_print("empty + 1", head, (int[]){1}, 1);

    const int rest[] = {4, 7, 10};
    for (size_t i = 0; i < sizeof rest / sizeof rest[0]; ++i) {
        add(&head, rest[i]);
    }
    struct Node *old_four = head->next;
    check_and_print("start", head, (int[]){1, 4, 7, 10}, 4);

    add(&head, 6);
    check_and_print("middle + 6", head, (int[]){1, 4, 6, 7, 10}, 5);
    add(&head, 0);
    check_and_print("front + 0", head, (int[]){0, 1, 4, 6, 7, 10}, 6);
    add(&head, 12);
    check_and_print("tail + 12", head, (int[]){0, 1, 4, 6, 7, 10, 12}, 7);
    add(&head, 4);
    check_and_print("duplicate + 4", head, (int[]){0, 1, 4, 4, 6, 7, 10, 12}, 8);
    struct Node *new_four = head->next->next;
    assert(new_four != old_four && new_four->next == old_four);
    puts("duplicate order: new 4 before old 4");

    struct Node *saved[8];
    struct Node *cur = head;
    for (size_t i = 0; i < 8; ++i) {
        assert(cur != NULL);
        saved[i] = cur;
        cur = cur->next;
    }
    assert(cur == NULL);
    bool inserted = insert_sorted(&head, 5, fail_allocate);
    assert(!inserted);
    cur = head;
    for (size_t i = 0; i < 8; ++i) {
        assert(cur == saved[i]);
        cur = cur->next;
    }
    assert(cur == NULL);
    check_and_print("failed + 5", head, (int[]){0, 1, 4, 4, 6, 7, 10, 12}, 8);
    puts("allocation failure: same nodes and links");

    struct Node *empty = NULL;
    inserted = insert_sorted(&empty, 9, fail_allocate);
    assert(!inserted && empty == NULL);
    puts("empty allocation failure: still empty");

    clear(&head);
    assert(head == NULL);
    add(&empty, 9);
    struct Node *old_nine = empty;
    add(&empty, 9);
    check_and_print("equal minimum + 9", empty, (int[]){9, 9}, 2);
    assert(empty != old_nine && empty->next == old_nine);
    clear(&empty);
    assert(empty == NULL);
    puts("clear: both lists empty");
    return 0;
}

empty + 1: 1
start: 1 -> 4 -> 7 -> 10
middle + 6: 1 -> 4 -> 6 -> 7 -> 10
front + 0: 0 -> 1 -> 4 -> 6 -> 7 -> 10
tail + 12: 0 -> 1 -> 4 -> 6 -> 7 -> 10 -> 12
duplicate + 4: 0 -> 1 -> 4 -> 4 -> 6 -> 7 -> 10 -> 12
duplicate order: new 4 before old 4
failed + 5: 0 -> 1 -> 4 -> 4 -> 6 -> 7 -> 10 -> 12
allocation failure: same nodes and links
empty allocation failure: still empty
equal minimum + 9: 9 -> 9
clear: both lists empty

from typing import Optional


class Node:
    def __init__(self, value: int, next: Optional["Node"] = None):
        self.value = value
        self.next = next


def move_max_to_front(head: Optional[Node]) -> Optional[Node]:
    if head is None or head.next is None:
        return head

    max_node = head
    max_prev = None
    prev = head
    cur = head.next

    while cur is not None:
        if cur.value > max_node.value:
            max_node = cur
            max_prev = prev
        prev = cur
        cur = cur.next

    if max_prev is None:
        return head

    max_prev.next = max_node.next
    max_node.next = head
    return max_node


def collect(head: Optional[Node]) -> list[Node]:
    nodes = []
    seen = set()
    while head is not None:
        assert id(head) not in seen, "cycle in result"
        seen.add(id(head))
        nodes.append(head)
        head = head.next
    return nodes


cases = ([], [7], [9, 3, 2], [3, 8, 2, 7], [3, 2, 7],
         [3, 8, 2, 8, 7], [8, 3, 8], [-5, -2, -9])
for values in cases:
    nodes = [Node(value) for value in values]
    for left, right in zip(nodes, nodes[1:]):
        left.next = right
    head = nodes[0] if nodes else None
    original_head = head
    old_links = [node.next for node in nodes]
    picked_index = values.index(max(values)) if values else None
    picked = nodes[picked_index] if picked_index is not None else None
    expected = ([picked] + nodes[:picked_index] + nodes[picked_index + 1:]
                if picked_index is not None else [])

    head = move_max_to_front(head)
    actual = collect(head)
    same_nodes = len(actual) == len(expected) and all(
        left is right for left, right in zip(actual, expected)
    )
    same_values = all(node.value == value for node, value in zip(nodes, values))
    assert same_nodes and same_values
    assert len({id(node) for node in actual}) == len(nodes)
    assert head is picked

    moved = picked_index is not None and picked_index > 0
    changed_links = sum(node.next is not old for node, old in zip(nodes, old_links))
    assert changed_links == (2 if moved else 0)
    for i, node in enumerate(nodes):
        if moved and i == picked_index - 1:
            expected_next = old_links[picked_index]
        elif moved and node is picked:
            expected_next = original_head
        else:
            expected_next = old_links[i]
        assert node.next is expected_next

    print(f"{values} -> {[node.value for node in actual]}; "
          f"picked_index={picked_index}; same_nodes={same_nodes}; "
          f"same_values={same_values}; changed_links={changed_links}")

[] -> []; picked_index=None; same_nodes=True; same_values=True; changed_links=0
[7] -> [7]; picked_index=0; same_nodes=True; same_values=True; changed_links=0
[9, 3, 2] -> [9, 3, 2]; picked_index=0; same_nodes=True; same_values=True; changed_links=0
[3, 8, 2, 7] -> [8, 3, 2, 7]; picked_index=1; same_nodes=True; same_values=True; changed_links=2
[3, 2, 7] -> [7, 3, 2]; picked_index=2; same_nodes=True; same_values=True; changed_links=2
[3, 8, 2, 8, 7] -> [8, 3, 2, 8, 7]; picked_index=1; same_nodes=True; same_values=True; changed_links=2
[8, 3, 8] -> [8, 3, 8]; picked_index=0; same_nodes=True; same_values=True; changed_links=0
[-5, -2, -9] -> [-2, -5, -9]; picked_index=1; same_nodes=True; same_values=True; changed_links=2