用python写单链表

链表的数据结构

链表是什么呢，来看下

链表，是一种数据结构。相对于数组而言，是不连续的一块内存空间。不仅如此，而且链表有多种，包括：单链表，双向链表，循环链表。这里先说下单链表。

单链表

单链表，由data数据域和next指针组成。简单点，就如下代码：

class Node:
    def __init__(self, data: int, nextNode: None):
        self._data = data
        self._nextNode = nextNode

操作

先说插入吧，插入分为几种情况，头插入，尾插入，中间任意位置插入。

头插入

代码如下：

尾插入

这个也比较简单，如下图：

中间插入

这个就比较复杂了，中间某个Node插入，分为2中情况， 这个位置的前边还是后边呢？接下来看代码，如下图，前边插入：

还有一种情况是后边插入，如下图：

插入就结束了。插入简单，但是查找费时。

删除

来看下删除操作吧，删除的操作代码如下：

时间复杂度：O(n)，这个主要浪费在查找上。

查找

代码如下：

时间复杂度O(n)

总结

总得来说，链表和数组相比，不是连续的内存空间，相对来说也复杂一点。插入操作和删除操作虽然比较效率高，但是时间耗费在查找上。查找的效率是O(n)。