双向链表的储存结构示意图
双向链表的初始化结构
1.双向链表的结点
代码实现
//双向链表的结点，包含一个数据域，两个指针域typedefstructDoublyNode { ElementTypedate; //数据域structDoublyNode*prev; //指向前缀结点structDoublyNode*next; //指向后缀结点}DoublyNode;
2.双向链表的头结点
//双向链表typedefstructDoublyLinkList { intlength; DoublyNode*next; };
3.总代码
//双向链表的结点，包含一个数据域，两个指针域typedefstructDoublyNode { ElementTypedate; //数据域structDoublyNode*prev; //指向前缀结点structDoublyNode*next; //指向后缀结点}DoublyNode; //双向链表typedefstructDoublyLinkList { intlength; DoublyNode*next; };
双向链表中的指定文件插入元素
1，插入的为第一个位置
代码实现
2.其他位置插入
代码实现
总代码
voidInsertDoublyLinkList(DoublyLinkList*dlist, intpos, ElementTypeelement) { //创建空节点DoublyNode*node= (DoublyLinkList*)malloc(sizeof(DoublyLinkList)); node->date=element; node->prev=NULL; node->next=NULL; //在第一个位置插入结点if (pos==1) { node->next=dlist->next; dlist->next=node; node->next->prev=node; dlist->length++; return; } DoublyLinkList*currNode=dlist->next; for (inti=1; currNode&&i<pos-1; i++) { currNode=currNode->next; } if (currNode) { node->prev=currNode; if (currNode->next) { //如果前置结点非空->因为空就表示没有后继结点了//将插入位置的前置结点改为指向新结点currNode->next->prev=node; } node->next=currNode->next; currNode->next=node; dlist->length++; } }
双向链表的删除
1.删除第一个元素
代码实现
2.删除其他位置元素
代码实现
总代码
voidDeleteDoublyLinkList(DoublyLinkList*dlist, intpos) { if (pos==1) { DoublyLinkList*node=dlist->next; if (node) { dlist->next; if (node->next) { //如果哟有第二个结点，那么设置第二个结点的前置结点为NULLnode->next->prev=NULL; } free(node); dlist->length--; } return; } DoublyLinkList*node=dlist->next; for (inti=1; i<pos; i++) { node=node->next; } if (node) { if (node->next) { node->next->prev=node->prve; } node->prev->next=node->next; free(node); dlist->length--; } return; }
