上一节讲了链表的基本概念以及单项链表的使用方法，这一节主要讲解双向链表的使用方法。

双向链表

含义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

特点：

1）在数据结构中具有双向指针
2）插入、删除数据的时候需要考虑前后的方向的操作

用法：

typedef struct NODE{
	struct NODE *prev;
	struct NODE *next;
	int	 data;
}Node;

1.初始化链表：

int InitNodeList(Node **node)
{
	*node=(Node*)malloc(sizeof(Node));//链表分配内存空间
	if(!*node)
	{
		return 0;
	}
	(*node)->prev=NULL;
	(*node)->next=NULL;
 	return 1;
}

2.插入数据：

int InsertNodeList(register Node *root,int data)
{
 register Node *this;
 register Node *next;
 register Node *newnode;
 for(this = root;(next = this->next)!= NULL; this =next)
 {
 if(next->data == data)
 {
 return 0;
 } 
 if(next->data > data)
 {
 break;
 } 
 }
 /*新节点分配内存空间*/
 newnode = (Node *)malloc(sizeof(Node));
 if(newnode == NULL) 

 {
 return -1;
 }
 
 /*新节点插入链表*/
 newnode->data = data;
 
 /*插入新节点*/
 newnode->next = next;
 this->next = newnode;
 
 if(this != root)
 {
 newnode->prev = this;
 }
 else
 {
 newnode->prev = NULL;
 }
 
 if(next != NULL)
 {
 next->prev = newnode;
 }
 else
 {
 root->prev = newnode;
 }
 return 1;
}

3.获取链表长度

int LengthNodeList(Node *root)
{
 int i = 0;
 Node *previous;
 previous=root->next;/*p指向链表的第一个结点。*/
 /*循环链表，直到节点为空*/
 while(previous)
 {
 i++;
 previous=previous->next; 

 }
 return i;
}

4.删除节点：

void DestroyNodeList(Node *root)
{
 Node *current,*next;
 
 if(root == NULL)
 {
 return; 
 }
 
 current=root;/*current 指向链表的根结点*/
 /*当节点指向为空，即到了链表末尾，跳出*/
 while(current)
 {
 next = current->next;/*指向当前结点的下一个结点。*/
 free(current);/*释放当前结点*/
 current = next;/*指向下一个结点*/
 }
}

5.调用：

int main(void)
{
	Node *root;
	int node_length = 0;
	InitNodeList(&root); /*初始化链表，得到一个跟节点*/
	InsertNodeList(root,10); /*向链表中插入一个数据*/
	InsertNodeList(root,20); /*向链表中插入一个数据*/
	node_length = LengthNodeList(root); /*获取链表长度*/ 

	printf("%d\n",node_length);
	DestroyNodeList(root); /*销毁链表*/
	return 0;
}

閱讀更多 大貓玩程序 的文章

關鍵字: 双向 C语言 数据结构