链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针（或引用）。链表在内存中不需要连续存储，这使得它在插入和删除操作上非常高效。链表的基本结构包括数据部分和指针部分，数据部分存储实际的数据，指针部分指向链表中下一个节点的地址。
链表有以下几种常见变体：
单向链表：每个节点只指向下一个节点。
双向链表：每个节点包含两个指针，分别指向前一个和后一个节点。
循环链表：尾节点的指针指向头节点，形成一个环。
链表相对于数组的优势在于其动态内存分配，允许在运行时添加或删除节点，但访问特定位置的元素需要遍历链表，因此访问时间复杂度为O（n）。链表的空间开销相对较大，因为每个节点都需要额外的空间来存储指针