通用型双向循环链表的理解

• 2022 年 2 月 6 日
• 筆記
• 编程通用知识基础

• 概要：
           通用型 ：说明在某个项目中或者嵌入式软件系统中具有统一的API操作链表，插入，查找，删除等。
           双向循环链表：具有指向前驱节点，后驱节点的链表结构，并且尾部节点的后驱节点指向头部。
           应用：在实际的应用中数据结构在条件允许的条件下设计越简单越好，特别是在资源紧缺的平台上，以下通过简单的实现，统一的一套API加上程序员编码时根据需要，个性化的节点数据内容以及查找方式，这样的实现是目前我所理解的通用型。
•  统一链表API

  /////////////////////////////////////List Code//////////////////////////////////////////////////////
  typedef struct linkHead
  {
  	struct linkHead *pxPrev;
  	struct linkHead *pxNext;
  }LinkHead;
  
  typedef int (*compareEntry)(LinkHead * entryA, LinkHead * entryB);
  
  //Init double Link List(creat)
  LinkHead * initLink();
  //Add Entry Tail
  void tailInsertEntry(LinkHead * list, LinkHead * inEntry);
  //Add Entry current Entry
  void currInsertEntry(LinkHead * currEntry, LinkHead * inEntry);
  //Delete Entry
  void deleteEntry(LinkHead * entry);
  //find Entry
  LinkHead * findEntry(compareEntry hadleLinkEntry, LinkHead *conditionEntry, LinkHead * list);
  
  //init double Link List(creat)
  LinkHead * initLink(int entrySize)
  {
  	entrySize = entrySize>=sizeof(LinkHead)?entrySize:sizeof(LinkHead);
  	LinkHead * pxLink = malloc(entrySize);
  	memset((char *)pxLink, 0, entrySize);
  	pxLink->pxPrev = (struct linkHead *)pxLink;
  	pxLink->pxNext = (struct linkHead *)pxLink;
  	return pxLink;
  }
  
  //Add Entry Tail
  void tailInsertEntry(LinkHead * list, LinkHead * inEntry)
  {
  	LinkHead * tail = list->pxNext;
  	while(tail != list)
  		tail = tail->pxNext;	
  	
  	inEntry->pxPrev = tail;
  	inEntry->pxNext = list;
  	tail->pxNext = inEntry;
  }
  
  //Add Entry current Entry
  void currInsertEntry(LinkHead * currEntry, LinkHead * inEntry)
  {
  	inEntry->pxPrev = currEntry;
  	inEntry->pxNext = currEntry->pxNext;
  	currEntry->pxNext->pxPrev = inEntry;
  	currEntry->pxNext = inEntry;
  }
  
  //Delete Entry
  void deleteEntry(LinkHead * entry)
  {
  	entry->pxPrev->pxNext = entry->pxNext;
  	entry->pxNext->pxPrev = entry->pxPrev;
  	free(entry);
  }
  
  //find Entry
  LinkHead * findEntry(compareEntry hadleLinkEntry, LinkHead *conditionEntry, LinkHead * list)
  {
  	LinkHead * tail = list->pxNext;
  	while(tail != list)
  	{
  		if(hadleLinkEntry(tail, conditionEntry))
  			return tail;
  		
  		tail = tail->pxNext;
  	}
  	
  	return 0;
  }

    

• 程序员个性化代码（根据使用场景需要）：

  
  //////////////////////////////////User Code/////////////////////////////////////////////////////////
  typedef struct myEntry
  {
  	LinkHead head;
  	int memberA;
  	int memberB;
  }MyEntry;
  
  //find Entry by MemberA
  int findEntrybyMemberA(LinkHead * entryA, LinkHead * entryB);
  
  //find Entry by MemberA
  int findEntrybyMemberA(LinkHead * entryA, LinkHead * entryB)
  {
  	MyEntry * tempEntryA = (MyEntry *)entryA;
  	MyEntry * tempEntryB = (MyEntry *)entryB;
  	
  	if(tempEntryA->memberA == tempEntryB->memberA)
  		return 1;
  	
  	return 0;
  }

    

• 简单使用demo

  MyEntry *myList;
  
  int main()
  {
  	MyEntry inList = {0};
  	MyEntry * find = 0;
  	
  	myList = (MyEntry *)initLink(sizeof(MyEntry));
  	myList->memberA = 1;
  	
  	inList.memberA = 10;
  	
  	tailInsertEntry(&myList->head, &inList.head);
  	
  	find = (MyEntry *)findEntry(findEntrybyMemberA, &inList.head, &myList->head);
  	
  	if(find)
  		printf("find Entry memberA : %d\n",find->memberA);
  	
  	return 0;
  }

    

• 运行结果：
  

  此随笔仅表达当前的理解，通用型是具有统一的操作入口，在使用时需求千变万化需要程序员自行脑补设计自己所需，这是编码的魅力所在，希望看到这篇博客的你有想法的话可以与我讨论多种其他对双向循环链表的理解，共同进步。