文章目录链表(Linked List)的概念：链表与数组的比较：1、数组2、链表单向链表的常用操作：1、链表的建立2、链表的遍历3、插入结点4、删除结点5、其他操作双向链表(Doubly Linked List)的常用操作：1、链表的建立2、双向链表的遍历3、插入结点4、删除结点5、其他操作（反转，查找，链表长度，释放链表）双向链表的优势：链表(Linked List)的概念：序号描述1一种动态内存分布的数据结构2若干个同一结构类型的结点依次串接而成3每个结点包含数据域和指针域两部分4常见类型包括：单向链表、双向链表、循环链表等typedefstructNode{intdata;// 数据域structNode*next;// 指针域，指向下一个结点}Node;链表与数组的比较：1、数组序号描述1需要事先定义固定长度的数组2内存空间连续分配3支持随机访问，访问效率高4在数组元素个数不确定时，可能会发生浪费内存空间的情况5插入和删除操作需要移动大量元素，效率较低2、链表序号描述1动态存储分配的数据结构2内存空间非连续分配，通过指针连接3不支持随机访问，只能顺序访问4根据需要动态开辟内存空间，比较方便地插入新元素（结点）5插入和删除操作效率高，不需要移动其他元素6使用链表可以节省内存，提高操作效率动态内存分配函数：malloc(),calloc(),realloc()动态内存释放函数：free()单向链表的常用操作：1、链表的建立头插法建立链表：Node*createListHead(intarr[],intn){Node*head=NULL;for(inti=0;in;i++){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=arr[i];newNode-next=head;head=newNode;}returnhead;}图示：初始: head → NULL插入1: head → [1] → NULL插入2: head → [2] → [1] → NULL插入3: head → [3] → [2] → [1] → NULL尾插法建立链表：Node*createListTail(intarr[],intn){Node*head=NULL,*tail=NULL;for(inti=0;in;i++){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=arr[i];newNode-next=NULL;if(head==NULL){head=newNode;tail=newNode;}else{tail-next=newNode;tail=newNode;}}returnhead;}图示：初始: head → NULL, tail → NULL插入1: head → [1] → NULL, tail → [1]插入2: head → [1] → [2] → NULL, tail → [2]插入3: head → [1] → [2] → [3] → NULL, tail → [3]2、链表的遍历voidtraverseList(Node*head){Node*current=head;while(current!=NULL){printf("%d - ",current-data);current=current-next;}printf("NULL\n");}// 计算链表长度intgetLength(Node*head){intlength=0;Node*current=head;while(current!=NULL){length++;current=current-next;}returnlength;}3、插入结点在头部插入：Node*insertAtHead(Node*head,intvalue){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;newNode-next=head;returnnewNode;}在尾部插入：Node*insertAtTail(Node*head,intvalue){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;newNode-next=NULL;if(head==NULL){returnnewNode;}Node*current=head;while(current-next!=NULL){current=current-next;}current-next=newNode;returnhead;}在指定位置插入：Node*insertAtPosition(Node*head,intvalue,intposition){if(position0)returnhead;Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;if(position==0){newNode-next=head;returnnewNode;}Node*current=head;for(inti=0;iposition-1current!=NULL;i++){current=current-next;}if(current==NULL){free(newNode);returnhead;}newNode
单链表，双链表（插入，删除，反转）
文章目录链表(Linked List)的概念：链表与数组的比较：1、数组2、链表单向链表的常用操作：1、链表的建立2、链表的遍历3、插入结点4、删除结点5、其他操作双向链表(Doubly Linked List)的常用操作：1、链表的建立2、双向链表的遍历3、插入结点4、删除结点5、其他操作（反转，查找，链表长度，释放链表）双向链表的优势：链表(Linked List)的概念：序号描述1一种动态内存分布的数据结构2若干个同一结构类型的结点依次串接而成3每个结点包含数据域和指针域两部分4常见类型包括：单向链表、双向链表、循环链表等typedefstructNode{intdata;// 数据域structNode*next;// 指针域，指向下一个结点}Node;链表与数组的比较：1、数组序号描述1需要事先定义固定长度的数组2内存空间连续分配3支持随机访问，访问效率高4在数组元素个数不确定时，可能会发生浪费内存空间的情况5插入和删除操作需要移动大量元素，效率较低2、链表序号描述1动态存储分配的数据结构2内存空间非连续分配，通过指针连接3不支持随机访问，只能顺序访问4根据需要动态开辟内存空间，比较方便地插入新元素（结点）5插入和删除操作效率高，不需要移动其他元素6使用链表可以节省内存，提高操作效率动态内存分配函数：malloc(),calloc(),realloc()动态内存释放函数：free()单向链表的常用操作：1、链表的建立头插法建立链表：Node*createListHead(intarr[],intn){Node*head=NULL;for(inti=0;in;i++){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=arr[i];newNode-next=head;head=newNode;}returnhead;}图示：初始: head → NULL插入1: head → [1] → NULL插入2: head → [2] → [1] → NULL插入3: head → [3] → [2] → [1] → NULL尾插法建立链表：Node*createListTail(intarr[],intn){Node*head=NULL,*tail=NULL;for(inti=0;in;i++){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=arr[i];newNode-next=NULL;if(head==NULL){head=newNode;tail=newNode;}else{tail-next=newNode;tail=newNode;}}returnhead;}图示：初始: head → NULL, tail → NULL插入1: head → [1] → NULL, tail → [1]插入2: head → [1] → [2] → NULL, tail → [2]插入3: head → [1] → [2] → [3] → NULL, tail → [3]2、链表的遍历voidtraverseList(Node*head){Node*current=head;while(current!=NULL){printf("%d - ",current-data);current=current-next;}printf("NULL\n");}// 计算链表长度intgetLength(Node*head){intlength=0;Node*current=head;while(current!=NULL){length++;current=current-next;}returnlength;}3、插入结点在头部插入：Node*insertAtHead(Node*head,intvalue){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;newNode-next=head;returnnewNode;}在尾部插入：Node*insertAtTail(Node*head,intvalue){Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;newNode-next=NULL;if(head==NULL){returnnewNode;}Node*current=head;while(current-next!=NULL){current=current-next;}current-next=newNode;returnhead;}在指定位置插入：Node*insertAtPosition(Node*head,intvalue,intposition){if(position0)returnhead;Node*newNode=(Node*)malloc(sizeof(Node));newNode-data=value;if(position==0){newNode-next=head;returnnewNode;}Node*current=head;for(inti=0;iposition-1current!=NULL;i++){current=current-next;}if(current==NULL){free(newNode);returnhead;}newNode
