双向链表（数据结构）

2025年4月21日 | 阅读 10 分钟

双向链表是一种复杂的链表类型，其中每个节点都包含一个指向序列中前一个节点以及后一个节点的指针。因此，在双向链表中，一个节点包含三个部分：节点数据、指向序列中后一个节点的指针（next 指针）、指向前一个节点的指针（previous 指针）。下面图示了一个双向链表的节点示例。

下图展示了一个包含三个节点的双向链表，其数据部分从 1 到 3。

在 C 语言中，双向链表中节点的结构可以表示为：

struct node 
{
	struct node *prev; 
	int data;
	struct node *next; 
} 

第一个节点的 prev 部分和最后一个节点的 next 部分将始终包含 null，表示两个方向的结束。

在单向链表中，我们只能单向遍历，因为每个节点只包含下一个节点的地址，而没有任何关于其前一个节点的信息。然而，双向链表克服了单向链表的这一限制。由于列表的每个节点都包含其前一个节点的地址，我们可以通过使用每个节点中存储的前一个地址来查找前一个节点的所有详细信息。

双向链表的内存表示

双向链表的内存表示如下图所示。通常，双向链表为每个节点消耗更多空间，因此会导致插入和删除等基本操作的开销更大。但是，我们可以轻松地操作列表中的元素，因为列表在两个方向（前向和后向）都维护着指针。

在下图所示的列表中，第一个元素 i.e. 13 存储在地址 1。head 指针指向起始地址 1。由于这是添加到列表中的第一个元素，因此列表的 prev 包含 null。列表的下一个节点位于地址 4，因此第一个节点在其 next 指针中包含 4。

我们可以以这种方式遍历列表，直到找到任何 next 部分包含 null 或 -1 的节点。

双向链表的操作

节点创建

struct node 
{
	struct node *prev;
	int data;
	struct node *next;
};
struct node *head; 

有关双向链表的所有剩余操作将在下表中进行说明。

序号	操作	描述
1	在开头插入	在链表的开头添加节点。
2	在末尾插入	在链表的末尾添加节点。
3	在指定节点后插入	在指定节点之后向链表中添加节点。
4	在开头删除	从列表开头移除节点
5	在末尾删除	从列表末尾移除节点。
6	删除具有给定数据的节点	删除包含给定数据的节点之后的节点。
7	搜索	将每个节点数据与要搜索的项目进行比较，如果找到项目则返回列表中项目的位置，否则返回 null。
8	遍历	至少访问列表中的每个节点一次，以执行某些特定操作，例如搜索、排序、显示等。

C 语言中实现双向链表所有操作的菜单驱动程序

示例

#include<stdio.h>
#include<stdlib.h>
struct node
{
    struct node *prev;
    struct node *next;
    int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
	while(choice != 9)
	{
		printf("\n*********Main Menu*********\n");
		printf("\nChoose one option from the following list ...\n");
		printf("\n===============================================\n");
		printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n
		5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");
		printf("\nEnter your choice?\n");
		scanf("\n%d",&choice);
		switch(choice)
		{
			case 1:
			insertion_beginning();
			break;
			case 2:
            		insertion_last();
			break;
			case 3:
			insertion_specified();
			break;
			case 4:
			deletion_beginning();
			break;
			case 5:
			deletion_last();
			break;
			case 6:
			deletion_specified();
			break;
			case 7:
			search();
			break;
			case 8:
			display();
			break;
			case 9:
			exit(0);
			break;
			default:
			printf("Please enter valid choice..");
		}
	}
}
void insertion_beginning()
{
   struct node *ptr; 
   int item;
   ptr = (struct node *)malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
    printf("\nEnter Item value");
    scanf("%d",&item);
    
   if(head==NULL)
   {
       ptr->next = NULL;
       ptr->prev=NULL;
       ptr->data=item;
       head=ptr;
   }
   else 
   {
       ptr->data=item;
       ptr->prev=NULL;
       ptr->next = head;
       head->prev=ptr;
       head=ptr;
   }
   printf("\nNode inserted\n");
}
   
}
void insertion_last()
{
   struct node *ptr,*temp;
   int item;
   ptr = (struct node *) malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
       printf("\nEnter value");
       scanf("%d",&item);
        ptr->data=item;
       if(head == NULL)
       {
           ptr->next = NULL;
           ptr->prev = NULL;
           head = ptr;
       }
       else
       {
          temp = head;
          while(temp->next!=NULL)
          {
              temp = temp->next;
          }
          temp->next = ptr;
          ptr ->prev=temp;
          ptr->next = NULL;
          }
           
       }
     printf("\nnode inserted\n");
    }
