2024/11/24 链表

链表

1.类型

（1）单链表

（2）双链表

（3）循环链表

2.链表在内存的存储方式

　　数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

　　链表是通过指针域的指针链接在内存中各个节点。

3.链表的定义

　　定义链表节点方式

Python:

class ListNode:
    def __init__(self, val, next=None):
            self.val = val
            self.next = next

C++

//单链表
struct ListNode{
    int val; //节点上存储的元素
    ListNode *next; //指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} //节点的构造函数
};

4.链表的操作

（1)删除节点

　　删除节点后，C++中最后再手动释放该节点，从而释放这块内容。

　　Java语言，Python语言，有自己的内存回收机制，不需要手动释放。

　　链表的增添和删除都是O(1)操作，但是删除最后一个节点，时间复杂度是O(n)

（2）增加节点

4’链表与数组的比较

　　数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

　　链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。