2.2 链表

内存空间是所有程序的公共资源,在一个复杂的系统运行环境下,空闲的内存空间可能散落在内存各处.我们知道,存储数组的内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间.此时链表的灵活性优势就体现出来了.

链表(linked list) 是一种线性数据结构,其中的每个元素都是一个节点对象,各个节点通过“引用”相连接.引用记录了下一个节点的内存地址,通过它可以从当前节点访问到下一个节点.

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

观察图2-2-1,链表的组成单位是节点（node）对象.每个节点都包含两项数据:

data: 数据域,也是节点的值
next: 指针域,指向下一个节点的指针

如以下代码所示，链表节点 ListNodec 除了包含值,还需额外保存一个引用（指针）.因此在相同数据量下,链表比数组占用更多的内存空间 .

CC++PythonJava

/* 链表节点结构体 */
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode *next; // 指向下一节点的指针
} ListNode;

/* 构造函数 */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

/* 链表节点结构体 */
struct ListNode {
    int val;         // 节点值
    ListNode *next;  // 指向下一节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

class ListNode:
"""链表节点类"""
def __init__(self, val: int):
    self.val: int = val               # 节点值
    self.next: ListNode | None = None # 指向下一节点的引用

/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

链表中的一些概念

头节点

在单链表的开始结点之前设立一个节点称之为头结点(也称为哨兵节点或哑节点),头结点的数据域可以不存储任何信息,也可以存储链表的长度等附加信息,头结点的指针域存储指向第一个结点(首元结点)的指针。

头指针

头指针是指链表中,指向第一个结点的指针.

头指针具有标识作用,所以常常会用头指针冠以链表的名字.所以你定义一个链表,那么链表的名字一般就是这个链表的头指针.

ListNode L = new ListNode(0); 左边的是指针和结点

无论链表是否为空,头指针均不为空,头指针是链表的必要元素.

首元节点

链表中第一个元素所在的结点,它是头结点后边的第一个结点.如果是带头结点的链表,则头结点后面的为首元结点.

元素是指链表中实际存储数据的结点,像头结点就不属于元素,因为它存储的不是数据,而是一些链表的属性信息(链表长度)或者为空.

整理成一句话就是

头指针: 指向第一个节点
头节点: 在首元结点前面设立的一个结点
首元结点: 链表中第一个元素所在的结点
元素结点: 存储链表实际信息的结点

单链表(带头结点)

下面以带头节点的单链表为例展示以下6种函数的实现

按值查找节点
按位序插入节点
按位序删除节点
头插法创建链表
尾插法创建链表

1 链表初始化

建立链表分为两步,第一步是初始化各个节点对象,第二步是构建节点之间的引用关系.初始化完成后,我们就可以从链表的头节点出发,通过引用指向next依次访问所有节点.

CC++PythonJava

linked_list.c
/* 先定义一个带头节点的单链表 */
typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素
    struct LNode *next;         //指针指向下一个节点
}LNode, *LinkList;              //LNode 是节点类型，LinkList是指向LNode这种节点的指针类型


// 初始化一个单链表(带头结点)
bool InitList(LinkList &L){
    L = (LNode * ) malloc(sizeof(LNode));   //分配一个头节点
    if(L == NULL)                           //  内存不足，分配失败
        return false;
    L->next = NULL;                         //头节点之后暂时还没有节点
    return true;
}

linked_list.cpp
/* 先定义一个带头节点的单链表 */
typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素
    struct LNode *next;         //指针指向下一个节点
}LNode, *LinkList;              //LNode 是节点类型，LinkList是指向LNode这种节点的指针类型


// 初始化一个单链表(带头结点)
bool InitList(LinkList &L){
    L = (LNode * ) malloc(sizeof(LNode));   //分配一个头节点
    if(L == NULL)                           //  内存不足，分配失败
        return false;
    L->next = NULL;                         //头节点之后暂时还没有节点
    return true;
}

linked_list.py
# TODO

linked_list.java
/* TODO */

可视化运行

【全屏观看】

2 链表插入节点(按位序插入)

在链表中插入节点非常容易.如图2-2-2所示,假设我们想在相邻的两个节点n0 和 n1 之间插入一个新节点 P ,则只需改变两个节点引用（指针）即可，时间复杂度为 O(1) .

