1、不带头节点的单链表
2、带头节点的单链表
3、不带头结点的双链表
4、带头结点的双链表
5、带头结点的双向循环链表
头指针：
-
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
-
头指针具有标识作用，所以常用头指针冠以链表的名字
-
无论链表是否为空，头指针均不为空，头指针是链表的必要元素
头节点：
-
头结点是为了操作的统一和方便而设立的，放在第一元素（首元节点）的结点之前，其数据域一般无意义(也可存放链表的长度)
-
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
-
头结点不一定是链表必须要素
#include#include typedef struct node //定义一个结构体，里面包含链表的一些格式定义！ { int data; //"数据域" 保存数据元素 struct node * next; //保存下一个数据元素的地址 struct node * prev; //保存上一个数据元素的地址 }Node;//将这个结构体另命名为node //创建表头表示链表 Node* creatList()//这个部分创造的节点也就是头指针! { Node * HeadNode = (Node *)malloc(sizeof(Node));//申请链表内存！ //初始化，自己指向自己 HeadNode->next = HeadNode->prev = HeadNode; return HeadNode; } //创建节点 Node* creatNode(int data) { Node* newNode = (Node *)malloc(sizeof(Node)); //初始化 newNode->data = data;//此处创造一个单独节点，还有做任何操作，所以前后指针都指向NULL newNode->next = NULL; newNode->prev = NULL; return newNode; } //遍历链表 void printList(Node *headNode) { //双向链表不光可以用 next 打印，也可以用 prev 进行打印 //next指针打印：先进后出 //prev指针打印：先进先出 Node *p = headNode -> next;//定义一个指针p，指向头指针的下一个节点！ while(p != headNode){ //判断p所指向的节点是不是头指针，如果不是依次向后轮，如果最终指向头 //指针，那就说明此时p指向的刚好是最后一个节点，遍历完毕 printf("%dt",p->data); p = p -> next; } printf("n"); } void insertNodebyHead(Node *headNode,int data)//插入节点：头插法 { Node *newNode = creatNode(data); //创建插入的节点 ，叫做nodeNode //注意顺序，赋值会改变指针指向，因此要先连后断 newNode -> prev = headNode; //新节点的的前指针指向头指针 newNode -> next = headNode -> next;//新节点的后指针指向头指针后面的节点 headNode ->next->prev = newNode;//头指针后面的节点的前指针指向新节点 headNode -> next = newNode; //头指针指向新节点 } void insertNodebyTail(Node *headNode,int data)//插入节点：尾插法 { Node *newNode = creatNode(data); //创建插入的节点 Node *lastNode = headNode; //第一步：首先要找到最后一个节点，定义一个尾节点指针， //先指向头指针，然后一一比对，找出尾节点 while(lastNode->next != headNode) //因为尾节点的后指针指向的是头指针，所以只需要判断这个节点 //是不是指向头指针，只要指向，那就说明这个节点就是尾节点 { lastNode = lastNode->next;//往下走 } //注意顺序， headNode->prev = newNode; //头指针指向新节点（插入后就变成了尾节点） newNode->next = headNode; //新节点（插入后就变成了尾节点）的后指针指向头指针 lastNode->next = newNode; //原尾指针的后指针指向新节点（现尾节点） newNode->prev = lastNode; //新节点（插入后就变成了尾节点）的前指针指向原节点 } void deleteNodebyAppoin(Node *headNode,int posData)//删除节点 { // posNode 想要删除的节点，从第一个节点开始遍历 // posNodeFront 想要删除节点的前一个节点 Node *posNode = headNode -> next; Node *posNodeFront = headNode; if(posNode == NULL) printf("链表为空，无法删除"); else{ while(posNode->data != posData) { //两个都往后移，跟着 posNodeFront 走 posNodeFront = posNode; posNode = posNodeFront->next; if (posNode->next == headNode) { printf("没有找到，无法删除"); return; } } //找到后开始删除 posNodeFront->next = posNode->next; posNode->next->prev = posNodeFront; free(posNode); } } int main() { Node* List = creatList(); insertNodebyHead(List,1); insertNodebyHead(List,2); insertNodebyHead(List,3); printList(List); insertNodebyTail(List,0); printList(List); deleteNodebyAppoin(List,2); printList(List); return 0; }
结果：
C语言高级-链表、状态机、多线程_钟浩森的博客-CSDN博客
