数据结构基础：单链表的概念与操作详解

数据结构基础：单链表的概念与操作详解

引用

CSDN

1.

https://blog.csdn.net/2301_80492355/article/details/142994755

前言

单链表（Singly Linked List）是一种常见的数据结构，用于存储一系列的元素，其中每个元素称为节点（Node）。在单链表中，每个节点包含两部分：一部分存储数据（data），另一部分存储指向下一个节点的指针（pointer 或 next）。

单链表的基本概念

1. 节点（Node）：

• 节点是单链表的基本单元。
• 每个节点包含两个部分：
• 数据域（data）：存储实际的数据。
• 指针域（next）：存储指向下一个节点的指针（如果当前节点是最后一个节点，则指针为 null 或 NULL）。

2. 头节点（Head Node）：

• 单链表通常有一个头节点，它指向链表的第一个实际数据节点（如果链表不为空）。
• 头节点本身不存储数据，也可以存储一个哨兵值（dummy value）或者作为链表操作的辅助。

3. 尾节点（Tail Node）：

• 链表的最后一个节点，其 next 指针为 null 或 NULL。

4. 链表长度（Length）：

• 链表中节点的数量。
• 通常通过一个额外的变量来维护链表的长度，以加快获取链表长度的操作。

5. 操作：

• 插入（Insert）：在链表的特定位置插入一个新节点。
• 删除（Delete）：删除链表中的某个节点。
• 查找（Search）：在链表中查找特定值的节点。
• 遍历（Traversal）：从头节点开始，依次访问链表中的每个节点。

6. 时间复杂度：

• 插入、删除和查找操作的时间复杂度通常为 O(n)，其中 n 是链表的长度。这是因为这些操作在最坏情况下需要遍历链表的一部分或全部节点。
• 遍历链表的时间复杂度为 O(n)。

7. 内存管理：

• 单链表使用动态内存分配来创建节点，因此在使用完毕后需要手动释放每个节点的内存，以避免内存泄漏。

单链表相比于数组，其优势在于插入和删除操作的时间复杂度较低（在已知位置的情况下），但劣势在于访问特定位置的节点需要从头节点开始遍历，不如数组那样高效。

单链表的基本操作

1. 初始化 O(1)

// 初始化 O(1)
Status InitList(LinkList& L)
{
    L = new LNode;
    L->next = NULL;
    return OK;
}

2. 销毁 O(n)

// 链表销毁 O(n),n为链表中数据节点的个数
Status DestroyLink(LinkList& L)
{
    LNode* pre = L;
    LNode* p = L->next;  //pre指向节点p的前驱节点
    while (p)
    {
        free(pre);  //释放pre节点
        pre = p;    //pre , p 同步向后移动一位
        p = pre->next;
    }
    //循环结束后，p为NULL,pre指向尾节点，释放它
    free(pre);
    return OK;
}

3. 判空 O(1)

// 判空 O(1)
Status ListEmpty(LinkList L)
{
    return(L->next == NULL);
}

4. 求表长 O(n)

// 求表长  O(n),n为链表中数据节点的个数
int ListLength(LinkList L)
{
    int n = 0;
    LNode* p = L->next;
    while (p)
    {
        n++;
        p = p->next;
    }
    return n;
}

5. 取值（按序号查找） O(n)

// 取值  O(n),n为链表中数据节点的个数
// 按照序号进行查找
Status GetElemLink(LinkList L, int i, ElemType& e)
{
    LNode* p = L->next;
    int j = 1;
    while (p && j < i)  //顺链表域向后查找，直到p为空或p指向第i个元素
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)  //i值不合法
    {
        return ERROR;  
    }
    else
    {
        e = p->data;  //用引用返回得到的参数数据
        return OK;
    }
}

6. 按值查找 O(n)

// 按照元素进行查找  O(n),n为链表中数据节点的个数
LNode* LocateElem(LinkList L, ElemType e)
{
    LNode* p;
    p = L->next;
    while (p && p->data != e)  //顺链表域向后查找，直到p为空或者p所指节点的数据域为e
    {
        p = p->next;
    }
    return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

7. 指定插入 O(n)

// 链表插入  O(n),n为链表中数据节点的个数
// 将e节点元素插入到i节点的前面，则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, ElemType e)
{
    LNode* p = L;
    int j = 0;
    while (p && j < i - 1)  //查找到第i-1个节点
    {
        ++j;
        p = p->next;
    }
    if (!p || j > i - 1)
    {
        return ERROR;
    }//该情况出现，即插入位置非法
    //循环结束后，已经移动到了i节点的前一个位置，进行尾插即可
    LNode* s = new LNode; //为即将要插入位置开辟一个结点
    s->data = e;
    s->next = p->next;//首先进行尾部连接
    p->next = s;//随后进行头部连接
    return OK;
}

8. 删除 O(n)

// 链表删除某个结点  O(n),n为链表中数据节点的个数
Status DeleteLink(LinkList& L, int i, ElemType e)
{
    LNode* p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }//循环结束后，p会指向要删除节点的前驱节点
    if (!(p->next) || j > i - 1)
    {
        return ERROR;
    }//要判断位置是否非法
    //进行删除
    LNode* q;
    q = p->next;    //临时保存被删除节点的地址以备后续释放
    p->next = q->next;  //改变被删除节点的前驱节点的指针域
    e = q->data;  //删除时拿出来被删除节点的数据
    delete q;
    return OK;
}

9. 输出链表

// 遍历打印链表  O(n),n为链表中数据节点的个数
void TraverseList(LinkList L)
{
    if (L == nullptr || L->next == nullptr) {
        cout << "链表为空" << endl;
        return;
    }
    LNode* p;
    p = L->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

10. 头插法 O(n)

// 头插法  O(n),n为链表中数据节点的个数
void CreatLink_F(LinkList& L, int n)
{
    L = new LNode;
    L->next = NULL;
    for (int i = 0; i < n; i++)
    {
        LNode* p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

11. 尾插法 O(n)

// 尾插法  O(n),n为链表中数据节点的个数
void CreatLink_L(LinkList& L, int n)
{
    L = new LNode;
    L->next = NULL;
    LNode* r = L;
    for (int i = 0; i < n; i++)
    {
        LNode* p = new LNode;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p; // 更新尾节点指针
    }
}

总结

单链表是一种基础且重要的数据结构，理解其基本概念和操作对于学习更复杂的数据结构和算法至关重要。通过本文的介绍和代码示例，读者应该能够掌握单链表的基本操作和实现细节。