动态数据结构

2024 年 8 月 28 日 | 阅读 9 分钟

动态数据结构是一种在运行时改变其大小的数据结构。存储在数据结构中的值可以轻松更改，无论是静态数据结构还是动态数据结构。但动态数据结构的设计方式使得数据和数据结构的大小都可以在运行时轻松更改。

动态数据结构定义的主要用例是为了在运行时轻松方便地更改数据结构的大小，而不会影响到在该数据结构增加或减少大小之前与之相关的其他操作。

与静态数据结构相比，在静态数据结构中我们只能在运行时更改数据结构中的数据，而在动态数据结构中，数据结构中的数据和数据结构的大小都可以轻松地相应地更改。在静态数据结构中，我们需要预定义或计算数据结构的大小。由于数据结构的大小已经固定，因此我们只能在静态数据结构中存储特定数量的数据。这个问题由动态数据结构解决，我们可以轻松存储在运行时生成的任何数量的数据，即在动态数据结构中，我们可以在程序执行期间的运行时轻松增加数据结构的大小。

除了这些好处之外，动态数据结构也存在一些缺点。动态数据结构的主要缺点之一是内存消耗问题。正如我们所知，动态数据结构不需要分配固定数量的内存，数据结构总是存在内存溢出的可能性。或者另一方面，如果数据结构在程序执行期间的某个操作中变为空，也可能发生内存不足。可以通过严格检查动态数据结构消耗的内存量来防止这些问题，在内存溢出的情况下，需要添加一个检查；在内存不足的情况下，需要添加一个对动态数据结构中存储的数据的检查。

动态数据结构的一些主要例子是

单向链表
双向链表
Vector
Stack
Queue
Tree

现在让我们详细看看双向链表，以便更好地理解动态数据结构及其工作原理。现在让我们编写一个双向链表的示例代码。

代码

// a sample c++ code for creating a Doubly Linked List

// iostream is included to use the cout and cin objects for input and output operation from the user.
#include <iostream>
using namespace std;
  
// A struct named Node is created that will acts as a doubly-linked list node
struct Node {
   int data;
   struct Node* next;
   struct Node* prev;
};
  
// a function named insert_front has created that inserts node at the front of the list
void insert_front(struct Node** head, int new_data)
{
   //allocate memory for New node
   struct Node* newNode = new Node;
  
   //assign data to new node
   newNode->data = new_data;
  
   //new node is head and previous is null, since we are adding at the front
   newNode->next = (*head);
   newNode->prev = NULL;
  
   //previous of head is new node
   if ((*head) != NULL)
   (*head)->prev = newNode;
  
   //head points to new node
   (*head) = newNode;
}
/* Given a node as prev_node,a fucntion named insert_After is created that insert a new node after the given node */
void insert_After(struct Node* prev_node, int new_data)
{
   //check if prev node is null
   if (prev_node == NULL) {
   cout<<"Previous node is required , it cannot be NULL";
   return;
}
   //allocate memory for new node
   struct Node* newNode = new Node;
  
   //assign data to new node
   newNode->data = new_data;
  
   //set next of newnode to next of prev node
   newNode->next = prev_node->next;
  
   //set next of prev node to newnode
   prev_node->next = newNode;
  
   //now set prev of newnode to prev node
   newNode->prev = prev_node;
  
   //set prev of new node's next to newnode
   if (newNode->next != NULL)
   newNode->next->prev = newNode;
}
  
//a function named insert_end is created that insert a new node at the end of the list
void insert_end(struct Node** head, int new_data)
{
   //allocate memory for node
   struct Node* newNode = new Node;
  
   struct Node* last = *head; //set last node value to head
  
   //set data for new node
   newNode->data = new_data;
  
   //new node is the last node , so set next of new node to null
   newNode->next = NULL;
  
   //check if list is empty, if yes make new node the head of list
   if (*head == NULL) {
   newNode->prev = NULL;
   *head = newNode;
    return;
}
  
//otherwise traverse the list to go to last node
while (last->next != NULL)
last = last->next;
  
//set next of last to new node
last->next = newNode;
  
//set last to prev of new node
newNode->prev = last;
return;
}
  
// a fucntion named display is created that prints contents of linked list starting from the given node
void displayList(struct Node* node) {
   struct Node* last;
   
   // until the last node is encountered the Linked List is traversed
   while (node != NULL) {
      cout<<node->data<<"<==>";
      last = node;
      node = node->next;
   }
   if(node == NULL)
   cout<<"NULL";
   }
  
