C언어로 만든 연결 리스트(Linked List)

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

/*

push
append
sort
print
clear
reverse
search
insert

delete - later

*/

typedef struct Node {
    char *data;
    struct Node *next;
} Node;


void exit_if_null(void *ptr, char *msg) {
    if (!ptr) {
        printf("unexpected null pointer: %s\n", msg);
        exit(EXIT_FAILURE);
    }
}

Node *createNode(char *data) { //create a node and return a pointer to the node.

    Node *p = malloc(sizeof(Node));
    exit_if_null(p, "Node memory allocation error\n");

    p->data = malloc(strlen(data) + 1);
    exit_if_null(p->data, "Node string memory allocation error\n");

    strcpy(p->data, data);
    p->next = NULL; // This will be set on insertion
    return p;
}

Node* swap(Node* ptr1, Node* ptr2) { 
    Node* tmp = ptr2->next; 
    ptr2->next = ptr1; 
    ptr1->next = tmp; 
    return ptr2; 
} 
  
int bubbleSort(Node** headRef) { 

    Node** h; 
    int i, j, swapped; 
    
    int count = 0;
    for(Node **p = headRef; *p; p = &(*p)->next) { //count number of nodes
        count++;
    }

    for (i = 0; i <= count; i++) { 
  
        h = headRef; 
        swapped = 0; 
  
        for (j = 0; j < count - i - 1; j++) { 
  
            Node* p1 = *h; 
            Node* p2 = p1->next; 
  
            if ( strcmp(p1->data, p2->data) > 0 ) {
  
                *h = swap(p1, p2); 
                swapped = 1; 
            } 
  
            h = &(*h)->next; 
        } 
  
        if (swapped == 0) 
            break; 
    } 
} 

void prependNode(Node **headRef, Node *newNode) {

    newNode->next = *headRef;
    *headRef = newNode;
}


void append(Node **headRef, Node *newNode) {

    Node **tracer = headRef;
    while (*tracer) {
        tracer = &(*tracer)->next;
    }
    newNode->next = *tracer;
    *tracer = newNode;
}

void insertN(Node **headRef, int pos, Node *newNode) {

    Node **tracer = headRef;
    int i = 1;
    
    if( pos < 1 ) {
        printf("index can't be less than 1.\n");
        exit(EXIT_FAILURE);
    }

    if( pos == 1 || *headRef == NULL ) {
        newNode->next = *headRef;
        *headRef = newNode;
        return;
    }

    while (*tracer != NULL && i < pos ) {
        tracer = &(*tracer)->next; 
        i++;
    }

    if( pos > i  ) {
        printf("index cant't be greater than %d\n", i );
        exit(EXIT_FAILURE);
    }

    newNode->next = *tracer;
    *tracer = newNode;
}


Node *deleteN(Node *head, int LOC) { int i;
   Node *p, *tmp;
   
   if(LOC==1) { tmp=head; head = head->next; free(tmp); return head; }
   
   for(p=head, i=1; p!=NULL && i < LOC; p=p->next, i++)
       tmp=p;
       
   tmp->next = p->next;
   free(p);
   
   return head;
}

void insert_after(Node *node_to_insert_after, Node * newnode) {

    newnode->next = node_to_insert_after->next;
    node_to_insert_after->next = newnode;
}

void clear(Node **headRef) {

    Node *temp;
    while (*headRef != NULL) {
        temp = *headRef;
        *headRef = (*headRef)->next;
        free(temp);
    }
    return;
}


void print(Node **headRef) {

    Node **tracer = headRef;
    while (*tracer) {
        puts( (*tracer)->data );
        tracer = &(*tracer)->next;
    }
    
}

Node *search(Node **headRef, char *str) {

    for(Node **tracer = headRef; *tracer ; tracer = &(*tracer)->next) {
        if (strcmp( (*tracer)->data, str) == 0 ) return *tracer;
    }

    return NULL;
}

void reverse(Node** headRef) {

    Node* current = *headRef;
    Node* next;

    while (current->next != NULL) {
        next = current->next;
        current->next = next->next;
        next->next = (*headRef);
        *headRef = next;
    }
}

int main() {
    
    Node *head = NULL; // declare the list head and initialize it to NULL
    
    insertN(&head, 1, createNode("kiwi"));  // insert at the head node
    prependNode(&head, createNode("papaya"));
    prependNode(&head, createNode("orange"));
    prependNode(&head, createNode("banana"));
    prependNode(&head, createNode("banana"));
    prependNode(&head, createNode("mango"));
    prependNode(&head, createNode("apple"));

    head = deleteN(head, 3);

    insertN(&head, 7, createNode("strawberry")); // 3rd node is strawberry. (Note that head is 1st node here.)
    insertN(&head, 1, createNode("blueberry"));  // insert at the head node
    
    Node *p = search(&head, "orange");

    if( p != NULL ) {
       insert_after( p, createNode("grapefruit"));
    }

    puts("\n***** before sort *****\n");
    print(&head);

    bubbleSort(&head); 
    puts("\n***** after sort *****\n");
    print(&head);

    reverse(&head); 
    puts("\n***** after reverse *****\n");
    print(&head);

    clear(&head);

    return 0;
}

/*
The arrow operator can then be used to indirectly access the member variable. The following are equivalent:

tracer = &(*tracer)->next;
tracer = &(*(*tracer)).next;
tracer = &(**tracer).next;
*/