链表（一）

2019-08-17 本文已影响0人小董不太懂

上个笔记我们讨论了列表扩容的问题，是必须要将列表扩充固定数目或者加倍吧。那么我们有没有可能往列表里加一个数据，我们就扩容一个数据，不再额外扩充浪费空间的这种数据结构存在呢？

如上图所示，比如我们先建立一个li的空列表，然后依次加入200,400,600这三个元素，每一个元素依次指向下一次元素，犹如被一根线串起来的，是不是我们就可以实现上述的数据结构了，当然这只是简单的一维链表，后面我们会继续介绍更多的也会更加复杂的链表结构，比如树图等。
这就引入了一个新的概念。

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

我们先来了解一下python中关于地址的概念：
我们先来思考一下，如何实现交换两个变量，是不是只要这样就可以了：

那我们有没有探究过它的本质呢？

看到这张图，我们会感觉诧异，为什么a不是内存的标号，而是一块新的内存呢，这就是python与其他语言的不同之处，a代表了一块新的内存且这块内存指向我们等号右边的元素。

第三步a,b赋值操作 在python中变量名就只是变量名，并不保存实际元素，而是保存实际元素所在的地址，从而指向这个元素

我们再看一个例子
这个例子更加印证了变量a只是个名字，存储的是指向等号右边元素的地址。

  """单链表的结点"""
   def __init__(self,item):
      # _item存放数据元素
     self.item = item
    # _next是下一个节点的标识
  self.next = None

我们根据图再来理解一下上面那一段代码的意思，表示节点是不是需要定义一个类，然后是node1和node2，node1保留了指向node2的地址，并不是说node1包含node2而是node1指向node2，并且node1和node2是两块分开的内存，但通过next串连起来了。