链表技巧

蔚落 2022-08-20 13:19 59阅读 0赞

在软件开发中，我想链表是除了数组之外，用的最多的一种数据结构。但是，如何把链表结构和数据本身能够完美地融合在一起，这本身确是一件复杂的事情。但是linux kernel在这方面为我们做出了示范，让我们在充分地享受方便的同时，无需考虑链表的一些具体操作。那么，在linux kernel下面，链表是怎么做到的呢？我们可以自己编写一个代码示范一下，基本原理都是一样的，可能在实现方式上略有不同。

**（1）定义链表的基本结构**

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  **typedef** **struct** \_LINK\_NODE  
2.  \{  
3.      **struct** \_LINK\_NODE\* prev;  
4.      **struct** \_LINK\_NODE\* next;  
5.  \}LINK\_NODE;

**（2）定义链表的基本操作**

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  **void** link\_init(**struct** \_LINK\_NODE\* pNode)  
2.  \{  
3.      ASSERT(NULL != pNode);  
4.    
5.      pNode->prev = NULL;  
6.      pNode->next = NULL;  
7.  \}  
8.    
9.  **void** link\_add(**struct** \_LINK\_NODE\* pNode, **struct** \_LINK\_NODE\* head)  
10. \{  
11.     ASSERT(NULL != pNode && NULL != head);  
12.   
13.     pNode->next = head->next;  
14.     pNode->prev = head;  
15.     head->next = pNode;  
16.     **if**(pNode->next)  
17.         pNode->next->prev = pNode;  
18. \}  
19.   
20. **void** link\_del(**struct** \_LINK\_NODE\* pNode)  
21. \{  
22.     ASSERT(NULL != pNode);  
23.   
24.     pNode->prev->next = pNode->next;  
25.     **if**(pNode->next)  
26.         pNode->next->prev = pNode->prev;  
27. \}

这里定义了链表的三个基本操作，即初始化、添加和删除。我们在这里设计的时候，为了说明方便，考虑的情况比较简单。这里编写的代码其实是有三个基本前提的：链表存在一个head节点，这个节点永远不删除；链表添加的数据都是放在head后面的；链表虽然是双向链表，但本身并不是循环链表。

**（3）在数据中嵌套使用LINK\_NODE**

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  **typedef** **struct** \_DATA\_TYPE  
2.  \{  
3.      LINK\_NODE head;  
4.      **int** value;  
5.  \}DATA\_TYPE;

这里定义了一个简单的数据类型，即为DATA\_TYPE。可是，我们记得前面定义的操作都是 关于 LINK\_NODE的，那么我们如何才能利用LINK\_NODE数据本身访问到DATA\_TYPE数据本身呢？其实不难，转化一下数据即可。

**（4）利用pNode访问pData**  
    现在假设存在这样的一个节点pNode，它的地址就是在DATA\_TYPE中head的地址，那么怎么才能进行转化呢？我们看看下面的代码是怎么做的？大家也可以自己在编译器上试一试？

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  \#define GET\_DATA\_ADDRESS(pNode, DATA, head) \\  
2.      (DATA\*)((**char**\*)(pNode) - (&((DATA\*)(0))->head))

这是一个宏，如果需要实际运算的话，应该这么做。

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  DATA\_TYPE\* pData =  GET\_DATA\_ADDRESS(pNode, DATA\_TYPE, head);

这中间其实存在一个技巧。那就是我们既然知道pNode的地址，那么只需要知道pNode和pData之间的偏移值就可以了。两者相减一下，获得值就是pData的数值，所以，这里可以利用(&((DATA\*)(0))->head)获取这个偏移值，就是这么简单。

**（5）利用pNode遍历pData**  
    因为这里的pNode是一个链表，所以利用pNode遍历pData就十分方便了。根据上面开发的思路，我们这里依然可以利用宏的方法实现pData和pNode之间的自动转换。

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  \#define FOR\_EACH\_DATA(pNode, pData, DATA, head) \\  
2.      **for**(; \\  
3.          pNode && (pData = GET\_DATA\_ADDRESS(pNode, DATA, head));\\  
4.          pNode = pNode->next)

使用的话依然十分简单，简单输入数据和数据结构类型即可，

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  FOR\_EACH\_DATA(pNode, pData, DATA\_TYPE, head)  
2.  \{  
3.      printf("pData->value = %d\\n", pData->value);  
4.  \}

**（6）其他**

通常为了使用方便，链表还会引申出更多的功能，比如自定义head节点，添加list的统计函数，或者是修改添加的方式、删除的方式等等。这些功能朋友们自己根据需要可以独立完成。当然，如果大家的思维再发散一下，也可以把这种方法推广到二叉树、平衡二叉树或者是红黑树上面。总之一句话，链表是我们在编程中使用得最多地一种技巧方法，希望朋友们可以多多掌握。

[view plain]: http://blog.csdn.net/feixiaoxing/article/details/7467730#