相比之下，在数组中插入元素的时间复杂度为O(n),在大数据量下的效率较低.

CC++PythonJava

linked_list.c
//在第 i 个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i < 1)
        return false;
    LNode *p;                       //指针p指向当前扫描到的节点
    int j = 0;                      //当前p指向的是第几个节点
    p = L;                          //L指向头节点，头节点是第0个节点(不存数据)

    //寻找第 i-1 个节点
    while(p != NULL && j < i-1){    //循环找到第 i-1 个节点
        p = p->next;
        j++;
    }

    if(p == NULL)                   //i值不合法
        return false;

    //新建一个节点并赋值要插入的数据e
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;

    //开始插入
    s->next = p->next;              //先将新节点的next指向第 i 个节点
    p->next = s;                    //将节点s连接到p之后

    return true;                    //插入成功
}

linked_list.cpp
//在第 i 个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i < 1)
        return false;
    LNode *p;                       //指针p指向当前扫描到的节点
    int j = 0;                      //当前p指向的是第几个节点
    p = L;                          //L指向头节点，头节点是第0个节点(不存数据)

    //寻找第 i-1 个节点
    while(p != NULL && j < i-1){    //循环找到第 i-1 个节点
        p = p->next;
        j++;
    }

    if(p == NULL)                   //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;              //先将新节点的next指向第 i 个节点
    p->next = s;                    //将节点s连接到p之后

    return true;                    //插入成功
}

linked_list.py
# TODO

linked_list.java
/* TODO */

可视化运行

【全屏观看】

3 链表删除节点

如图 2-2-3 所示,在链表中删除节点也非常方便,只需改变一个节点的引用（指针）即可。

Info

请注意,尽管在删除操作完成后节点 P 仍然指向 n1,但实际上遍历此链表已经无法访问到 P ,这意味着 P 已经不再属于该链表了。

CC++PythonJava

linked_list.c
// 按位序删除，i=1删表头，i=length删头尾
bool List_Del (LinkList &L, int i, ElemType &e) {           //删除时返回删除的元素
    if (i < 1 || i > List_Length(pHead)) return false;      //删除位置不合法
    LNode *p;                                               //指针p指向当前扫描到的节点
    int j = 0;                                              //当前p指向的第几个节点
    p = L;                                                  //L和p相同，都指向头节点

    //寻找第 i-1 个节点
    while(p != NULL && j < i-1){                            //循环找到第 i-1 个节点
        p = p->next;
        j++;
    }

    LNode *q = p->next;                                     // q指向待删除结点
    e = q->data;                                            //返回即将删除的数据
    p->next = q->next;                                      // 将q节点从链中“断开”
    free(q);                                                //释放节点的存储空间
    return true;                                            //删除成功
}

linked_list.cpp
// 按位序删除，i=1删表头，i=length删头尾
bool List_Del (LinkList &L, int i, ElemType &e) {           //删除时返回删除的元素
    if (i < 1 || i > List_Length(pHead)) return false;      //删除位置不合法
    LNode *p;                                               //指针p指向当前扫描到的节点
    int j = 0;                                              //当前p指向的第几个节点
    p = L;                                                  //L和p相同，都指向头节点

    //寻找第 i-1 个节点
    while(p != NULL && j < i-1){                            //循环找到第 i-1 个节点
        p = p->next;
        j++;
    }

    LNode *q = p->next;                                     // q指向待删除结点
    e = q->data;                                            //返回即将删除的数据
    p->next = q->next;                                      // 将q节点从链中“断开”
    free(q);                                                //释放节点的存储空间
    return true;                                            //删除成功
}

linked_list.py
# TODO

linked_list.java
/* TODO */

4 访问节点

在链表中访问节点的效率较低.如上一节所述,我们可以在O(1)时间下访问数组中的任意元素.链表则不然,程序需要从头节点出发,逐个向后遍历,直至找到目标节点.也就是说,访问链表的第i个节点需要循环i - 1>轮,时间复杂度为O(n).

CC++PythonJava

linked_list.c
/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
        return NULL;
        head = head->next;
    }
    return head;
}

