链表 linked list

定义

就是一些包含数据的独立数据结构的集合。链表中每个节点通过链或指针连接在一起。程序通过指针访问链表中节点。

单链表

每个节点包含一个指向下一个节点的指针，链表最后一个节点的指针字段的值为NULL，提示链表后不再有其他节点。

• 通过链表第一个节点可以访问剩余所有的节点。
• 根指针（root pointer）指向链表的第一个节点。

typedef struct NODE{
    struct NODE *link;
    int value;
}Node；

单链表的插入

将新节点插入到一个有序的单链表中

• 插入函数需要检查是否到达链表的尾部
• root是一个指针
• 为新节点分配内存时是否成功

#define FALSE 0
#define TRUE 1

int sll_insert(Node **linkp,int new_value){
    Node *current;
    Mode *new;
    
    //寻找正确插入位置：按序访问链表
    while((current = *linkp) != NULL && current->value < new_value)
    linkp = &current -> link;
    
    // 为新节点分配内存
    new = (Node *)malloc(sizeof(Node));
    
    // 如果内存分配失败返回false
    if(new == NULL)
    return FALSE;
    
    // 将新值存到新节点中
    new->value = new_value;
    new->link = current;
    
    return TRUE；
}

双链表

每个节点都包含两个指针：指向前一个节点的指针和指向后一个节点的指针

typedef struct NODE{
    struct NODE *fwd;
    struct NODE *bwd;
    int value;
}Node；

根节点

• 根节点fwd字段指向链表的第一个节点
• 根节点bwd字段指向链表的最后一个节点
• 如果量表为空，则两个字段都为NULL

双链表的插入

编写一个当插入值原先不存在于链表中才插入的插入函数

将节点插入到链表中，可能出现的四种情况

1. 新值插入到链表的中间位置
2. 新值插入到链表的起始位置
3. 新值插入到链表的结束位置
4. 原链表为空的情况下，插入的位置既是起始位置又是结束位置

int dll_insert(Node *rootp,int value){
    Node *this;
    Node *next;
    Node *new;
    
    for(this = rootp;(next = this->fwd) != NULL;this = next){
        if(next->value == value)
        return 0;
        if(next->value>value)
        break;
    }
    new = (Node *)malloc(sizeof(node));
    
    if(new == NULL)
    return -1;
    
    new->value = value;
    
    newnode->fwd = next;
    this->fwd = new;
    
    if(this != rootp)
    new->bwd = this;
    else
    new->bwd = NULL;
    
    if(next != NULL)
    next->bwd = new;
    else
    rootp->bwd - new;
    
    return 1;
}