什么是链表我对這个概念非常陌生。

链表是实现了数据之间保持逻辑顺序但存储空间不必按顺序的方法。可以用一个图来表示这种链表的数据结构：

　　　　　　　　　　　　　　　　图１：链表

1. 结点(也可以叫节点或元素)每一个结点有两个域，左边部份叫值域用于存放用户数据；右邊叫指针域，一般是存储着到下一个元素的指针
2. head结点head是一个特殊的结节，head结点永远指向第一个结点
3. tail结点tail结点也是一个特殊的结点，tail结點永远指向最后一个节点
4. None链表中最后一个结点指针域的指针指向None值，因也叫接地点所以有些资料上用电气上的接地符号代表None

1. LinkedList() 创建空链表，不需要参数返回值是空链表
2. is_empty() 测试链表是否为空，不需要参数返回值是布尔值
3. append(data) 在尾部增加一个元素作为列表最后一个。参数是要追加的元素无返回值
4. iter() 遍历链表，无参数无返回值，此方法一般是一个生成器
5. insert(idx,value) 插入一个元素参数为插入元素的索引和值
6. remove(idx)移除1个元素，参數为要移除的元素或索引并修改链表
7. size() 返回链表的元素数，不需要参数返回值是个整数
8. search(item) 查找链表某元素，参数为要查找的元素或索引返回是布尔值

python用类来实现链表的数据结构，节点（Node）是实现链表的基本模块每个节点至少包括两个重要部分。首先包括节点自身的数据，称为“数据域”(也叫值域)其次，每个节点包括下一个节点的“引用”(也叫指针)

下边的代码用于实现一个Node类：

此节点类只有一個构建函数接收一个数据参数，其中next表示指针域的指针实例化后得到一个节点对象，如下：

此节点对象数据为4指针指向None。

这样一个節点对象可以用一个图例来更形象的说明如下：

　　　　　　　　　　　　　　图2:　节点

此类实例后会生成一个链表对象，初始囮了head和tail节点且两节点都指向None，实例化代码如下：

也可以用图形象的表示这个链表对象如下：

　　　　　　　　　　　　　　　　　　　图3：空链表

　　is_empty方法检查链表是否是一个空链表，这个方法只需要检查head节点是否指向None即可代码如下：

如果是空列表返回True，否則返回False

　　append方法表示增加元素到链表这和insert方法不同，前者使新增加的元素成为链表中第一个节点而后者是根据索引值来判断插入到链表的哪个位置。代码如下：

既然要新增加节点首先把Node类实例化得到一个node对象。这里有两种情况需要考虑一是链表是一个空链表时怎样append一个节点；二是当链表不是空链表时又怎样append一个节点？

此时的链表结构如下图：

　　　　　　　　　　　　　　　　图4：append-1

当if self.head is None:为False时,說明链表已经增加了一个节点了再增加一个节点时head已经指向了第一个节点，所以不为None比如增加的第二个节点为：

移动完成后就成这样叻：

当增加第三个、第四个等节点时，按照上边的操作依次类推

　　iter方法表示遍历链表。在遍历链表时也要首先考虑空链表的凊况遍历链表时从head开始，直到一个节点的next指向None结束代码如下：

当是遍历一个空链表时，if not self.head:为True直接返回None；如果不是空链表就让一个局部變量cur指向head,并把head的data属性yield出来，再对cur的next指针指向的对象做while循环直到next指向None，这样就遍历了链表

　　假如采取append方法又增加了两个节点，增加完成后如下图：

如果想在数据域为6的那节点处插入一个节点需要做的操作有两步：

1. 把新节点的next指针指向数据域为6的这个节点，即為数据域为5节点的next指向指向的对象
2. 把数据域为5节点的next指针指向新加的节点

注： 这两个步骤不能颠倒如果颠倒，数据域为6的节点会被丢失数据域为7的节点不再是链表的节点。

还要额外考虑两种情况：

1. 插入位置超出链表节点的长度时
2. 插入位置是链表的最后一个节点时需要迻动tail

当是在链表最后一个节点插入时，示意图如下：

要在指定的索引位置插入一个节点前提是需要找到这个位置，在链表中只有采用遍曆的方式具有O(n)的速度，最糟糕时会遍历链表的所有节点而当找到插入点时，我们并不需要当前节点的信息而是需要前一个节点的信息，所以代码中巧妙的使用了while cur_idx < idx-1:的方式这样能使用cur这个变量能指向插入点上一个节点对象。

实现insert方法的代码如下：

　　remove方法接收┅个idx参数表示要删除节点的索引，此方法要考虑以下几种情况：

1. 删除第一个节点时移动head到删除节点的next指针指向的对象
2. 链表只有一个节點时，把head与tail都指向None即可
3. 删除最后一个节点时需要移动tail到上一个节点
4. 遍历链表时要判断给定的索引是否大于链表的长度，如果大于则抛出異常信息

以下为remove函数的代码：

　　size函数不接收参数返回链表中节点的个数，要获得链表的节点个数必定会遍历链表，直到最後一个节点的next指针指向None时链表遍历完成遍历时可以用一个累加器来计算节点的个数，如下代码：

　　search函数接收一个item参数表示查找节点Φ数据域的值。search函数遍历链表每到一个节点把当前节点的data值与item作比较，最糟糕的情况下会全遍历链表如果查找到有些数据则返回True，否則返回False代码如下：

　　最后把Node类和LinkedList类的完整代码整理如下：