链表（1）----单链表基本操作

1、单链表定义

单链表元素定义：

typedef  struct ListElement_t_{
    void  *data;
    struct ListElement_t_  *next;
} ListElement_t;
           

单链表定义：

typedef struct List_t_{
    int  size;
    int  (*match)(const void  *key1, const void  *key2);
    int  (*destroy)(void  *data);
    ListElement_t  *head;
    ListElement_t  *tail;
}  List_t;
           

2、单链表初始化：

int  list_init( List_t *list, int (*match)(const void *key1, const void *key2), int (*destroy)(void *data)){
    list->size = 0;
    list->match = match;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
    return 0;
}
           

3、插入

给定链表元素element， 在element之后插入数据data，需要开辟空间；

异常情况考虑：

（1）是否超过链表的最大容量

            if (list_is_full( list )

                    return OVERFLOW;

（2）申请节点空间是否成功

           if( (new_element = (ListElement_t *)malloc( sizeof( ListElement_t))) == NULL )

                          return  ALLOCA_ERROR;

需要考虑的情况：

（1）若element为NULL，则在头结点插入；

    new_element->next = list->head;

    list->head = new_element;

        同时需要考虑是不是为空链表，如果是则需要维护尾指针；

    if(list_is_empty( list))

        list->tail = new_element;

（2）若element不为NULL，则在头结点之后的某个节点后面插入，需要考虑element为尾节点

new_element->next = element->next;

        element->next = new_element;

        if( list_is_tail( list, element ))

            list->tail = element;

int list_insert_next( List_t *list, ListElement_t *element, const void *data ){
    ListElement_t  *new_element = NULL;
    if( ( new_element = (ListElement_t *)malloc( sizeof( ListElement_t ))) == NULL )
        return ALLOCA_ERROR;
  
    new_element->data = data;
    new_element->next =NULL;
 
    if( element == NULL ){
        if( list_is_empty( list) )
            list->tail = new_element;

        new_element->next = list->head;
        list->head = new_element;
    } else {
        if( list_is_tail( element ))
                list->tail = new_element;    
   
        new_element->next = element->next;
        element->next = new_element;
   }

   list->size++;
   return 0;
}
           

4、删除

删除指定元素element之后的元素。

异常情况：

（1）链表为空

          if( list_is_empty ( list) )

                   return -1;

（2）待删除节点为空，或者说删除尾节点之后的节点

          if( list_is_tail ( element ))

                   return -2;

需要考虑的情况为：

（1）如果element为NULL，则删除头结点。

          *data = list->head->data;

          del_element = list->head;

          list->head = list->head->next;

          需要注意，是否删除的节点为最后一个：

          if( list_size( list ) == 1 )

                  list->tail = NULL;

（2）如果是其他节点，则删除element后面的节点

          *data = element->next->data;

          del_element = element->next;

          element->next = element->next->next;

          需要注意的是如果删除的是尾节点

          if( list_is_tail( list, del_element))

                  list->tail = element;

int list_remove_next( List_t *list, ListElement_t *element, void **data ){
    if( list_is_empty( list ) || list_is_tail(list, element))
        return -1;
    ListElement_t *del_element = NULL;
    if(element == NULL ){
        *data = list->head->data;
        del_element = list->head;
        list->head = list->head->next;
        if( list_size( list ) == 1 )
            list->tail = NULL;
    } else {
        *data = element->next->data;
        del_element = element->next;
        if ( list_is_tail( list, element->next) )
            list->tail = element;
    }
    free(del_element);
    del_element = NULL;
    list->size--;
    return 0;
}
           

5、销毁链表

int list_destroy( List_t *list){
    void *data;
    while( list_size( list ) > 0 ){
        if( (list_remove_next( list, NULL, (void **)&data) == 0) && 
               ( list->destory != NULL ) )
            list->destory( data );
    }
    return 0;
}
           

6、其他函数

inline int  list_is_empty( List_t *list)
{
    return (list->size == 0 ? 1 : 0 );
}

inline int list_is_head( List_t *list, ListElement_t *element)
{
    return ( element == list->head ? 1:0);
}

inline int list_is_tail(List_t *list, ListElement_t *element)
{
    return ( element == list->tail ? 1:0);
}

inline int list_size( List_t *list)
{
    return list->size;
}
           

7、通过遍历求链表长度

int list_size( List_t *list ){
    if( list == NULL )
        return ERROR;

    ListElement_t *pNode = list->head;
    int len = 0;
    while( pNode != NULL ){
        ++len;
        pNode = pNode->next;
    }

    return len;
}
           

int list_size( List_t *list ){

    if( list == NULL )

        return ERROR;

    ListElement_t *pNode = list->head;

    int len = 0;

    while( pNode != NULL ){

        ++len;

        pNode = pNode->next;

    }

    return len;

}

其他相关题目下面以超链接形式给出：

链表面试题合集

1、单链表基本操作

2、双链表基本操作

3、循环单链表基本操作

4、反转单链表

5、查找单链表倒数第K个节点

6、倒序打印链表

7、查找链表中间节点

8、删除链表第K个节点，平均时间复杂度为O(1)

9、判断链表是否有环

10、判断两个单链表是否相交

11、求相交链表的第一个相交节点

12、判断是否有环，并判定是6型环还是0型环

13、判断链表是否有环，并求环入口节点

14、合并两个有序单链表

15、给定链表中间某节点，不遍历链表，将带插入节点插入给定节点之前

16、删除链表重复元素