2.3 双链表

2 线性表

单链表	双链表
无法逆向检索，不太方便	可进可退，存储密度更低

2.4.1 基本操作

• 插入
• 删除
• 遍历

  #include<stdio.h>
  #include<stdlib.h>
  typedef struct DNode{
      int data;
      struct DNode *prior,*next;
  } DNode, *DLinklist;
  
  //创建一个结点
  DNode* CreateNode(int data){
      DNode *p;
      p=(DNode*)malloc(sizeof(DNode));
      p->data=data;
      p->prior=NULL;
      p->next=NULL;
      return p;
  }
  
  //输出链表
  void printlist(DLinklist L){
      DNode* p=L;
      for(;p!=NULL;p=p->next)
          printf("%d ",p->data);
  }
  
  int main(){
      DLinklist L=NULL;
      //创建一个结点
      DNode *p=CreateNode(1);
      //插入
      InsertNextNode(p,CreateNode(2));
      InsertNextNode(p->next,CreateNode(3));
      InsertNextNode(p->next->next,CreateNode(4));
      InsertNextNode(p->next->next->next,CreateNode(5));
  
      //输出链表
      printlist(p);
      return 0;
  }
  
  //后插
  int InsertNextNode(DNode *p, DNode *s){
      if(p==NULL||s==NULL)
          return 0;
      s->next=p->next;
      if(p->next!=NULL)
          p->next->prior=s;
      s->prior=p;
      p->next=s;
      return 1;
  }
  
  //删除
  int DeleteNode(DNode *p){
      if(p==NULL)
          return 0;
      p->prior->next=p->next;
      p->next->prior=p->prior;
      free(p);
      return 1;
  }

2.5 循环链表

2.6 静态链表

2.6.1 代码实现

• 插入
• 删除

2.7 顺序表vs链表

	顺序表	链表
逻辑结构	线性结构	线性结构
存储结构	顺序存储	链式存储
优点	随机存取，存储密度高	插入和删除

赏

谢谢你请我吃糖果