线性表的链式存储结构

为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，除了存储本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。

我们把存储数据元素信息的位置称为数据域，把存储其直接后继信息的位置称为指针域。这两部分组成数据元素的结点(Node)。

头结点和头指针

1. 头结点

   头结点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义；

   有了头结点，对在第一个元素结点前插入和删除第一个结点的操作就与其他结点的操作统一了；

   头结点不是链表的必须要有的；

2. 头指针

   头指针是指指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针；

   无论链表是否为空，头指针均不为空。头指针是链表的必要元素；

链式存储结构

单链表

typedef int DateType;
//链表结点
typedef struct ListNode
{DateType date;struct ListNode* next;
}ListNode;

插入操作

尾插

思路：申请一个新节点newnode，判断单链表是否为空，若为空则直接插入*pplist=newnode，若不为空则寻找单链表的表尾(定义一个tail指针遍历链表，若tail->next=NULL则表示tail是单链表的表尾)再将新节点插入。

void ListPushBack(ListNode** pplist, DateType x)
{//申请空间，创建一个新结点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//数据域、指针域赋值newnode->date = x;newnode->next = NULL;//判断链表是否为空if (*pplist == NULL){*pplist = newnode;//若为空，则直接插入}else//若不为空，寻找链表位进行插入操作{//定义tail寻找链表尾ListNode* tail = *pplist;while (tail->next != NULL){tail = tail->next;}//尾部插入新结点tail->next = newnode;}
}

头插

思路：创建一个新节点newnode ，让newnode的next指向原来的单链表头ppList，ppList指向新创建的结点。

void ListPushFront(ListNode** pplist, DateType x)
{ //申请一个新节点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//数据域、指针域赋值newnode->date = x;newnode->next = NULL;//插入新节点newnode->next = *pplist;*pplist = newnode;}
}

删除操作

尾删

思路：定义两个指针，一个pre初始化为NULL用来在遍历时找到单链表的前一个结点，另一个tail初始化指向单链表的表头用来在遍历时找到单链表的表尾；判断单链表的结点个数，若单链表为空或者只有一个结点，则直接*pplist=NULL，若单链表有多个结点，则遍历找到表尾和表尾的前一个指针，将新的表尾置空，释放原来的表尾结点。

void ListPopBack(ListNode** pplist)
{//定义pre指向链表尾的前一个结点ListNode* pre = NULL;//定义tail寻找链表尾ListNode* tail = *pplist;//1.链表为空或者只有一个结点if (tail == NULL || tail->next == NULL){free(tail);*pplist = NULL;}else//2.链表有多个结点{while (tail->next != NULL){pre = tail;tail = tail->next;}//将新的表尾置空pre->next = NULL;//释放掉原来的表尾结点free(tail);}
}

头删

思路： 判断链表的结点个数，1、链表为空，直接return，2、链表只有一个结点，删除这个结点，将来链表置空，3、链表有个结点，定义一个指针next指向链表头结点的下一个结点，删除头结点，重新定义链表的头；

void ListPopFront(ListNode** pplist)
{ListNode* plist = *pplist;//1、空if (plist == NULL){return;}//2、只有一个结点else if (plist->next == NULL){free(plist);*pplist = NULL;}//3、正常情况else{ListNode* next = plist->next;free(plist);*pplist = next;}
}

查找操作

思路：按值查找，定义一个指针cur遍历单链表进行查找。

ListNode* ListFind(ListNode* plist, DateType x)
{ListNode* cur = plist;while (cur != NULL){if (cur->date == x ){return cur;}cur = cur->next;}return NULL;
}

循环链表

将单链表中终端节点的指针域由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)。

双向链表

双向链表(doouble linked list)实在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以再双向链表中有两个指针域，一个指向直接后继，一个指向直接前驱。

//带头结点双向循环链表
typedef int DataType;
typedef struct ListNode
{DataType data;//数据域struct ListNode* pre;//前驱指针域struct ListNode* next;//后继指针域
}ListNode;

插入操作

尾插

void ListPushBack(ListNode* phead, DataType x)
{//申请一个新节点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//数据域赋值newnode->data = x;//指针域赋值newnode->pre = NULL;newnode->next = NULL;//定义tail指针指向链表的表尾结点ListNode* tail = phead->pre;//插入tail->next = newnode;newnode->pre = tail;newnode->next = phead;phead->pre = newnode;
}

头插

void ListPushFront(ListNode* phead, DataType x)
{//申请一个新节点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//数据域赋值newnode->data = x;//指针域赋值newnode->pre = NULL;newnode->next = NULL;//定义head指针指向链表的头结点ListNode* head = phead->next;//插入phead->next = newnode;newnode->pre = phead;newnode->next = head;head->pre = newnode;
}

删除操作

尾删

void ListPopBack(ListNode* phead)
{//断言，链表若为空，则不删除assert(phead->next != phead);//tail指针指向链表的尾结点ListNode* tail = phead->pre;//prev指针指向尾结点的前一个结点ListNode* prev = tail->pre;//释放尾结点free(tail);//重新连接prev->next = phead;phead->pre = prev;
}

头删

void ListPopFront(ListNode* phead)
{//断言，链表若为空，则不删除assert(phead->next != phead);//定义first指针指向链表的头结点ListNode* first = phead->next;//定义second指针指向链表的头结点ListNode* second = first->next;//释放结点free(first);//重新建立连接phead->next = second;second->pre = phead;
}