【数据结构】线性表的链式表示—单链表

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

1. 单链表的定义

逻辑上相邻的两个元素在物理位置上可以不相邻。

单链表的逻辑结构还是线性表。只不过每个结点除了存放数据元素外，还要存储指向下一个结点的指针。

单链表结点的定义：

typedef struct LNode{ // 单链表结点类型
    ElemType data;  // 数据域
    struct LNode *next;  // 指针域
}LNode,*LinkList;

说明：

• typedef相当于起别名，具体用法参考C语言的文章。
• LNode强调这是一个结点。*LinList强调这是一个单链表。

头指针：链表中第一个节点的存储位置，用来标识单链表。

头结点：在单链表第一个节点之前附加的一个结点，为了操作上的方便。

若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，它标识一个链表。

头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。

2. 优缺点比较

3. 单链表的基本操作

插入操作

• 创建新结点

q=(LNode*)malloc(sizeof(LNode))
q->data=x;

• 头插入和中间插入

q->next=p->next;
p->next=q;

• 表尾插入

p->next=q;
q->next=NULL;

说明：q是新插入的元素。p是指针指向的元素。

对于插入元素，头指针的数据域始终为空，位置不动。

插入到第i个位置实际上是将原本i-1元素的next赋值给新插入元素的next。并将i-1元素的next指向新插入元素。

删除操作

p=GetElem(L,i-1); // 查找删除位置的前驱结点
p->next=q->next;
free(q);

说明：q是要删除的元素，p是指针指向的元素。删除完后要释放空间。

对于删除元素，头指针的数据域始终为空，位置不动。

删除第i个元素实际上是将原本i元素的next赋值给i-1个位置元素的next。也叫作断链。这样第i-1个元素就和第i+1个元素链接起来，形成链表。

按位查找

LNode *p=L->next;
int j=1;
while(p && j<i){
    p=p->next;
    j++;
}
return p;

按值查找

LNode *p=L->next;
while(p!=NULL && p->data!=e){
    p=p->next;
}
return p;

说明：L表示头指针，用来指向头结点。

注意：

链表的插入、删除、查找都需要从第一个元素开始向后遍历，找到相应的额位置，所以时间复杂度均为O(n)。

4. 小结

如需完整代码，微信公众号后台回复“线性表”即可领取。