2025年手写链表 yeap

大家好，我是讯享网，很高兴认识大家。

手写链表

链表还会写吗？哈哈哈，好像有点忘了！

链表是什么？其实链表不重要，重要的是链表的节点。我们能写出来的不是链表，而是链表的节点，我们往链表的节点一直添加节点它就自动变成链表了。我们只要有链表的头节点，就能找到它后面的所有节点。

java中的链表是这样的

public class ListNode{ 
    int val；//表示数值 ListNode next；//表示下一个对象

讯享网

c的链表

讯享网int struct snode { 
    int data; struct snode*next; }LSNode;

不过要注意，链表分有头结点和无头结点两种。其实都可以。

接下来就讲一下带头结点的链表

首先是初始化

讯享网

void StackInitate(LSNode**head) { 
    *head=(LSNode*)malloc(sizeof(LSNode));//头指针的地址 (*head)->next=NULL; } //上面的LSNode只是声明，并没有分配空间，定义才有分配空间 //所以下面才需要*head=(LSNode*)malloc(sizeof(LSNode));为其分配空间

其实这里初始化的时候，因为要对链表的头节点进行修改，链表的头结点是一个指针，要对指针修改，所以传进去的必须是二级指针。

（不要被这个head迷惑，后面有一些操作变量的名字也定义为head，但是却是不一样的）

比如说

插入

讯享网void ListPush(LSNode*head,i,x)//在头结点为head的链表中的第i个位置插入数据为x的节点 { 
    LSNode*q=head; //这里必须要注意！！！i从0还是1开始，有没有头节点，j从-1还是0还是1开始while循环的条件有很大的区别 //但有一点是核心，就是要在位置i插入，就要找到i-1的节点 //下面以有头结点，i从0开始为例 j=-1; while(q->next!=NULL&&j<i-1)//这里必然是q->next!=NULL,才能保证是指向最后一个节点，如果是q!=NULL,则是指向最后一个节点的下一个节点 { 
    q=q->next; j++; } if(j!=i-1) { 
    cout<<"插入的元素位置参数错！"<<endl; return 0; } LSNode*new=（LSNode*）malloc（sizeof（LSNode））; new->data=x; new->next=q->next; q->next=new; return 1; }

删除

void ListPop(LSNode*head,i,int *x)//在头结点为head的链表中的第i个位置删除节点 { 
    LSNode*q=head; LSNode*s; //这里必须要注意！！！i从0还是1开始，有没有头节点，j从-1还是0还是1开始while循环的条件有很大的区别 //但有一点是核心，就是要在位置i插入，就要找到i-1的节点 //下面以有头结点，i从0开始为例 j=-1; while(q->next!=NULL&&q->next->next!=NULL&&j<i-1) //这里要多一个q—>next->next!=NULL,为什么呢，因为后面需要用到它赋值，所以也就不能为空 { 
    q=q->next; j++; } if(j!=i-1) { 
    cout<<"删除的元素位置参数错！"<<endl; return 0; } s=q->next; *x=s—>data; q->next=q->next->next;//(在物理意义上把该节点删除了） free(s); return 1; }

取数据元素

讯享网void ListGet(LSNode*head,i,int *x)//在头结点为head的链表中的第i个位置取节点 { 
    LSNode*q=head; LSNode*s; j=-1; while(q->next!=NULL&&j<i)//这里最大的特点就是 变成了j<i,为什么，因为取元素只要直接取就行，不需要找到前一个节点去操作 { 
    q=q->next; j++; } if(j!=i-1) { 
    cout<<"取元素位置参数错！"<<endl; return 0; } *x=q—>data; return 1; }

撤销单链表

void Destory(SLNode **head) { 
    SLNode*p,*p1; p=*head; while(p!=NULL) { 
    p1=p; p=p->next; free(p1); } *head=NULL; }

head

好，现在来讲讲一开始说到的head的问题，

初始化时：void StackInitate(LSNodehead)
插入时：void ListPush(LSNode*head,i,x)
虽然两个都是head，但是只是名称叫做head而已，代表的意义不同，第二个head才是实质意义上的头结点，而第一个head其实是头结点的指针。

所以实际上在构建的时候是这样构建的

手写链表

插入

删除

取数据元素

撤销单链表

head

相关推荐