void insertion_specified()
{
   struct node *ptr,*temp;
   int item,loc,i;
   ptr = (struct node *)malloc(sizeof(struct node));
   if(ptr == NULL)
   {
	   printf("\n OVERFLOW");
   }
   else
   {
	   temp=head;
	   printf("Enter the location");
	   scanf("%d",&loc);
	   for(i=0;i<loc;i++)
	   {
		   temp = temp->next;
		   if(temp == NULL)
		   {
			   printf("\n There are less than %d elements", loc);
			   return;
		   }
	   }
	   printf("Enter value");
	   scanf("%d",&item);
	   ptr->data = item;
	   ptr->next = temp->next;
	   ptr -> prev = temp;
	   temp->next = ptr;
	   temp->next->prev=ptr;
	   printf("\nnode inserted\n");
   }
}
void deletion_beginning()
{
    struct node *ptr;
    if(head == NULL)
	{
		printf("\n UNDERFLOW");
	}
	else if(head->next == NULL)
	{
		head = NULL; 
		free(head);
		printf("\nnode deleted\n");
	}
	else
	{
		ptr = head;
		head = head -> next;
		head -> prev = NULL;
		free(ptr);
		printf("\nnode deleted\n");
	}

}
void deletion_last()
{
    struct node *ptr;
    if(head == NULL)
	{
		printf("\n UNDERFLOW");
	}
	else if(head->next == NULL)
	{
		head = NULL; 
		free(head);	
		printf("\nnode deleted\n");
	}
	else 
	{
		ptr = head; 
		if(ptr->next != NULL)
		{
			ptr = ptr -> next; 
		}
		ptr -> prev -> next = NULL; 
		free(ptr);
		printf("\nnode deleted\n");
	}
}
void deletion_specified()
{
	struct node *ptr, *temp;
	int val;
	printf("\n Enter the data after which the node is to be deleted : ");
	scanf("%d", &val);
	ptr = head;
	while(ptr -> data != val)
	ptr = ptr -> next;
	if(ptr -> next == NULL)
	{
		printf("\nCan't delete\n");
	}
	else if(ptr -> next -> next == NULL)
	{
		ptr ->next = NULL;
	}
	else
	{ 
		temp = ptr -> next;
		ptr -> next = temp -> next;
		temp -> next -> prev = ptr;
		free(temp);
		printf("\nnode deleted\n");
	}	
}
void display()
{
	struct node *ptr;
	printf("\n printing values...\n");
	ptr = head;
	while(ptr != NULL)
	{
		printf("%d\n",ptr->data);
		ptr=ptr->next;
	}
} 
void search()
{
	struct node *ptr;
	int item,i=0,flag;
	ptr = head; 
	if(ptr == NULL)
	{
		printf("\nEmpty List\n");
	}
	else
	{ 
		printf("\nEnter item which you want to search?\n"); 
		scanf("%d",&item);
		while (ptr!=NULL)
		{
			if(ptr->data == item)
			{
				printf("\nitem found at location %d ",i+1);
				flag=0;
				break;
			} 
			else
			{
				flag=1;
			}
			i++;
			ptr = ptr -> next;
		}
		if(flag==1)
		{
			printf("\nItem not found\n");
		}
	}	
		
}

编译并运行

输出

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value12

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value1234

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
2

Enter value89

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
3
Enter the location1
Enter value12345

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12345
12
89

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
5

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123
12345

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
7

Enter item which you want to search?
123

item found at location 1 
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

Can't delete

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
9 

Exited..

关于双向链表的选择题

问题 1：连接两个循环双向链表和两个双向链表所需的时间是多少？

O(n), O(n)
O(n), O(1)
O(1), O(n)
O(1), O(1)

答案

选项 C: O(1), O(n)

通过至少一个链表的最后一个节点指针（当然，除非另有说明，否则还需要链表头指针），可以在 O(1) 时间内轻松连接两个循环双向链表。双向链表需要 O(n) 时间，因为我们无法在 O(1) 时间内找到双向链表的最后一个元素。

问题 2：如果所有双向链表的节点数据都相同，则找出以下程序的功能。

 
struct DDL{
    struct DDL * prev;
    int data;
    struct DDL * next;
}

void DDLnew(struct DDL * first){
    struct DDL * current = First, Second;
    if(current == NULL)
    return;
    
    while(current-> next!= NULL){
        if(current->data == current->next->data){
            Second = current->next->next;
            free(current->next);
            current->next = Second;
            current->next->prev = current;
        }
        else{
            current = current->next;
        }
    }
}   

删除重复节点。
删除间隔重复节点。
删除相邻节点。
无

答案

d) 以上都不是

First = 100（设为 head）

Current = 100

Second = 200

Free(current → next) = free(200)

Current → next = 300

Current → next → prev = 100

First = 100

Current = 100

Second = NULL

Free(current → next) = free(300)

Current → next = 300 NULL

Current → next → prev = 100 NULL

退出循环

对于连续相同数据的节点，除了第一个节点外，其余节点都将被删除。

因此，选项 (D) 是正确的。

问题 3：是否可以通过每个节点仅使用一个指针来创建双向链表？

是的，可以通过存储当前节点和前一个节点的 XOR 来实现。
是的，可以通过存储前一个节点和后一个节点的地址的 XOR 来实现。
是的，可以通过存储地址和下一个节点的 XOR 来实现。
不可能

答案

(b) 是的，可以通过存储前一个节点和后一个节点的地址的 XOR 来实现。它们被称为 XOR 链表。

问题 4：在通过单向链表实现双向链表时需要多少个额外的指针？

答案

(a) 1。双向链表需要两个指针，而我们知道单向链表已经有一个指针，所以我们需要一个额外的指针才能从单向链表实现双向链表。

问题 5：双向链表每个节点所需的最小字段数是。

答案

(a) 3，双向链表的每个节点都有三个字段，即数据部分、指向下一个节点的指针、指向前一个节点的指针。

下一主题循环链表

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

双向链表（数据结构）

双向链表的内存表示

双向链表的操作

C 语言中实现双向链表所有操作的菜单驱动程序

示例

关于双向链表的选择题

相关帖子

循环双向链表

链表类型

数据结构中的链表

循环链表

单向链表

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器