单链表(具体接口实现)-白红宇

单链表(具体接口实现)

阅读量：282 次

发布时间：2019-03-01

本文共 2872 字，大约阅读时间需要 9 分钟。

链表是一种数据存储结构，它通过指针将数据元素按逻辑顺序连接起来。与数组不同，链表并不需要连续的物理空间，数据元素可以分布在内存的不同位置。这种结构使得链表在某些场景下比数组更为灵活。

链表的分类

链表的分类可以从几个方面进行：单向或双向、带头或不带头、循环或非循环。其中，单链表是我们今天主要关注的对象，它是一种单向、不带头、非循环的链表结构。

单链表的接口实现

单链表的实现通常包括以下几个基本操作：

动态申请结点：

通过malloc函数分配内存，创建一个新的链表节点。

SListNode* BuySListNode(SLTDataType x) {
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL) {
        printf("malloc node fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

链表打印：

遍历链表，从头节点开始依次打印每个节点的数据。

void SListPrint(SListNode* phead) {
    SListNode* cur = phead;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

尾插操作：

动态申请一个新节点，将其添加到链表的最后一个节点的后面。

void SListPushBack(SListNode** phead, SLTDataType x) {
    SListNode* newnode = BuySListNode(x);
    if (*phead == NULL) {
        *phead = newnode;
    } else {
        SListNode* tail = *phead;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

头插操作：

动态申请新节点，将其作为链表的新头节点。

void SListPushFront(SListNode** phead, SLTDataType x) {
    SListNode* newnode = BuySListNode(x);
    if (*phead == NULL) {
        *phead = newnode;
    } else {
        *phead = newnode;
    }
}

头删操作：

删除链表的第一个节点，并释放内存。

void SListPopFront(SListNode** phead) {
    if (*phead == NULL) {
        return;
    } else if ((*phead)->next == NULL) {
        free(*phead);
        *phead = NULL;
    } else {
        SListNode* next = (*phead)->next;
        free(*phead);
        *phead = next;
    }
}

尾删操作：

删除链表的最后一个节点，并释放内存。

void SListPopBack(SListNode** phead) {
    if (*phead == NULL) {
        return;
    } else if ((*phead)->next == NULL) {
        free(*phead);
        *phead = NULL;
    } else {
        SListNode* prev = NULL;
        SListNode* tail = *phead;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

插入操作：

在指定位置之后插入一个新节点。

void SListInsertAfter(SListNode* pos, SLTDataType x) {
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

删除操作：

删除指定位置之后的所有节点。

void SListEraseAfter(SListNode* pos) {
    if (pos->next == NULL) {
        return;
    }
    SListNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    posNext = NULL;
}

查找操作：

遍历链表，找到指定值的节点。

SListNode* SListFind(SListNode* plist, SLTDataType x) {
    SListNode* head = plist;
    while (head != NULL) {
        if (head->data == x) {
            return head;
        }
        head = head->next;
    }
    return NULL;
}

链表与顺序表的对比

链表和顺序表各有优缺点：

对比项	链表	顺序表
存储空间	不连续，灵活	连续，效率更高
插入删除	时间复杂度O(1)，空间O(1)	时间复杂度O(n)，空间O(1)
随机访问	不支持，需从头节点开始遍历	支持，直接通过索引访问
缓存命中率	较低	较高

链表的灵活性和动态性使其在某些场景下更具优势，但其缺乏随机访问能力和较低的缓存命中率也需要在实际应用中权衡考虑。

转载地址：http://gkso.baihongyu.com/

你可能感兴趣的文章