上一節講了鏈表的基本概念以及單項鍊表的使用方法，這一節主要講解雙向鏈表的使用方法。

雙向鏈表

含義：

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。

特點：

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;
}

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

關鍵字: 數據結構 鏈表 雙向