链表、散列表

<ul> <li>链表是物理存储单元上非连续的、非顺序的存储结构，</li> <li>数据元素的逻辑顺序是通过链表的指针地址实现， <ul> <li>每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。</li> </ul></li> <li>根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 </li> </ul> <h2>优点</h2> <ul> <li>不需要初始化容量，可以任意加减元素； </li> <li>添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；</li> </ul> <h2>缺点</h2> <ul> <li>因为含有大量的指针域，占用空间较大； </li> <li>查找元素需要遍历链表来查找，非常耗时。</li> </ul> <h2>适用场景</h2> <ul> <li>数据量较小，需要频繁增加，删除操作的场景</li> </ul> <h2>散列表</h2> <ul> <li>散列表，也叫哈希表</li> <li>根据索引和值 (key和value) 直接访问的数据结构，通过key和value来映射到集合中的一个位置，可以很快找到集合中的对应元素。</li> <li> <p>记录的存储位置=f(key)，对应关系 f 成为散列函数，又称为哈希 (hash函数)，</p> </li> <li>把Key通过一个固定的算法函数(哈希函数)转换成一个整型数字，将该数字对数组长度进行取余，取余结果就当作数组的下标，</li> <li>将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，查找速度很快。</li> </ul> <h2>散列表优缺点</h2> <ul> <li>利用hash表的优势，对于集合的查找元素时非常方便的，</li> <li>哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，很多时候需要用到一种数组链表来做，也就是拉链法。 <ul> <li>拉链法是数组结合链表的一种结构</li> </ul></li> <li>哈希表的应用场景很多，也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。</li> </ul>