//main function starts
int main() {

   /* Start with the empty list */
   struct Node* head = NULL;
  
   char ch;
   int data;
   do{
                  // Menu
                  // Display messages
                  cout<<"Please Choose one of the Operations::"<<endl;
                  cout<<"1. To Insert Data in the End of the Doubly Linked List."<<endl;
                  cout<<"2. To Insert Data in the Front of the Doubly Linked List."<<endl;
                  cout<<"3. To Insert Data aftere the head node in the Doubly Linked List."<<endl;
                  cout<<"4. To Display Data in the Doubly Linked List."<<endl;
                  cout<<"\n";
                  

                  // taaking input in the choice variable
                  int choice;
                  cin>>choice;

                  // Switch case
                  switch (choice) {

                  // Case 1
                  case 1:

                        // Display message
                        cout<<"Enter the data that you want to add to the Doubly Linked List::"<<endl;                        
                        cin>>data;
                        insert_end(&head,data);
                        cout<<"Data Entered Successfully at the End of the Doubly Linked List."<<endl;
                        // Break statement to terminate a case
                        break;

                  // Case 2
                  case 2:

                        // Display message
                        cout<<"Enter the data that you want to add to the Doubly Linked List::"<<endl;                        
                        cin>>data;
                        insert_front(&head,data);
                        cout<<"Data Entered Successfully at the Front of the Doubly Linked List."<<endl;
                        // Break statement to terminate a case
                        break;

                  // Case 3
                  case 3:{

                       // Print statements
                        cout<<"Enter the data that you want to add after the head node of the Doubly Linked List::"<<endl;                        
                        cin>>data;
                        insert_After(head,data);
                        cout<<"Data Entered Successfully after the head node of the Doubly Linked List."<<endl;
                        // Break statement to terminate a case
                        }
                        break;

                  // Case 4
                  case 4:

                        cout<<"Data in the Doubly Linked List is::"<<endl;
                        displayList(head);
                        // Break statement to terminate a case
                        break;

                  default:
                        // Print statement
                        cout<<"Please enter a valid option from the menu to proceed further.\n "<<endl;
                        // Break statement
                        break;
                  }


                  cout<<"\nType [N or n] to terminate the program.\nType [Y or y] to continue the program.\n";
                  cin>>ch;
                  
            } while (!(ch == 'N' || ch == 'n'));
    
   return 0;
}// end of the main function

输出

Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

1
Enter the data that you want to add to the Doubly Linked List::
12
Data Entered Successfully at the End of the Doubly Linked List.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

4
Data in the Doubly Linked List is::
12<==>NULL
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

2
Enter the data that you want to add to the Doubly Linked List::
20
Data Entered Successfully at the Front of the Doubly Linked List.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

4
Data in the Doubly Linked List is::
20<==>12<==>NULL
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

3 
Enter the data that you want to add after the head node of the Doubly Linked List::
15
Data Entered Successfully after the head node of the Doubly Linked List.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

4
Data in the Doubly Linked List is::
20<==>15<==>12<==>NULL
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

1
Enter the data that you want to add to the Doubly Linked List::
67
Data Entered Successfully at the End of the Doubly Linked List.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data at the End of the Doubly Linked List.
2. To Insert Data in the Front of the Doubly Linked List.
3. To Insert Data after the head node in the Doubly Linked List.
4. To Display Data in the Doubly Linked List.

4
Data in the Doubly Linked List is::
20<==>15<==>12<==>67<==>NULL
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
n

在上面写的代码中，我们首先在双向链表的末尾插入了值。然后我们在双向链表的开头添加了数据。然后，在双向链表的头节点之后添加了一个数据。并且写有不同的函数，如 insert_end()、insert_front() 和 insert_After()，分别用于在双向链表的末尾、开头和头节点之后添加数据。

并且在每次插入操作后都会打印双向链表的内容。

在双向链表中，我们可以通过调用其中一个写入的插入函数来存储任意数量的数据，并且在程序执行时双向链表的大小会自动增加。所以，我们可以说双向链表满足动态数据结构的所有条件。

因此，本文清楚地介绍了什么是动态数据结构，以及它相对于静态数据结构的优势。我们还看到了 C++ 编程语言中一种动态数据结构——双向链表的实现。

下一个主题数据结构中的哈希函数

← 上一个下一个 →

动态数据结构

代码

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

动态数据结构

代码

相关帖子

栈的应用、优点和缺点

后缀表达式求值

栈指针

对近乎排序的数组进行排序

队列的应用、优点和缺点

使用多项式滚动哈希函数进行字符串哈希

线段树中的懒惰传播

如何在单个数组中高效实现 k 个栈

分配最少页数

最长公共子串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器