【数据结构】链表(单链表与双链表实现+原理+源码)

简介: 【数据结构】链表(单链表与双链表实现+原理+源码)

一、链表定义

链表是一种数据结构,它由一系列节点组成,这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用(指针)。链表的最后一个节点通常指向一个特定的值(如空值或null),表示链表的结束。

链表是一种数据结构,它由一系列节点组成,这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用(指针)。链表的最后一个节点通常指向一个特定的值(如空值或null),表示链表的结束。

链表可以分为单链表和双链表两种主要类型:

1. 单链表(Singly Linked List):每个节点包含数据和指向下一个节点的指针。链表的最后一个节点指向null。

1. 节点1      节点2      节点3
2. | 数据1 | -> | 数据2 | -> | 数据3 | -> null

2. 双链表(Doubly Linked List):每个节点包含数据、指向下一个节点的指针,以及指向前一个节点的指针。这使得在双链表中可以更方便地进行前向和后向遍历。

null <- | 数据1 | <-> | 数据2 | <-> | 数据3 | -> null

链表优点:  链表相对于数组的优势在于插入和删除操作的效率较高,因为不需要移动大量元素,只需调整节点的指针。然而,链表的缺点是访问元素时需要按顺序遍历,而数组可以通过索引直接访问元素。链表在内存中不需要连续的存储空间,因此可以更灵活地分配内存。

二、链表实战

1、单链表(C语言实现版本)

#include <stdio.h>
#include <stdlib.h>
 
// 定义节点结构
struct Node {
    int data;           // 节点数据
    struct Node* next;  // 指向下一个节点的指针
};
 
// 定义链表结构
struct LinkedList {
    struct Node* head;   // 链表头指针
};
 
// 初始化链表
void initLinkedList(struct LinkedList* list) {
    list->head = NULL;  // 将头指针初始化为NULL,表示链表为空
}
 
// 在链表末尾添加节点
void append(struct LinkedList* list, int data) {
    // 创建新节点
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
 
    // 判断链表是否为空
    if (list->head == NULL) {
        // 如果为空,将新节点设为头节点
        list->head = new_node;
    } else {
        // 如果不为空,找到链表末尾,将新节点链接到末尾
        struct Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}
 
// 在链表开头添加节点
void prepend(struct LinkedList* list, int data) {
    // 创建新节点
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = list->head;
 
    // 将新节点设为头节点
    list->head = new_node;
}
 
// 删除节点
void deleteNode(struct LinkedList* list, int data) {
    struct Node* current = list->head;
    struct Node* prev = NULL;
 
    // 遍历链表,找到待删除节点及其前一个节点
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }
 
    // 如果找到待删除节点
    if (current != NULL) {
        // 如果待删除节点不是头节点
        if (prev != NULL) {
            prev->next = current->next;
        } else {
            // 如果待删除节点是头节点
            list->head = current->next;
        }
        free(current);  // 释放内存
    }
}
 
// 更新节点
void updateNode(struct LinkedList* list, int oldData, int newData) {
    struct Node* current = list->head;
 
    // 遍历链表,找到待更新节点
    while (current != NULL && current->data != oldData) {
        current = current->next;
    }
 
    // 如果找到待更新节点
    if (current != NULL) {
        current->data = newData;  // 更新节点数据
    }
}
 
// 搜索节点
struct Node* searchNode(struct LinkedList* list, int data) {
    struct Node* current = list->head;
 
    // 遍历链表,找到包含指定数据的节点
    while (current != NULL && current->data != data) {
        current = current->next;
    }
 
    return current;  // 返回节点指针
}
 
