初识链表
简介
链表应该是面试时被提及最频繁的数据结构。所谓链表其实就是把一组节点通过指针引用的方式串成一条链。
何为节点？
链表中的节点就相当于一串珍珠项链上的一颗颗珍珠。每一个节点包含数据data，和指向下一个节点的指针next
内存分布
链表是一种动态数据结构，内存分配不是在创建链表时一次性完成，而是每添加一个结点分配一次内存，然后调整节点中指针的指向来确保新结点被链接到链表当中，这一点是链表跟数组最大的不同点。
数组和链表的内存分布
链表分类
从链表的实现方式可以把链表分为单链表，双向链表，循环链表
单链表指的是链表中节点的指针只能指向链表中的下一个元素或者为空，节点之间不能相互指向。
双向链表每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个节点都有两种指针，即prev和next。prev指针指向前一个节点，next指针指向后一个节点。
循环链表指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。
比如下图中分别是单链表，双向链表和循环链表
优点和缺点
优点
上一节中，我们了解了数组的优势是随机访问查询效率较高，但是插入和删除操作的时间复杂度较高。链表与数组恰恰相反，在往链表中插入和删除节点时只需要改变被插入节点前后两个节点的指针指向即可。
将元素5插入到链表节点7的前面，只需要将节点3的next指针指向5，然后将5的指针指向节点7即可。
缺点
有得必有失，链表的访问操作就逊色很多。由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的，所以无法做到随机访问。
链表的遍历就犹如寻宝游戏。你前往第一个地址，那里有一张纸条写着“下一个元素的地址为123”。因此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”，以此类推。
内容小结
链表，跟数组一样，也是非常基础、非常常用的数据结构。不过链表要比数组稍微复杂，从普通的单链表衍生出来好几种链表结构，比如双向链表、循环链表。
和数组相比，链表更适合插入、删除操作频繁的场景。但是在链表中访问某元素的时间复杂度较高。
在下一节中，将会以单链表为举例，实现链表所包含的一些基本操作，以及面试中经常会考查到的链表操作。
按识别二维码，关注公众号