struct Node;
// 单链表可由头指针唯一确定，在C语言中可以使用‘结构体指针’描述。
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

// 节点
struct Node {
    ElementType Element;
    Position    Next;
};

// 是否是空表
int isEmpty(List l) {
    return l -> Next == NULL;
}

// 是否是链表的末尾
int isLast(Position p) {
    return p -> Next == NULL;
}

// 查找，时间复杂度 O(N)
Position find(ElementType x, List l) {
    Position p;
    p = l -> Next;
    while (p != NULL && p -> Element != x) {
        p = p -> Next;
    }
    return p;
}

// 查找x的前驱元，时间复杂度 O(N)
Position findPrevious(ElementType x, List l) {
    Position p;
    p = l;
    while (p -> Next != NULL && p -> Next -> Element != x) {
        p = p -> Next;
    }
    return p;
}

// 删除，时间复杂度 O(N)
void delete(ElementType x, List l) {
    Position p, tmpCell;
    p = findPrevious(x, l);
    
    if (!isLast(p)) {
        tmpCell = p -> Next;
        p -> Next = tmpCell -> Next;
        free(tmpCell);
    }
}

// 插入，时间复杂度 O(1)
void insert(ElementType x ,List l, Position p) {
    Position tmpCell;
    tmpCell = malloc(sizeof(struct Node));
    
    if (tmpCell == NULL) {
        printf("out of space");
    }
    
    tmpCell -> Element = x;
    tmpCell -> Next = p -> Next;
    p -> Next = tmpCell;
}