链表篇

上学期就自己看了一遍大话数据结构，也记录了一些链表的内容，趁着刷题巩固一下自己所学知识。


链表

是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

根据指针的指向，链表能形成不同的结构，例如

单链表，双向链表，循环链表

等。

缺点：

1. 因为含有大量的指针域，占用空间较大；
2. 查找元素需要遍历链表来查找，非常耗时。

适用场景：

数据量较小，需要频繁增加，删除操作的场景

链表的增删操作

• 
  直接使用原来的链表来进行删除操作。
  
• 
  设置一个虚拟头结点在进行删除操作。
  

- ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点

链表思维导图借鉴如下