🌺链表

🌷链表的定义

线性表的链式存储又称为单链表，其特点是用一组任意的存储单元来存储线性表的数据元素。

为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系，a1除了存储自身的信息之外，还需要存储一个指向其后续内容的信息（一般为后续内容的地址）。这两部分信息组成数据元素ai的存储映像，称为结点。

单链表中结点类型的描述如下：

typedef struct LNode  //定义单链表结点类型 
{
  ElemType data;    //数据元素 
  struct LNode *next;  //指向下一地址 
}LNode, *LinkList;

🌷链表的存储方式

整个链表的存取必须从头指针开始进行，头指针指向链表的第一个结点的存储位置。同时由于最后一个元素没有直接后继，则单链表的最后一个结点的指针为空（NULL）

我们来想一想，如果用链表来存储【Ceylan】，它的逻辑状态是什么样的呢？

首先应该需要一个头指针L，它指向第一个元素 'C'，通过 'C' 所在结点的信息，可以访问下一节点 'e' 所在位置，以此类推，就可以完整找到整个【Ceylan】

🌷单链表的初始化

单链表的初始化就是建立一个新的空的单链表。

🔺实现原理

1️⃣生成新结点作为头结点，用头指针L指向头结点

2️⃣头结点指向空

💬 代码演示

Status InilList(LinkList &L)
{//构建一个空的链表L 
  L=new LNode;  //生成新结点作为头结点，用头指针L指向头结点 
  L->next=NULL;  //头结点指向空 
  return OK; 
}

🌷头插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的表头，也就是头结点之后

💬 代码演示

void CreateList_H(LinkList &L,int n)
{
  L=new LNode;  
  L->next=NULL;           //先建立一个带头结点的空链表 
  for(int i=0;i<n;i++)
  {
  p=new LNode;    //生成新节点*p 
  cin>>p->data;    //输入p结点的数据 
  p->next=L->next;L->next=p;  //将新结点*p插入到头结点之后  
  }
}

❗️注意：

因为每次插入都是在链表头部，所以应该逆位序输入数据。输入顺序和线性表中的逻辑顺序是相反的。

🌷尾插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的尾部

💬 代码演示

void CreateList_R(LinkList &L,int n)
{
  L=new LNode;  //先建立一个带头结点的空链表 
  r=L;    //尾指针指向头结点 
  for(int i=0;i<n;i++)
  {
  p=new LNode;    //生成新节点*p 
  cin>>p->data;    //输入p结点的数据 
  p->next=NULL;r->next=p;  //将新结点*p插入尾结点*r之后  
  r=p 
  }
}

🌷按序号寻找结点值

🔺实现原理

1️⃣从第一个结点开始，顺指针next逐个向下搜索，直到找到第  i  个结点，

2️⃣若没有找到，返回最后一个指针域NULL

💬 代码演示

LNode *GetElem(LinkList L,int i)
{
  int j=1;    //计数，初始为1 
  LNode *p=L->next;  //头结点指针赋值给p 
  if(i==0)
  return L;   //若i为 0，返回头指针 
  if(i<1)
  return NULL;  //若i无效，则返回 NULL 
  while(p&&j<i)   //从第一个元素开始找，直到第i个结点 
  {
  p=p->next;
  j++;
  }
  return p;    //返回第 i 个结点的指针 
}

🌷按值寻找结点

🔺实现原理

1️⃣从第一个结点开始，顺指针next逐个向下搜索数值，直到找到符合的数值

2️⃣若没有找到，返回最后一个指针域NULL

💬 代码演示

LNode *LocateElem(LinkList L,ElemType e)
{
  LNode *p=L->next;
  while(p!=NULL&&p->data!=e)  //从第一个结点开始查找数据域为 e 的结点 
  {
  p=p->next;
  }
  return p;     //找到后返回该结点指针，否则返回NULL 
}

🌷插入结点

将值为 x 的新结点插到单链表的第 i 个位置。

