#include <stdio.h>
#include <stdlib.h>
//定义链接节点结构 包含了节点的数据域、前后指针域
typedef struct node {
    char *data;
    struct node *next;
    struct node *prior;
} node;
//定义链表结构 包含链表头节点指针、链表长度
typedef struct {
    node *head;
    int len;
}LinkedList;
//初始化双向链表 包括生成表头，初始化表长度
LinkedList * init() {
    LinkedList *L = NULL;
    L = (LinkedList *)malloc(sizeof(LinkedList));
    node *head =  (node *)malloc(sizeof(node));
    head->next = head;
    head->prior= head;
    L->head = head;
    L->len = 0;
    return L;
}
//向链表头部插入数据
void add_to_head(LinkedList *L, char *data) {
    node *dnode = (node *)malloc(sizeof(node));
    dnode->data = data;
    dnode->next = L->head->next;
    dnode->prior= L->head;
    L->head->next->prior = dnode;
    L->head->next = dnode;
    L->len++;
}
//向链表尾部插入数据
void add_to_tail(LinkedList *L, char *data) {
    node *dnode = (node *)malloc(sizeof(node));
    dnode->data = data;
    dnode->next = L->head;
    dnode->prior= L->head->prior;
    dnode->prior->next = dnode;
    L->head->prior = dnode;
    L->len++;
}
//从链表中删除下标为index的节点，index从0开始。
//index在链表前半段时从头部遍历 index在链表后半段时从头部逆向遍历
void del_data(LinkedList *L, int index) {
    if(index > L->len) {
        printf("index error");
        return;
    }
    node * node_tmp = NULL;
    int i=0;
    if(index < L->len/2) {
        node_tmp = L->head->next;
        for(i=0; i<index; i++) {
            node_tmp = node_tmp->next;
        }
    } else {
        node_tmp = L->head->prior;
        for(i=0; i<L->len-index; i++) {
            node_tmp = node_tmp->prior;
        }
    }
    node_tmp->prior->next = node_tmp->next;
    node_tmp->next->prior = node_tmp->prior;
    free(node_tmp);
    L->len--;
}
//遍历并打印链表（正向）
void foreach(LinkedList *L) {
    node *n = L->head->next;
    while(n != L->head) {
        printf("%s\n", n->data);
        n = n->next;
    }
}
//遍历并打印链表（逆向）
void rforeach(LinkedList *L) {
    node *n = L->head->prior;
    while(n != L->head) {
        printf("%s\n", n->data);
        n = n->prior;
    }
}
int main() {
    LinkedList *L;
    L = init();
    add_to_tail(L, "C");
    add_to_tail(L, "C++");
    add_to_tail(L, "C#");
    add_to_tail(L, "java");
    add_to_tail(L, "php");
    add_to_tail(L, "python");
    add_to_tail(L, "ruby");
    add_to_tail(L, "object-c");
    printf("打印链表\n");
    foreach(L);
    printf("删除index=2的元素 打印链表\n");
    del_data(L, 2);
    foreach(L);
    printf("逆向打印链表\n");
    rforeach(L);
    return;
}