单链表不带头标准c语言实现

比眉伴天荒 2022-05-08 05:20 204阅读 0赞

链表是一种物理[存储单元][Link 1]上非连续、非顺序的[存储结构][Link 2]，[数据元素][Link 3]的逻辑顺序是通过链表中的[指针][Link 4]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素][Link 5]的数据域，另一个是存储下一个结点地址的[指针][Link 4]域。 相比于[线性表][Link 6][顺序结构][Link 7]，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服[数组][Link 8]链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了[数组][Link 8]随机读取的优点，同时链表由于增加了结点的[指针][Link 4]域，空间开销比较大。链表最明显的好处就是，常规[数组][Link 8]排列关联项目的方式可能不同于这些数据项目在[记忆体][Link 9]或[磁盘][Link 10]上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的[节点][Link 11]，但是不允许[随机存取][Link 12]。链表有很多种不同的类型：[单向链表][Link 13]，[双向链表][Link 14]以及[循环链表][Link 15]。

下面给出不带头的单链表标准实现：

定义节点：

typedef struct node 
    { 
        int data;
        struct node * next;
    }Node;

尾插：

void pushBackList(Node ** list, int data) 
    { 
        Node * head = *list;
        Node * newNode = (Node *)malloc(sizeof(Node));//申请空间
        newNode->data = data; newNode->next = NULL;
        if(*list == NULL)//为空
            *list = newNode;
        else//非空
        {
            while(head ->next != NULL)
                head = head->next;
            head->next = newNode;
        }
    }

插入：

int insertList(Node ** list, int index, int data) 
    {
        int n;
        int size = sizeList(*list); 
        Node * head = *list; 
        Node * newNode, * temp;
        if(index<0 || index>size) return 0;//非法
        newNode = (Node *)malloc(sizeof(Node)); //创建新节点
        newNode->data = data; 
        newNode->next = NULL;
        if(index == 0) //头插
        {
            newNode->next = head; 
            *list = newNode; 
            return 1; 
        }
        for(n=1; n<index; n++) //非头插
            head = head->next;
        if(index != size) 
            newNode->next = head->next; 
        //链表尾部next不需指定
        head->next = newNode; 
        return 1;
    }

按值删除：

void deleteList(Node ** list, int data) 
    { 
        Node * head = *list; Node * temp; 
        while(head->next!=NULL) 
        { 
            if(head->next->data != data) 
            { 
                head=head->next; 
                continue; 
            } 
            temp = head->next;
            if(head->next->next == NULL) //尾节点删除
                head->next = NULL; 
            else 
                head->next = temp->next; 
            free(temp);
        }    
        head = *list; 
        if(head->data == data) //头结点删除
        { 
            temp = head; 
            *list = head->next; 
            head = head->next; 
            free(temp); 
        }
    }

打印：

void printList(Node * head) 
    { 
        Node * temp = head; 
        for(; temp != NULL; temp=temp->next) 
            printf("%d ", temp->data); 
        printf("\n"); 
    }

清空：

void freeList(Node ** list) 
    { 
        Node * head = *list; 
        Node * temp = NULL; 
        while(head != NULL) //依次释放
        { 
            temp = head; 
            head = head->next; 
            free(temp); 
        } 
        *list = NULL; //置空
    }

别的也没啥了，都是基本操作

有些代码要分情况，很麻烦，可读性较强吧

看我压缩代码：[https://blog.csdn.net/hebtu666/article/details/81261043][https_blog.csdn.net_hebtu666_article_details_81261043]

[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83/8727749
[Link 2]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84/350782
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 4]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304
[Link 5]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[Link 6]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8/3228081
[Link 7]: https://baike.baidu.com/item/%E9%A1%BA%E5%BA%8F%E7%BB%93%E6%9E%84/9845234
[Link 8]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[Link 9]: https://baike.baidu.com/item/%E8%AE%B0%E5%BF%86%E4%BD%93/3029693
[Link 10]: https://baike.baidu.com/item/%E7%A3%81%E7%9B%98/2842227
[Link 11]: https://baike.baidu.com/item/%E8%8A%82%E7%82%B9/865052
[Link 12]: https://baike.baidu.com/item/%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96/4610937
[Link 13]: https://baike.baidu.com/item/%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8/8671935
[Link 14]: https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2968731
[Link 15]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/3228465
[https_blog.csdn.net_hebtu666_article_details_81261043]: https://blog.csdn.net/hebtu666/article/details/81261043