链表学习笔记

；我们把链表想象成火车，火车头便是链表的表头，每节车厢就是链表的元素，车厢里载的人和物就是元素的数据域，连接车厢的部件就是元素的指针。由此，我们可以得出链表的一个特点：元素之间前后依赖，串联而成。

还有，我们可以发现，链表的元素不能随机访问。想象下，在高速运行的火车上，如果我们想从车头到达某个车厢，是不是只能挨个车厢走过去，而不能直接到达目标车厢。

另外，除了火车头，每节车厢前面只连接一节车厢；除了最后的车厢，每节车厢后面也只连接一节车厢。这也是链表的特点：元素前面和后面不会出现多个元素相连的情况。

数据结构 = 结构定义 + 结构操作

   //结构定义
typedef struct ListNode {
    int data;//数据域
    struct ListNode *next;//指针域
} ListNode;

typedef struct List {
    ListNode head;
    int length;//这里我们维护了一个链表的长度
} List;
    //初始节点
ListNode *get_new_node(int val) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data = val;
    p->next = NULL;
    return p;
}
	//初始化链表
List *get_link_list() {
    List *l = (List *)malloc(sizeof(ListNode));
    l->head.next = NULL;
    l->length = 0;
    return l;
}
   //插入
int insert(List *l, int ind, int val) {
    if (l == NULL) return 0;
    if (ind < 0 || ind > l->length) return 0;
    ListNode *p = &(l->head), *node = get_new_node(val);
    while (ind--) p = p->next;
    node->next = p->next;
    p->next = node;
    l->length += 1;
    return 1;
}
     //
int erase(List *l, int ind) {
    if (l == NULL) return 0;
    if (ind < 0 || ind >= l->length) return 0;
    ListNode *p = &(l->head), *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = q->next;
    free(q);
    l->length -= 1;
    return 1;
}

void reveser(List *l) {
    ListNode *p = l->head.next, *q;
    l->head.next = NULL;
    while (p) {
        q = p->next;
        p->next = l->head.next;
        l->head.next = p;
        p = q;
    }
    return ;
}
	//遍历（打印）
void output(List *l) {
    printf("List(%d) = [", l->length);
    for (ListNode *p = l->head.next; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL]\n");
    return ;
}
	//释放节点
void clear_node(ListNode *node) {
    if (node == NULL) return ;
    free(node);
    return ;
}
	//释放链表
void clear(List *l) {
    if (l == NULL) return ;
    ListNode *p = l->head.next, *q;
    while (p) {
        q = p->next;
        clear_node(p);
        p = q;
    }
    free(l);
    return ;
}