在学习RTOS操作系统时，在任务优先级设置时用到了双向链表，说实话数据结构的东西只是停留在大学上课阶段，并未实践过，在操作系统中看得云里雾里，遂将其单独拿来了进行了一下思考，经过一个上午的摸索逐渐领会到了其中的精华。
1.什么是双向链表
百度百科：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
此表中包含两个重要信息：链表结构，节点结构
首先定义好节点的结构体：
typedef struct _tNode
{
int data;
struct _tNode * pre;
struct _tNode * next;
}tNode;
然后在定义链表的结构体：
typedef struct _tList
{
tNode HeadNode;
int NodeCount;
}tList;
这个结构体的作用就是可以在工程中创建多个这样的链表结构，结构体里包含头结点HeadNode和此链表节点的数量NodeCount用来对链表进行操作的定位。头结点并不保存数据，只是提供指向节点的指针用来连接整个链表。所以在操作链表时可以很快地进行各种操作。在操作链表时只需要对完成对节点地添加和删除即可，头结点保持不变！
基本初始化：
void tNodeInit(tNode *Node)
{
Node->pre = Node;
Node->next = Node;
} void tListInit(tList *list)//初始化链表
{
list->HeadNode.pre = &(list->HeadNode);
list->HeadNode.next = &(list->HeadNode);
list->NodeCount = ;
} int tListCount(tList *list)//返回链表节点数量
{
return list->NodeCount;
}
节点数据的插入和删除：
tNode* FirstNode(tList *list)//返回首节点
{
tNode* node = (tNode*);
if (list->NodeCount != )
{
node = list->HeadNode.next;
}
return node;
} tNode* LastNode(tList *list)//返回最后一个节点
{
tNode* node = (tNode*);
if (list->NodeCount != )
{
node = list->HeadNode.pre;
}
return node;
} tNode* tListPre(tList* list,tNode* node)//返回一个节点的前一个节点
{
if (node->pre == node)
{
return (tNode*);
}
else
{
return node->pre;
}
} tNode* tListNext(tList* list, tNode* node)//返回节点的后一个节点
{
if (node->next == node)
{
return (tNode*);
}
else
{
return node->next;
}
} void RemoveAll(tList* list)//删除所有节点
{
tNode* CurrentNode, *NextNode;
int count; NextNode = list->HeadNode.next;
for (count=list->NodeCount;count > ;count --)
{
CurrentNode = NextNode;
NextNode = CurrentNode->next; CurrentNode->pre = CurrentNode;
CurrentNode->next = CurrentNode;
} list->HeadNode.pre = &(list->HeadNode);
list->HeadNode.next = &(list->HeadNode); list->NodeCount = ;
} void tListHeadAdd(tList *list,tNode *node)//在头部添加节点
{
node->next = list->HeadNode.next;
node->pre = list->HeadNode.next->pre; list->HeadNode.next = node;
list->HeadNode.next->pre = node; list->NodeCount ++; } void tListLastAdd(tList *list,tNode *node)//在最后添加节点
{
node->pre = list->HeadNode.pre;
node->next = list->HeadNode.pre->next; list->HeadNode.pre->next = node;
list->HeadNode.pre = node; list->NodeCount ++;
} tNode* RemoveFirstNode(tList *list)//移除第一个节点
{
tNode *node = (tNode *);
if (list->HeadNode.next != )
{
node = list->HeadNode.next; node->next->pre = &(list->HeadNode);
list->HeadNode.next = node->next; list->NodeCount --; free(node);
}
else
{
return node;
}
} void tListInsertAfter(tList * list, tNode * nodeAfter, tNode * nodeToInsert)//在一个节点后添加一个节点
{
nodeToInsert->next = nodeAfter->next;
nodeToInsert->pre = nodeAfter; nodeAfter->next->pre = nodeToInsert;
nodeAfter->next = nodeToInsert; list->NodeCount ++;
} void tListRemove(tList * list, tNode * node)//移除节点
{
node->pre->next = node->next;
node->next->pre = node->pre; free(node); list->NodeCount --; }
在这个双向链表的实现过程中可以很好地实现队列操作，先进先出概念如这样验证：
int main()
{
tList list;
tNode *node;
int i = ; tListInit(&list); for (i = ; i < ; i++)
{
node = (tNode*)malloc(sizeof(tNode)); printf("Please input the number:");
scanf_s("%d",&node->data); tListLastAdd(&list, node);
} node = FirstNode(&list); printf("List is:");
for (i = ; i < ; i++)
{
printf("%d ",node->data);
node = node->next;
}
printf("\n");
getch();
return ;
}
实现效果为：
在这个基础上还可以用于多种其他用处！
PS:今天是自己第一天也是第一次写博客，在实现的过程中遇到很多问题也有很多想法，本来想一一记录但是发现写起来还是很艰辛，也许我现在就是一个小菜鸟，但是希望能够通过自己的努力一点一滴地积累逐渐成长，希望这个博客可以被我一直写下去！
写于广东海悟科技有限公司 2017-11-10 22:29:50