链表——单链表

链表——单链表

链表的形式有很多，主要有一下的区别：

1、单向、双向
2、带头、不带头
3、循环、非循环

单链表

物理存储形式

单链表与顺序表的逻辑存储形式一样，都是线性存储，但是单链表的物理存储缺并不一定连续，它的每个元素之间是由地址指针相连的，所以它的每个单位是由一个存储元素和一个地址指针组成的节点，结构图如下：

上图为不带头、单向、不循环链表

代码实现

#include<stdio.h>
#include<stdlib.h>typedef int DataType;
typedef struct Node
{DataType data;       //数据域struct Node* next;   //指针域
}Node;
typedef struct LinkList
{Node* head;       //头指针
}LinkList;//初始化
void LinkListInit(LinkList* L);
//创建一个新节点
Node* CreateNewNode(DataType data);
//头插
void HeadPush(LinkList* L, DataType data);
//尾插
void TailPush(LinkList* L, DataType data);
//在pos之后插入节点
void LinkListInsert(Node* pos, DataType data);
//头删
void HeadPop(LinkList* L);
//尾删
void TailPop(LinkList* L);
//删除pos后的节点
void LinkListDelete(Node* pos);
//查找
Node* LinkListFind(LinkList* L, DataType data);
//打印
void LinkListPrint(LinkList* L);
//销毁
void LinkListDestroy(LinkList* L);
//初始化
void LinkListInit(LinkList* L)
{L->head = NULL;
}//创建一个新节点
Node* CreateNewNode(DataType data)
{Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;return node;
}//头插
void HeadPush(LinkList* L, DataType data)
{Node* node = CreateNewNode(data);if (L->head == NULL){L->head = node;}else{node->next = L->head;L->head = node;}
}//尾插
void TailPush(LinkList* L, DataType data)
{Node* node = CreateNewNode(data);if (L->head == NULL){L->head = node;}else{Node* p = L->head;while (p->next != NULL){p = p->next;}p->next = node;}
}//在pos之后插入节点
void LinkListInsert(Node* pos, DataType data)
{if (pos == NULL){return;}Node* node = CreateNewNode(data);node->next = pos->next;pos->next = node;
}//头删
void HeadPop(LinkList* L)
{if (L->head != NULL){Node* p = L->head;L->head = p->next;free(p);}
}//尾删
void TailPop(LinkList* L)
{if (L->head != NULL){Node* tail = L->head;Node* p = NULL;while (tail->next != NULL){p = tail;tail = tail->next;}if (p == NULL){L->head = NULL;}else{p->next = NULL;}free(tail);}
}//删除pos后的节点
void LinkListDelete(Node* pos)
{if (pos == NULL){return;}if (pos->next != NULL){Node* p = pos->next;pos->next = p->next;free(p);}
}//查找
Node* LinkListFind(LinkList* L, DataType data)
{if (L->head == NULL){return NULL;}Node* p = L->head;while (p != NULL){if (p->data == data){return p;}p = p->next;}return NULL;
}//打印
void LinkListPrint(LinkList* L)
{Node* p = L->head;while (p != NULL){printf("%d ", p->data);p = p->next;}printf("n");
}//销毁
void LinkListDestroy(LinkList* L)
{Node* p = L->head;Node* q = NULL;if (p != NULL){q = p;p = p->next;free(q);}
}

此为无头、单向不循环链表，结构简单，一般不会单独存储数据，更多的是作为其他数据结构的子结构，真正用来存储的是双向带头循环链表。