// 显示链表内容
void display(struct LinkedList* list) {
    struct Node* current = list->head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
 
// 释放链表内存
void freeLinkedList(struct LinkedList* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
}
 
int main() {
    struct LinkedList myLinkedList;
    initLinkedList(&myLinkedList);
 
    // 添加节点
    append(&myLinkedList, 1);
    append(&myLinkedList, 2);
    append(&myLinkedList, 3);
 
    // 显示链表内容
    printf("链表内容:");
    display(&myLinkedList);
 
    // 在开头添加节点
    prepend(&myLinkedList, 0);
 
    // 显示链表内容
    printf("在开头添加节点后的链表:");
    display(&myLinkedList);
 
    // 删除节点
    deleteNode(&myLinkedList, 2);
 
    // 显示链表内容
    printf("删除节点后的链表:");
    display(&myLinkedList);
 
    // 更新节点
    updateNode(&myLinkedList, 1, 10);
 
    // 显示链表内容
    printf("更新节点后的链表:");
    display(&myLinkedList);
 
    // 搜索节点
    int searchData = 10;
    struct Node* searchResult = searchNode(&myLinkedList, searchData);
    if (searchResult != NULL) {
        printf("找到数据为 %d 的节点。\n", searchData);
    } else {
        printf("未找到数据为 %d 的节点。\n", searchData);
    }
 
    // 释放链表内存
    freeLinkedList(&myLinkedList);
 
    return 0;
}

执行结果详细:

2、双链表(C++)

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
  
using namespace std;  
typedef struct Node  
{  
    int data;  
    struct Node *prior;  
    struct Node *next;  
} LinkList;  
  
LinkList *Create()  
{  
    LinkList *head;  
    head=(LinkList*)malloc(sizeof(LinkList));  
    if(head!=NULL)  
    {  
        head->prior=NULL;  
        head->next=NULL;  
        return head;  
    }  
    else return NULL;  
}  
  
int Insert(LinkList *head,int e)  //尾插法
{  
    LinkList *p;  
    LinkList *q=head;  
    p=(LinkList*)malloc(sizeof(LinkList));  
    if(p!=NULL)  
    {  
        p->data=e;  
        p->prior=NULL;  
        p->next=NULL;  
        while(q->next!=NULL)  
        {  
            q=q->next;  
        }  
        q->next=p;  
        return 1;  
    }  
    return 0;  
}  
  
LinkList* Change(LinkList *head) //变成双向链表后返回一个尾指针  
{  
    LinkList *p,*q;  
    p=head;  
    q=p->next;  
    while(q!=NULL)  
    {  
        q->prior=p;  
        p=p->next;  
        q=q->next;  
    }  
    return p;  
}  
  
void Output1(LinkList *head) //从头到尾遍历输出  
{  
    LinkList *p;  
    p=head->next;  
    while(p!=NULL)  
    {  
        printf("%d ",p->data);  
        p=p->next;  
    }  
    printf("\n");  
}  
  
void Output2(LinkList *tail) //从尾到头遍历输出  
{  
    LinkList *p;  
    p=tail;  
    while(p->prior!=NULL)  
    {  
        printf("%d ",p->data);  
        p=p->prior;  
    }  
    printf("\n");  
}  
  
void FreeLink(LinkList *head)  //释放
{  
    LinkList *p,*q;  
    p=head;  
    q=NULL;  
    while(p!=NULL)  
    {  
        q=p;  
        p=p->next;  
        free(q);  
    }  
}  
  
int main()  
{  
    LinkList *phead,*tail;  
    int n,e,flag;  
    phead=Create();  
    if(phead!=NULL)  
    {  
        cout<<"请输入长度:";
 scanf("%d",&n);  
        for(int i=0;i<n;i++)  
        {  
            scanf("%d",&e);  
            flag=Insert(phead,e);  
        }
 cout<<"从头到尾输出为: ";
        Output1(phead);  
        tail=Change(phead); 
 cout<<"从尾到头输出为: ";
        Output2(tail);  
        FreeLink(phead);  
    }  
    return 0;  
}

代码执行结果:

三、分析总结

链表是一种常见的数据结构,具有一些优点和应用:

优点:

1. 动态内存分配:链表允许在运行时动态分配内存,这使得它更加灵活,不需要预先指定存储空间大小,通过动态分配内存可以实现降低时间运行成本。

2. 插入和删除效率高:在链表中插入和删除节点相对容易且效率较高。相比之下,数组在中间或开头插入/删除元素可能需要移动大量元素。

3. 大小可变:*链表可以根据需要动态增长或缩小,而不浪费内存。

应用:

1. 实现动态数据结构:链表常用于实现其他动态数据结构,如栈、队列、图等。

2. 内存分配:动态链表的能力使其在动态内存分配的场景中非常有用,例如,动态分配内存的链表可用于管理操作系统的进程列表。

3. 实现算法:链表常用于算法实现,例如,链表在排序算法、图算法等方面有广泛的应用。

4. 嵌入式系统: 在资源受限的嵌入式系统中,链表可以更好地处理动态数据。

5. LRU缓存淘汰算法:链表可以用于实现LRU(Least Recently Used)缓存淘汰算法,用于管理缓存中的数据。

6. 数据库:数据库中的索引通常使用链表实现,以支持高效的插入和删除操作。

总的来说,链表在许多场景中都是一种强大且灵活的数据结构,特别适合那些需要频繁插入和删除操作的应用。

小结

大家点赞、收藏、关注、评论啦 !

谢谢哦!如果不懂,欢迎大家下方讨论学习哦。


相关文章
|
1天前
|
存储
【数据结构】带头+双向+循环链表(DList)(增、删、查、改)详解
【数据结构】带头+双向+循环链表(DList)(增、删、查、改)详解
|
1天前
|
存储 安全 C++
【数据结构】无头+单向+非循环链表(SList)(增、删、查、改)详解
【数据结构】无头+单向+非循环链表(SList)(增、删、查、改)详解
|
2天前
|
存储 缓存 算法
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(下)
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现
4 0
|
2天前
|
存储 算法
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(上)
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现
10 0
|
2天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
5 0
|
7天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
7天前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
|
7天前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
7天前
|
算法 安全 数据处理
LeetCode刷题---707. 设计链表(双向链表-带头尾双结点)
LeetCode刷题---707. 设计链表(双向链表-带头尾双结点)
|
7天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
11 0