/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *LIST; 
typedef struct node *position;

/* node，节点 */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 * 操作
 */
LIST init_list(void);
void delete_list(LIST);
int is_null(LIST);
void insert_node(position, int);
void delete_node(LIST, position);
position find_last(LIST);
position find_value(LIST, int);
position find_previous(LIST, position);
void print_list(LIST);

/* for testing purpose */
void main()
{
    LIST L;
    position np;
    
    int i;
    /* elements to be put into the list */
    int a[] = {1, 3, 5, 7, 9};

    /* initiate a list */
    L = init_list();
    print_list(L);

    /* insert nodes. Insert just after head node */
    for (i=4; i>=0; i--) {
        insert_node(L, a[i]);
    }
    print_list(L);

    /* delete first node with value 5 */
    np = find_value(L, 5);
    delete_node(L, np);
    print_list(L);

    /* delete list */
    delete_list(L);

    /* initiate a list */
    L = init_list();
    print_list(L);

    /* insert nodes. Insert just after head node */
    for (i=4; i>=0; i--) {
        insert_node(L, a[i]);
    }
    print_list(L);

    /* delete list */
    delete_list(L);
}

/*
 * Traverse the list and print each element
 * 打印表
 */
void print_list(LIST L)
{
    position np;
    if(is_null(L)) {
        printf("Empty List\n\n");
        return;
    }

    np = L;
    while(np->next != NULL) { 
        np = np->next;
        printf("%p: %d \n", np, np->element);
    }
    printf("\n");

}

/*
 * Initialize a linked list. This list has a head node
 * head node doesn‘t store valid element value
 * 创建表
 */
LIST init_list(void) 
{
    LIST L;
    L = (position) malloc(sizeof(struct node));
    L->next = NULL;
    return L;
}

/*
 * Delete all nodes in a list
 * 删除表
 */
void delete_list(LIST L)
{
    position np, next;

    np   = L;
    do {
        next = np->next;
        free(np);
        np   = next;
    } while(next != NULL);    
}

/*
 * if a list only has head node, then the list is null.
 * 判断表是否为空
 */
int is_null(LIST L) 
{
    return ((L->next)==NULL);
}

/*
 * insert a node after position np
 * 在np节点之后，插入节点
 */
void insert_node(position np, int value) 
{
    position nodeAddr;
    
    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = value;
    nodeAddr->next = np->next;
    np->next = nodeAddr;    
}

/*
 * delete node at position np
 * 删除np节点
 */
void delete_node(LIST L, position np)
{
    position previous, next;
    next     = np->next;
    previous = find_previous(L, np);
    if(previous != NULL) {
        previous->next = next;
        free(np); 
    }
    else {
        printf("Error: np not in the list");
    }
}

/*
 * find the last node of the list
 * 寻找表的最后一个节点
 */
position find_last(LIST L)
{
    position np;
    np = L;
    while(np->next != NULL) {
        np = np->next;
    }
    return np;
}

/*
 * This function serves for 2 purposes:
 * 1. find previous node 
 * 2. return NULL if the position isn‘t in the list
 * 寻找npTarget节点前面的节点
 */
position find_previous(LIST L, position npTarget)
{
    position np;
    np = L;
    while (np->next != NULL) {
        if (np->next == npTarget) return np; 
        np = np->next;
    } 
    return NULL;
}

/*
 * find the first node with specific value
 * 查询
 */
position find_value(LIST L, int value) 
{
    position np;
    np = L;
    while (np->next != NULL) {
        np = np->next;
        if (np->element == value) return np;
    }
    return NULL;
}