🔺实现原理

1️⃣调用按序号查找函数，查找第i-1个结点，假设返回结点为*p

2️⃣令新结点*s的指针域指向*p的后续结点

3️⃣令结点*p的指针域指向新的插入的结点*s

💬 代码演示

p=GetElem(L,i-1)  //查找插入位置的前驱结点 
s->next=p->next;  //新结点*s的指针域指向*p的后续结点
p->next=s;    //令结点*p的指针域指向新的插入的结点*s

🌷删除结点

将单链表的第 i 个结点删除。

🔺实现原理

1️⃣调用按序号查找函数，查找第 i 个结点，假设返回结点为*p

2️⃣将*p指针域next指向下下位结点

❓提出问题

之前讲到的链表结点中只有一个指向后续结点的指针域，若从某个结点出发只能顺指针向后一个一个寻查其他结点。若要访问某个结点的前驱节点，只能从头开始遍历。

有什么方法可以克服单链表这种单向性的缺点呢？

答案就是循环链表，双向链表

🌺循环链表

🔺实现原理

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。由此，从循环链表中任意一个结点出发都能找到其他结点。

对于这个循环链表，可以用O(1)的时间访问第一个结点，但是要访问最后一个结点，却需要O(n)时间，因为需要将单链表全部扫描一遍。

❓有没有什么方法可以用O(1)的时间由链表指针访问到最后一个结点呢？

我们需要对这个循环链表进行改造，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都为O(1)的时间了。

🌷循环链表与单链表的差别

他们的差别在于：

当链表遍历时，判别终止的条件不同。假设当前指针为p，在单链表中判断是否到达终点条件为【p！= NULL】或【p->！= NULL】，循环链表的判断条件为【p->next！= L】

🌺双向链表

🔺实现原理

双链表的结点中有两个指针域，一个指向后一结点，一个指向前一结点，结点结构如图所示

💬 代码演示

双链表结点:

typedef struct DNode
{
  ElemType data;
  struct DNode *prior,*next;
}DNode, *DLinklist;

🌷双向链表插入

在双链表中p所指的结点之后插入结点*s

💬 代码演示

s->next=p->next;            //将结点*插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;

🌷双向链表删除

删除双链表中结点*p的后续结点*q

💬 代码演示

p->next=q->next;        //操作一
q->next->prior=p;       //操作二
free(p);                //释放结点空间

🌺线性表与链表的选择

在实际应用中，由于它们各有自己的优缺点，使用哪一种存储结构，应该根据具体问题具体分析，通常从空间和时间两个方向作比较分析。

🌷空间性能的比较

顺序表的存储空间必须提前分配，元素个数受到限制。一但存储空间装满了就不能扩容，若继续添加元素，就会出现内存溢出。若提前分配空间过大，可能导致大量空间被闲置，若提前分配空间过小，可能造成溢出。

链表不需要为其提前分配空间，只要内存空间允许，链表就能无限增加元素。

🌷时间性能的比较

🌹存取元素的效率

顺序表是由数组实现的，它可以顺序存取，也可以随机存取。

链表是一种顺序存取结构，只能从表头顺序存取元素

🌹逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理元素位置也相邻

采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是由指针链接来表示的

🌹查找的效率

对于按值找，两者的时间复杂度都为O(n)

对于按序号查找，顺序表可以随机访问，时间复杂度仅为O(1)，链表的时间复杂度为O(n)

🌹插入或删除的效率

对于顺序表，进行插入或删除时，要移动后方大量的元素，时间复杂度为O(n)

对于链表，在进行插入或删除时，不需要移动前后元素，只需要修改指针，时间复杂度为O(1)

🌷选择总结

1.当难以估计线性表的长度或存储规模时，不应采用顺序表，应采用链表。

2.若需要经常进行插入，删除操作时，不应采用顺序表，应采用链表。

3.若需要经常按序号访问结点值时，不应采用链表，应采用线性表。

🌺每日金句

本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