单链表、双向链表、循环链表 |
您所在的位置：网站首页 › 单链表循环 › 单链表、双向链表、循环链表 |
单链表、双向链表、循环链表
|
文章目录
常见链表单链表双向链表循环链表单向循环链表双向循环链表
常见链表
学习三种常见的链表结构，他们分别是：单链表、双向链表和循环链表。 单链表单链表有两个较特殊节点，头结点和尾节点。头结点用来记录链表的基地址，可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向一个空地址NULL，表示链表上的最后一个节点。 和数组一样，链表也支持数据的查找、插入和删除操作。但相对于数据的插入删除需要做大量的搬移操作，链表的插入，删除的时间复杂度为O(1)。但是链表想要随机访问第k个元素，就没有数组高效，随机访问数据的时间复杂度为O(n)。单向链表的简单实现代码如下： link_list.h /* ***************************************************************************** * * File: linke_list.h * * Description: Single link list header file * * * History: * Created: Apri, 2019 * * Copyright (c) 2019 * All rights reserved. * ****************************************************************************/ #ifndef LINK_LIST_ #define LINK_LIST_ typedef struct _node{ struct _node *next; int date; }node, *list; list init_single_link_list(); int insert_to_link_list_head(list list, int date); int insert_to_link_list_tail(list list, int date); void show_single_link_list (list head); void delete_from_link_tail(list list_); #endiflink_list.c /* ***************************************************************************** * * File: link_list.c * * Description: Single link list file * * * History: * Created: Apri, 2019 * * Copyright (c) 2019 * All rights reserved. * ****************************************************************************/ #include #include #include "link_list.h" list init_single_link_list() { list link_list = NULL; link_list = (list)malloc(sizeof(list)); if(NULL == link_list){ printf("malloc failed !!\n"); exit(1); } link_list->next = NULL; return link_list; } /* insert a node to single link list 头插法 */ int insert_to_link_list_head(list list_, int date) { list p = NULL; if (NULL == list_) { printf("list is NULL ...\n"); exit(1); } p = (list)malloc(sizeof(list)); if(p == NULL) { printf("malloc failed \n"); exit(1); } p->date = date; p->next = list_->next; list_->next = p; return 1; } /* * 尾插法实现 */ int insert_to_link_list_tail(list list_, int date) { list p = NULL; if (NULL == list_) { printf("list is NULL ...\n"); exit(1); } p = (list)malloc(sizeof(list)); if(NULL == p) { printf("malloc fialed !\n"); exit(1); } while(list_->next) { list_ = list_->next; } p->date = date; list_->next = p; p->next = NULL; return 1; } void show_single_link_list (list head) { if (NULL == head) { printf(" list is null ...\n"); return; } head = head->next; while(head) { printf("date ---- > %d \n", head->date); head = head->next; } return; } /* * delete element from tail of link list * */ void delete_from_link_tail(list list_) { if(NULL == list_) { printf("list is NULL ...\n"); exit(1); } if(list_->next == NULL) { free(list_); list_ = NULL; } while(list_->next->next) { list_ = list_->next; } free(list_->next); list_->next= NULL; return ; } /* * delete from link head * */ void delete_from_link_head(list list_) { list p = NULL; if(NULL == list_) { printf("link is NULL ...\n"); exit(1); } if(list_->next) { p = list_->next; list_->next = p->next; free(p); } return; } /* * get link list size * * */ int get_link_size(list list_) { int size = 0; if(NULL == list_) { printf("link is NULL ...\n"); exit(1); } while(list_->next) { ++size; list_ = list_->next; } return size; } void delete_specific_date(list list_, int date) { list p = NULL; int size = 0; if(NULL == list_) { printf("list is NULL ...\n"); exit(1); } size = get_link_size(list_); if (size next; while(p->date != date) { p = list_->next; } list_->next = p; free(list_); return; } int main() { list head = NULL; int i; head = init_single_link_list(); #if 0 for (i = 0; i next = NULL; head->pre = NULL; double_linklist *pNew = (double_linklist *)malloc(sizeof(double_linklist)); if (!pNew) { perror("malloc failed."); exit(1); } pNew->next = NULL; pNew->pre = head; head->next = pNew; return head; } /* @func: 头插法，新增的节点插入头结点后面 */ bool insert_linklist_head(double_linklist* head, ElementType date) { if (!head) { perror("d_linklist is NULL"); exit(1); } double_linklist* pNew = (double_linklist *)malloc(sizeof(double_linklist)); if (!pNew) { perror("malloc failed."); exit(1); } pNew->date = date; /*先确定新增节点的前后指针指向*/ pNew->pre = head; pNew->next = head->next; head->next->pre = pNew; head->next = pNew; printf("insert %d\n", head->next->date); return true; } bool isEmpty(double_linklist* head) { if (!head) { perror("d_linklist is NULL."); exit(1); } if (head->next->next == NULL && head->next->pre == head) return true; else return false; } /* @func: 删除一个节点 */ ElementType delete(double_linklist* head) { if (!head) { perror("d_linklist is NULL."); exit(1); } if (isEmpty(head)) { printf("double linklist is empty.\n"); exit(1); } double_linklist* pDel = head->next; ElementType val = pDel->date; pDel->next->pre = head; head->next = pDel->next; if (pDel) { free(pDel); pDel = NULL; } return val; } void display(double_linklist* head) { if (!head) { perror("d_linklist is NULL.\n"); exit(1); } if (isEmpty(head)) { printf("double linklist is empty.\n"); exit(1); } double_linklist* tmp = head->next; while (tmp->next != NULL) { printf("val ---> %d\n", tmp->date); tmp = tmp->next; } } int main() { double_linklist* d_link = init_double_linklist(); insert_linklist_head(d_link, 20); insert_linklist_head(d_link, 10); printf("delete val is %d .\n", delete(d_link)); printf("delete val is %d .\n", delete(d_link)); display(d_link); } 循环链表 单向循环链表和单链表相比，循环链表的优点是从链尾到链头特别容易，适合处理具有环形结构特点的数据，如著名的约瑟夫问题。循环链表的简单实现如下： robin_linklist.h #ifndef ROBIN_LINKLIST_ #define ROBIN_LINKLIST_ #include "stdbool.h" typedef int ElementType; typedef struct _node { ElementType date; struct _node* next; }robin_linklist; robin_linklist* init_robin_linklist(); bool insert_to_robin_linklist(robin_linklist* link, ElementType date); bool delete_from_robin_linklist(robin_linklist* link); void display_robin_linklist(robin_linklist* link); #endifrobin_linklist.c #include #include #include "robin_linklist.h" robin_linklist* init_robin_linklist() { robin_linklist *head = (robin_linklist *)malloc(sizeof(robin_linklist)); if (!head) { perror("malloc failed."); exit(1); } /*next指针指向自己*/ head->next = head; robin_linklist *node = (robin_linklist *)malloc(sizeof(robin_linklist)); if (!node) { perror("malloc failed."); exit(1); } node->next = head; head->next = node; return head; } /* @func : insert a element to linklist */ bool insert_to_robin_linklist(robin_linklist* link, ElementType date) { if (!link) { perror("link is NULL."); exit(1); } robin_linklist* node = (robin_linklist *)malloc(sizeof(robin_linklist)); if (!node) { perror("malloc failed."); exit(1); } node->date = date; node->next = link->next; link->next = node; return true; } /* @func : delete a element from linklist */ bool delete_from_robin_linklist(robin_linklist* link) { if (!link) { perror("link is NULL."); exit(1); } if (link->next->next != link) { robin_linklist *tmp = link->next; link->next = tmp->next; return true; }else { printf("link is empty.\n"); return false; } } void display_robin_linklist(robin_linklist* link) { if (!link) { perror("link is NULL."); exit(1); } robin_linklist *tmp = link->next; while(link != tmp->next) { printf("val ---> %d\n", tmp->date); tmp = tmp->next; } } int main() { /*test code*/ robin_linklist *ro_linklist = init_robin_linklist(); insert_to_robin_linklist(ro_linklist, 10); display_robin_linklist(ro_linklist); delete_from_robin_linklist(ro_linklist); display_robin_linklist(ro_linklist); delete_from_robin_linklist(ro_linklist); } 双向循环链表
double_robin_linklist.c #include #include #include "double_robin_linklist.h" dou_robin_link * init_double_robin_linklist() { dou_robin_link* head = (dou_robin_link *)malloc(sizeof(dou_robin_link)); if (!head) { perror("malloc failed."); exit(1); } head->next = head; head->pre = head; /*创建尾节点*/ dou_robin_link *tail = (dou_robin_link *)malloc(sizeof(dou_robin_link)); if (!tail) { perror("malloc failed."); exit(1); } tail->pre = head; tail->next = head; head->next = tail; return head; } bool isEmpty(dou_robin_link* link) { if (!link) { perror("link is NULL."); exit(1); } if (link->next->next == link && link->next->pre == link) { printf("double robin linklist is empty.\n"); return true; } else { return false; } } /* @func： 头插法 */ bool insert_head(dou_robin_link * link, ElementType date) { if (!link) { perror("link is NULL."); exit(1); } dou_robin_link *pNew = (dou_robin_link *)malloc(sizeof(dou_robin_link)); if (!pNew) { perror("malloc is NULL."); exit(1); } pNew->date = date; pNew->next = link->next; pNew->pre = link; link->next = pNew; link->next->next->pre = pNew; printf("insert -->%d\n", link->next->date); return true; } /* @func: 头删法 */ ElementType delete(dou_robin_link* link) { if (!link) { perror("link is NULL."); exit(1); } if (isEmpty(link)) { exit(1); } dou_robin_link *pDel = link->next; ElementType val = pDel->date; link->next = pDel->next; pDel->next->pre = link; printf("delete ---> %d\n", val); if(pDel) { free(pDel); pDel = NULL; } return val; } void display(dou_robin_link* link) { if(!link) { perror("link is NULL."); exit(1); } if(isEmpty(link)) { exit(1); } dou_robin_link* tmp = link->next; while (tmp->next != link && tmp->next->pre != link) { printf("val ---> %d\n", tmp->date); tmp = tmp->next; } } int main() { dou_robin_link *head = init_double_robin_linklist(); insert_head(head, 10); insert_head(head, 20); delete(head); display(head); } |
双向链表的简单实现： double_robin_linklist.h【本文地址】