概念
其所有节点除了包含自己存储的元素，还能够指向其他结点（地址）
优点
不要求大片连续空间，改变容量方便
缺点
不可随机存取，要耗费一定空间存放指针
创建
头插法
#include"head.h"
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
int length;
}LNode,*LinkList;//用来区分表和点
LinkList InitList1()
{
printf("头插法\n");
LinkList head = (LinkList)malloc(sizeof(LNode));//创建一个头
LNode* node = NULL;//定义新节点
head->next = NULL;
node = head->next;//新节点的下一位永远指向空
printf("创建几个节点？\n");
int cnt;
scanf("%d", &cnt);
for (int i = 0; i < cnt; i++)
{
node = (LinkList)malloc(sizeof(LNode));//为新节点开辟空间
int value;
printf("请输入节点元素值\n");
scanf("%d", &value);
node->data = value;//为新节点赋值，node存放的data为value
node->next = head->next;//将头指针所指的下一个节点赋值给新节点所指的下一个位置
head->next = node;//将新节点的位置赋值给head所指的下一个位置
}
return head;
}
LinkList TraverseList(LinkList head)
{
int i = 1;
while (head->next!=NULL)//head本身不存参数，若下一位非空则输入合法
{
head = head->next;//表的数值从head所指的下一个节点开始算
printf("元素%d:%d\n",i,head->data);
i++;
}
return 0;
}
int main()
{
LinkList head = InitList1();
TraverseList(head);
}
结果
注：
①头插法，顾名思义，在头结点后依次插入，新来的元素总会在头结点后面，因此输出也为倒序输出，相对不直观，因此个人喜欢尾插法。
②head.h头文件是个人所写，只是为了防止vs报错，正常用stdio.h之类的也可以
尾插法
LinkList InitList2()
{
printf("尾插法\n");
LinkList head = (LinkList)malloc(sizeof(LNode));
LNode* node = NULL;
LNode* end = NULL;
head->next = NULL;
end = head;
printf("创建几个节点？\n");
int cnt;
scanf("%d", &cnt);
for (int i = 0; i < cnt; i++)
{
node = (LinkList)malloc(sizeof(LNode));//为新节点开辟空间
int value;
printf("请输入节点元素值\n");
scanf("%d", &value);
node->data = value;
end->next = node;
end = node;
}
end->next = NULL;
return head;//必须返回一个值
}
运行结果
插入节点
头插法
LinkList Insert(LinkList head)
{
LNode* node = (LinkList)malloc(sizeof(LNode));
int n, elem;
printf("请输入需要插入的元素（头插）\n");
scanf("%d",&elem);
node->data = elem;
node->next = head->next;
head->next = node;
printf("插入元素%d成功\n",node->data);
return head;
}
尾插法
LinkList Insert2(LinkList head)
{
LNode* node = (LinkList)malloc(sizeof(LNode));
int n, elem;
printf("请输入需要插入的元素（尾插）\n");
scanf("%d", &elem);
node->data = elem;
while (head->next)
{
head = head->next;
}
head->next = node;
node->next = NULL;
printf("插入元素%d成功\n", node->data);
return head;
}
中间插入
LinkList Insert3(LinkList head)//无法头插
{
int n, elem;
printf("新插入的元素放置の位置\n");
scanf("%d", &n);
printf("请输入要插入的元素\n");
scanf("%d", &elem);
LNode* node = (LinkList)malloc(sizeof(LNode));
node->next = NULL;
node->data = elem;
int len = 0;
while (head->next)
{
len++;
head = head->next;
if (len == n)
{
node->next = head->next;
head->next = node;
}
}
//printf("表长:%d\n", len);
return head;
}