数据结构不带头结点的单链表,单链表是不是逻辑结构
目录链表。什么是链表？链表的分类目标是一点简单的准备。单链表的本体是动态打印的。添加、删除、检查、修改节点等。接口函数如尾插入、头插入、尾删除和指定位置添加和删除函数用于查找指定位置。在指定位置之前插入数据，在指定位置删除数据。最后
故事还在继续。财技大学生做完序列表，感觉很好，有了把所有数据结构都过一遍的想法。他自信地翻到高阶数据结构的后面，然后合上，做了一个很棒的决定：还是先挑软霸。
所以，今天的受害者是单链表。
什么是链表？
链表是物理存储结构中一种不连续、无顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接的顺序来实现的。
(链表的魅力)
好了，我们已经解决了什么是，让我们来解决为什么会有链表的问题。序列表不香吗？
好香，好香，好香。
但是，序列表有几个小问题：
指定位置的头插入/删除，时间复杂度为O(N)。你需要申请新的空间来扩充产能。如果遇到极端情况，一个序列表的空间特别大，这样复制数据释放空间，会有不小的消耗。之前我们选择增加2的容量。如果我们需要的空间比较小，就会有很多空间浪费。因此我们需要一种新的数据结构来解决上述问题。
于是，链表诞生了。
注意：
从图中可以看出，链结构在逻辑上是连续的，但在物理上不一定是连续的。链表的节点通常是从堆中应用的。从堆中应用的空间可能是连续的，也可能不是连续的。
链表的分类：单向或双向前导，或无前导，循环或非循环。上述情况的排列组合可以有八个链表结构。
今天我们要写一个没有头的单向非循环链表。
没有奖品的测验：接下来是什么？
目标：一个无表头的单向无环链表，实现添加、删除、检查、修改等基本界面功能。开始！
一点简单的准备工作。
单链表的本体typedef int SLTDataType
typedef结构SListNode
{
SLTDataType数据；
struct SListNode * next
} SListNode同时，主要功能：
int main()
{
SListNode * plist=NULL
返回0；
}
单链表打印//单链表打印
void SListPrint(SListNode* phead)
{
断言(phead)；
SListNode * cur=phead
而(cur！=空)
{
printf(%d-，cur-data)；
cur=cur-next；
}
printf( NULL \ n )；
}遍历整个链表，打印当前节点的值，指针指向下一个节点，直到节点为空，打印结束。
很好理解。
动态申请节点//动态申请节点
slist node * buys list node(SLT data type x)
{
slist node * new node=(slist node *)malloc(sizeof(slist node))；
new node-data=x；
new node-next=NULL；
返回newnode
}申请一个节点，给数据赋值，将指针初始化为null。
这不是很简单吗？让我们来看看新增内容、删除内容和更正内容：
添加、检查、更改等界面功能
插尾因为插尾相对容易，所以先说插尾。
void slist push back(slist node * * PP head，SLTDataType x)
{
slist node * new node=buys list node(x)；
if (*pphead==NULL)
{
* pphead=newnode
}
其他
{
SListNode * tail=* pphead
while(尾巴——下一个！=空)
{
tail=tail-next；
}
tail-next=new node；
}
}传递二级指针的原因：函数传递形参，形参的改变不影响实参。老问题。
比顺序表稍微复杂一点的是，链表要考虑的情况比顺序表多，不过不用担心，我慢慢画，慢慢分析。
极端情况是怎样的？这是终点。
所以我们在编写链表的时候，需要考虑这种编写方式是否适合端点。如果不是，我们需要特别考虑。
例如，我们当前的尾部插入：
注：为了方便理解，我们都是从一般到特殊来分析。
一般情况：特殊情况：链表为空，没有tail- next，直接插入即可。
在标题中插入void slistpushfront(slist node * * PP head，sltdatatype x)。
{
slist node * new node=buys list node(x)；
new node-next=* PP head；
* pphead=newnode
}
按照图中所示的方法链接即可。
这时候可能有人会问，如果链表是空的呢？
我们来分析一下：如果链表为空，pphead指向NULL，new node-next=* PP head；然后newnode指向null，pphead指向newnode。没有问题。
头删除void slistpopfront(slist node * * PP head)
{
if (*pphead==NULL)
{
Printf(链表为空！\ n’)；
返回；
}
SListNode * tmp=* pphead
* PP head=(* PP head)-next；
免费(tmp)；
}
先用tmp接收头节点，然后将pphead向后移动一步，释放tmp。
注意，重点是防止链表为空。
删除尾部void slistpopback(slist node * * PP head)
{
if (*pphead==NULL)
{
Printf(链表为空！\ n’)；
返回；
}
else if ((*pphead)- next==NULL)
{
免费(* PP head)；
* pphead=NULL
}
其他
{
SListNode * tail=* pphead
SListNode * prev=NULL
while(尾巴——下一个！=空)
{
prev=tail
tail=tail-next；
}
自由(尾巴)；
prev-next=NULL；
}
}删尾应该比较复杂。我们来慢慢分析一下：
先写出一般逻辑：先找到尾节点和尾节点的前一个节点，删除尾节点，尾节点的前一个节点指向null。考虑特殊情况：空链表：直接返回。只有一个节点，直接删除，pphead留空。
指定位置添加和删除功能
查找指定位置//查找链表
slist node * slist find(slist node * PP head，SLTDataType x)
{
SListNode * pos=pphead
while (pos！=空)
{
如果(位置数据==x)
{
退货位置；
}
pos=pos-next；
}
返回NULL
}遍历，找到返回地址，但不返回NULL。
遍历什么是最好的。
在指定位置之前插入数据。//单链表在pos位置前插入X
void slist insert(slist node * * PP head，SListNode* pos，SLTDataType x)
{
if (pos==*pphead)
{
SListPushFront(pphead，x)；
返回；
}
其他
{
slist node * new node=buys list node(x)；
SListNode * cur=* pphead
while (cur- next！=位置)
{
cur=cur-next；
}
new node-next=pos；
cur-next=new node；
}
}在第一个节点之前插入是头插入。
其他位置的大概逻辑见下图：
删除指定位置的数据。//单链表删除pos位置的值
无效滑动酯酶(滑动节点** pphead，滑动节点* pos)
{
if (pos==*pphead)
{
SListPopFront(PP head)；
返回；
}
其他
{
SListNode * cur=* pphead
while (cur- next！=位置)
{
cur=cur-next；
}
cur-next=pos-next；
免费(pos)；
}
}第一个位置是头删除，直接在函数上。
剩下的位置直接上就行了。
注意：删除和添加函数都使用cur接收pos之前的位置。写代码的时候，不需要考虑断开的顺序。写起来很方便，不需要考虑回放图。
最后，单链表适合删除头插，其余位置需要遍历，不太划算。还是画画重要。广告：亲爱的兄弟们，我们最近成立了一个非专业转码社区。欢迎来玩！
转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。