链表的基本操作

链表

本文中主要分析以下几个链表：

不带头节点的单链表、带头节点的双向循环链表

链表：一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个节点

链表分类

1.单/双链表

2.带/不带头节点

3.循环/不循环链表

单链表

基本操作：初始化、销毁、插、删、查

在删除和插入中分：头删/插、尾删/插、正常删/插

• 定义结构体

typedef int DataType;

typedef struct ListNode
{
    DataType data;
    struct ListNode* next;
} ListNode;

• 初始化

void ListInit(ListNode **ppfirst)
{
    assert(*ppfirst!=NULL);
    *ppfirst = NULL;
}

• 销毁

void DestroyList(ListNode **ppfirst)
{
    ListNode *next = *ppfirst;
    for(ListNode *cur = *ppfirst;cur!=NULL;cur = next)
    {
        next = cur->next;
        free(cur);
    }
    *ppfirst = NULL;
}

• 创建节点

ListNode* CreatNode(DateType data)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    assert(newnode);
    node->data = data;
    node->next = NULL;
    
    return newnode;
}

• 插入

分析

正常情况：从堆上申请空间，更改ppfirst的值

特殊情况：*ppfirst == NULL

• 头插

void ListPushFront(ListNode **ppfirst, DataType data)
{
    assert(ppfirst != NULL);
    ListNode* node = CreatNode(data);
    node->next = *ppfirst;
    
    *ppfirst = node;
}

• 尾插（遍历链表）

void ListPushBack(ListNode **ppfirst, DataType data)
{
    ListNode* node = CreatNode(data);
    //特殊情况 链表为空
    if(*ppfirst == NULL)
    {
        *ppfirst = node;
        return;
    }
    //正常情况
    ListNode *cur = *ppfirst;
    while(cur != NULL)
    {
        cur = cur->next;
    }
    cur->next = node;
}

• 正常插入（中插）

分析

1. 如果要插入的位置是第一个节点—>调用头插
2. 找到要插入的位置的前一个节点，插入

void ListInsert(ListNode **ppfirst, ListNode *pos, DataType data)
{
    //pos是第一个节点
    if(*ppfirst == pos)
    {
        ListPushFront(ppfirst,data);
        return;
    }
    //找到pos前一个节点
    ListNode *cur = *ppfirst;
    while(cur->next != pos)
    {
        cur = cur->next;
    }
    ListNode *node = CreatNode(data);
    node->next = cur->next;
    cur->next = node;
}

• [ ] 删除

• 头删

分析

1. 变量地址不为空
2. 不能为空链表

void ListPopFront(ListNode **ppfirst)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    ListNode *del = *ppfirst;
    *ppfirst = del->next;
    free(del);
}

• 尾删

分析

1. cur->next->next == NULL
2. 特殊：只有一个节点

void ListPopBack(ListNode **ppfirst)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    //只有一个节点
    if((*ppfirst)->next == NULL)
    {
        free(*ppfirst);
        *ppfirst = NULL;
        return;
    }
    ListNode *cur = *ppfirst;
    ListNode *del;
    while(cur->next->next != NULL);
    {
        cur = cur->next;
    }
    del = cur->next;
    cur->next = NULL;
    free(del);
}

• 正常删除（中删）

分析

1. 当要删除的是第一个节点时—>头删
2. 先找到要删除的节点的前一个节点，然后删除

void ListEarse(ListNode **ppfirst, ListNode *pos)
{
    assert(ppfirst != NULL);
    assert(*ppfirst != NULL);
    if((*ppfirst)->next == pos)
    {
        ListPopFront(ppfirst);
        return;
    }
    ListNode *cur = *ppfirst;
    while(cur->next != pos)
    {
        cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
}

• 查找

分析

1. 遍历链表
2. 传值

ListNode* ListFind(ListNode* first, DataType data)
{
    assert(first);
    for(ListNode *cur = first; cur != NULL; cur = cur->next)
    {
        if(cur->data == data)
        {
            return cur;
        }
    }
    return NULL;
}

双向带头循环链表

基本操作：初始化、销毁（删除带头节点）、清空（保留带头节点）、插、删

在删除和插入中分：头删/插、尾删/插、正常删/插

• 定义结构体

typedef struct DListNode
{
	int data;
	struct DListNode *prev;
	struct DListNode *next;
} DListNode;

• 初始化
  

void DListInit(DListNode **ppHead)
{
    assert(ppHead != NULL);
    DListNode *pHead = (DListNOde*)malloc(sizeof(DListNode));
    pHead->prev = pHead;
    pHead->next = pHead;
    
    *ppHead = pHead;
}

• 清空链表

void DListClear(DListNode *pHead)
{
    DListNode *cur = pHead->next;
    DListNode *next;
    while(cur != pHead)
    {
        next = cur->next;
        free(cur);
    }
    pHead->next = pHead;
	pHead->prev = pHead;
}

• 销毁

void DListDestroy(DListNode **ppHead)
{
    assert(ppHead != NULL);
    DListClear(*ppHead);
    free(*ppHead);
    *ppHead = NULL;
}

• [ ] 插入

• 正常插入
  

void DListInsert(DListNode *pHead, DListNode *pos, int data)
{
    (void)pHead;//仅仅是为了防止编译警告
    DListNode *node = (DListNOde*)malloc(sizeof(DListNode));
    node->data = data;
    
    node->prev = pos->prev;
	node->next = pos;
	pos->prev->next = node;
	pos->prev = node;
}

• 头插

void DListPushFront(DListNode *pHead, int data)
{
    DListInsert(pHead, pHead->next, data);
}

• 尾插

void DListPushBack(DListNode *pHead, int data)
{
    DListInsert(pHead,pHead,data);
}

• [ ] 删除
  

• 正常删除

void DListErase(DListNode *pHead, DListNode *pos)
{
    (void)pHead;
    assert(pHead != NULL);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    
    free(pos);
}

• 头删

void DListPopFront(DListNode *pHead)
{
	DListErase(pHead,pHead->next);
}

• 尾删

void DListPopBack(DListNode *pHead)
{
	DListErase(pHead, pHead->prev);
}