数据结构之链表（看不懂你来找我）

大家好，欢迎来到IT知识分享网。

数据结构🚀链表

一、👿什么是链表？

链表是一种常见的数据结构，由一系列节点构成，每个节点包含当前节点的数据和一个指针(单向链表)或者两个指针(双向链表)，链表是一种动态的数据结构，可以动态的增删节点。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

1、链表的特点

• 动态内存分配：链表中的节点是在运行时动态创建的，可以根据需要分配和释放内存。
• 可扩展性：链表的大小可以根据需要动态增长或缩小，没有固定的大小限制。
• 非连续存储：链表中的节点可以分散在内存的不同位置，每个节点包含数据和指向下一个节点的指针。

二、🤡单向链表

• 每个节点包含一个数据域和一个指针域。指针域指向下一个节点，直到最后一个节点指向空指针(Null)
  
  

Head：指向头节点的指针。这里Head=200，表示第一个数据的地址。
每个节点包含当前的数据和一个指针(指向下一个数据)，不懂指针的同学可以复习一下指针。

1、构建一个单项链表

• 这里使用C++语言

struct Node{ 
       int data; // 数据 struct Node* next; //地址 }; struct Node* head; //创建一个头节点，以便后续使用 

2、插入数据

• 在链表中的任意位置插入数据

void Insert(int data ,int n){ 
       // n表示要插入的位置，从1开始算 Node* temp1 = new Node(); // 创建一个节点先承载我们要插入的数据 temp1->data = data; temp1->next = NULL; if(n==1){ 
       // 如果要插入第一个位置就把temp1的地址给head head = temp1; return; } Node* temp2 = head; // 如果不插入第一个位置就创建第二个节点 for(int i=1;i<n-1;i++){ 
       //temp2从第一个节点一直走到第n-1个节点 temp2 = temp2->next; } temp2->next = temp1;//因为temp2指向第n-1个节点，所以temp2->next就是第n个节点的地址，将temp1的地址赋给temp2->next } 

3、删除数据

• 在链表的任何一个位置删除一个数据

void Delete(int n){ 
       // 删除第n个节点 Node* temp1 = head; // 此时temp1指向第一个节点 if(n==1){ 
       head = temp1->next; // 如果删除第一个节点，就把head指向第二个节点(temp1->next) delete temp1; return; } for(int i=1;i<n-1;i++){ 
       temp1 = temp1->next; //temp1指向目标节点的前一个节点 } Node* temp2 = temp1->next; // 此时temp2指向要删除的那个节点(目标节点) temp1->next = temp2->next; //将目标节点的下一个节点接到目标节点的下一个节点 delete temp2; // 删除temp2 } 

4、打印链表

• 迭代方式实现

void Print(){ 
       struct Node* temp = head; while(temp != NULL){ 
       //从第一个循环到最后一个 std::cout<<temp->data<<" "; temp = temp->next; } std::cout<<std::endl; } 

• 递归方式实现

void Rec_print(struct Node* p){ 
       //递归打印 p:头节点的指针 if(p == NULL) return; // 退出条件 printf("%d ",p-> data); Rec_print(p->next); } 

5、反转链表

• 迭代方式实现

void Reverse(){ 
       Node* prev = NULL; Node* curr = head; Node* next; while(curr != NULL){ 
       next = curr->next;//next指向curr的下一个节点,使用next先存着curr节点 curr->next = prev;// curr指向prev prev = curr; curr = next; } head = prev; } 

这里的循环可能不太好理解，可以看看下面这张图

• 递归方式实现

void Recursion_reverse(struct Node* p){ 
       //p节点及其往后的节点全部反转 if(p->next == NULL){ 
       head = p; return; } Recursion_reverse(p->next); struct Node* q = p->next; q->next = p; p->next = NULL; } 

三、🤡双向链表

• 双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。
  
  

1、创建一个双向链表

struct Double_Node{ 
       // 双向链表 int data; struct Double_Node* next; struct Double_Node* prev; }; struct Double_Node* head2;//创建头节点 

2、插入节点

• 如果看不懂可以自己Debug一下或者画图看看

void Double_insert(int x,int n){ 
      //在任意位置插入一个节点 struct Double_Node *NewNode = new Double_Node(); NewNode->data = x; NewNode->prev = NULL; NewNode->next = NULL; if(n==1){ 
       //使NewNode成为头节点 NewNode->next = head2;//头节点 head2->prev = NewNode; head2 = NewNode; return; } struct Double_Node* temp = head2; for(int i=1;i<n-1;i++){ 
       //temp循环到第n-1个节点 temp = temp->next; } NewNode->next = temp->next;//插入节点 NewNode->prev = temp; temp->next = NewNode; temp->next->prev = NewNode; } 

3、删除节点

void Double_delete(int n){ 
       //删除第n个节点 struct Double_Node* temp = head2; if(n==1){ 
       head2 = temp->next; head2->prev = NULL; delete temp; return; } for(int i=1;i<n-1;i++){ 
       temp = temp->next; } struct Double_Node* temp2 = temp->next; temp->next = temp2->next; temp2->next->prev = temp; } 

4、打印双向链表

• 双向链表的打印实现和单项链表的一样,这里就不写了

四、🤡总结

双向链表的方法实现和单向列表的实现相似，实现方式有很多种，在学习中，重要的是学习链表的这种思想，并不是单单的使用代码，不理解的可以多Debug几次，深入理解。