无头单链表实现

本文主要是介绍无头单链表实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表的结构是一个一个节点，每个节点中有指向下一个节点的指针域和自身的值域，

typedef int Datatype;
typedef struct SlistNode {Datatype data;struct SlistNode* next;
}Node;

初始化操作
这个head是指向链表的指针，链表作为线性结构一定有起始位置，这样才能找到下一个节点的位置。初始化那就让这个指针指向空。

void SlistInit(Node** head) {assert(head);*head = NULL;
}

创建一个节点
现在创建的链表是空的，定义这个方法可以给链表中添加节点，首先开辟一个空间，空间空间里有两个字段，一个是值域一个指向下一个节点的指针域。一个单独的节点还没有形成链的结构，让它的next指向空。

Node* BuySlistNode(Datatype data) {Node* node = (Node*)malloc(sizeof(Node));if (NULL == node) {exit(0);return NULL;}node->data = data;node->next = NULL;return node;
}

尾插
尾插首先判断链表是不是空链表，如果是空的那就需要先种一个节点，直接让head指向它，它也就成连链表的第一个节点了。不为空的话，找最后一个节点，再种一个节点，让最后一个节点的指针域指向它就行了。链表不为空的时候，不能改变head的指向，定义一个新指针来完成找节点的动作。

void Slistpushback(Node** head, Datatype data) {assert(head);if (*head == NULL) {//如果head指向空，说明链表是空链表。种一个节点*head = BuySlistNode(data);}else {//链表不为空，找最后一个节点Node* cur = *head;while (cur->next ) {cur = cur->next;}cur->next = BuySlistNode(data);}
}

尾删
如果链表是空的，那不用操作了，如果链表是非空的而且只有一个节点，解读一下就是head指向了一个节点，head中的指针域指向为空。表明后面没有节点了。那直接释放head的空间，再把head置为空。
如果链表有多个节点，首先找到最后一个节点，然后将其释放，里面的next置为空。但是这里，因为需要把最后一个节点释放掉，还有一步操作要把倒数第二个节点的next指针置为空，如果直接把cur释放了，再找倒数第一个节点要重新遍历一次链表，所以用另一个指针，在cur每次向后走之前把cur的值保存起来，这样到时候释放最后一个节点后，prev就是最后一个节点的地址，直接把它置为空。

void Slistpopback(Node** head) {assert(head);if (*head == NULL) {return;}else if ((*head)->next == NULL) {free(*head);*head = NULL;}else {//非空，多个节点Node* cur = *head;Node* prev = NULL;while (cur->next) {prev = cur;cur = cur->next;}free(cur);prev->next = NULL;}
}

头插
如果是空链表，种一个节点，直接让head指向新节点，如果是非空的，先让新节点的next指针指向原连链表，再让head指向新节点。

void Slistpushfront(Node** head, Datatype data) {assert(head);Node* newnode = BuySlistNode(data);newnode->next = *head;*head = newnode;
}

头删，和尾删原理差不多，如果是空链表，不用操作，如果是非空并且只有一个节点，直接释放，如果有多个节点，首先将head的指向保存起来，然后让head的指向变为下一个元素，再释放掉head。

void Slistpopfront(Node** head) {assert(head);if (*head == NULL) {return;}else if ((*head)->next == NULL) {free(*head);*head = NULL;}else {Node* delnode = *head;*head = delnode->next;free(*head);}
}

任意位置的插入
首先判断位置合不合法，pos一定是一个有效的节点，因为单向链表的结构，只能通过一个节点的指针域找到后一个节点的位置，所以一定是往pos之后的位置插入的，如果要硬往前插，需要其他的设计。过程就是先设置一个新节点，让新节点的next指针指向，原本pos的后一个节点。再让pos的next指针指向新节点。

void SlistInsert(Node* pos, Datatype data) {Node* newnode = NULL;if (NULL == pos) {return;}newnode = BuySlistNode(data);newnode->next = pos->next;pos->next = newnode;
}

任意位置的删除
要删除，首先pos得是一个有效的节点，然后pos不能是最后一个节点，
给的这个方法其实传入pos，但是删除的是pos的下一个节点，原因同样是因为链表的结构，只能通过一个节点找到下一个节点，这个方法只传了一个pos，没法找到它的上一个节点，也就没法改变上一个节点的指向，删除链表就断了。
让pos的next指针指向下一个节点的下一个节点。再把pos后面的节点释放掉。

void SlistErase(Node* pos) {if (NULL == pos || pos->next == NULL) {return;}pos->next = pos->next->next;free(pos->next);
}

销毁方法
直接用头删的方法，每删除一个头节点，就让下一个节点称为新的头节点，直到链表为空

void SlistDestroy(Node** head) {Node* delnode = NULL;while (*head != NULL) {delnode = *head;*head = delnode->next;free(delnode);}
}

这篇关于无头单链表实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---