linked_list.cpp
/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    delete P;
}

linked_list.py
def access(head: ListNode, index: int) -> ListNode | None:
"""访问链表中索引为 index 的节点"""
for _ in range(index):
    if not head:
        return None
    head = head.next
return head

linked_list.java
/* 访问链表中索引为 index 的节点 */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

5 查找节点

遍历链表,查找其中值为 target 的节点,输出该节点在链表中的索引.此过程也属于线性查找.代码如下所示:

CC++PythonJava

linked_list.c
/* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.cpp
/* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.py
def find(head: ListNode, target: int) -> int:
"""在链表中查找值为 target 的首个节点"""
index = 0
while head:
    if head.val == target:
        return index
    head = head.next
    index += 1
return -1

linked_list.java
/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

6 尾插法 - 建立单链表

下面展示通过尾插法创建一个链表。

尾插法的特点是每插入一个新节点,链表的尾节点指针(pTail)会更新为新插入的节点,使其始终指向当前链表的尾结点。从而使得输入的数据在链表中按顺序存储>。当输入数据为 999 时，循环结束，将尾节点的 next 指针置为 NULL 表示链表结束，函数返回最终的链表头节点。

CC++

linked_list.c
// 创建链表-通过尾插法
LinkList List_Create_Tail_Insert(LinkList &pHead) {
LNode *pTemp; // 临时节点指针
LNode *pTail = pHead; // 尾节点指针，初始指向头结点
int x; // 用于存储输入的数据
scanf("%d", &x);
while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x; // 尾节点的下一个指针指向新节点
    pTail->next = pTemp; // 更新尾节点指针，使其指向新节点
    pTail = pTemp; // 读取下一个数据
    scanf("%d", &x);
}
pTail->next = NULL; // 尾节点的下一个指针置为 NULL，表示链表结束
return pHead; // 返回带头结点的链表头指针
}

linked_list.cpp
// 创建链表-通过尾插法
LinkList List_Create_Tail_Insert(LinkList &pHead) {
LNode *pTemp; // 临时节点指针
LNode *pTail = pHead; // 尾节点指针，初始指向头结点
int x; // 用于存储输入的数据
scanf("%d", &x);
while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x; // 尾节点的下一个指针指向新节点
    pTail->next = pTemp; // 更新尾节点指针，使其指向新节点
    pTail = pTemp; // 读取下一个数据
    scanf("%d", &x);
}
pTail->next = NULL; // 尾节点的下一个指针置为 NULL，表示链表结束
return pHead; // 返回带头结点的链表头指针
}

7 头插法 - 建立单链表

下面展示通过尾插法创建一个链表。

请注意

头插法结果为倒叙

该代码通过头插法创建一个链表. 头插法的特点是每插入一个新节点,链表的头节点就会变成新插入的节点,从而使得输入的数据在链表中是倒序存储>的. 当输入数据为 999 时，创建链表的循环结束,函数返回最终的链表头节点.

CC++

linked_list.c
// 创建链表，头插法结果为倒叙
LinkList List_Create(LinkList &pHead) {
LNode *pTemp; int x; // 临时节点指针
scanf("%d", &x);
while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x;
    pTemp->next = pHead->next; // 新节点的指针指向当前头节点的下一个节点
    pHead->next = pTemp; // 头指针指向新节点，使其成为新的头节点
    scanf("%d", &x);
}
return pHead; // 返回带头结点的链表头指针
}

linked_list.cpp
// 创建链表，头插法结果为倒叙
LinkList List_Create(LinkList &pHead) {
LNode *pTemp; int x; // 临时节点指针
scanf("%d", &x);
while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x;
    pTemp->next = pHead->next; // 新节点的指针指向当前头节点的下一个节点
    pHead->next = pTemp; // 头指针指向新节点，使其成为新的头节点
    scanf("%d", &x);
}
return pHead; // 返回带头结点的链表头指针
}

2.2 链表

链表中的一些概念

头节点

头指针

首元节点

单链表(带头结点)

1 链表初始化

2 链表插入节点(按位序插入)

3 链表删除节点

4 访问节点

5 查找节点

6 尾插法 - 建立单链表

7 头插法 - 建立单链表

评论