什么是单链表

在讨论单链表之前，先了解下什么是节点。因为节点是链表的构成要素。节点由两部分组成：

1.数据部分--包含数据

2.地址部分--指向下一节点的指针

在单链表中，每一个节点的地址部分包含下一节点位置的信息。这就构成一组链。链表的第一个节点由头指针跟踪。最后一个节点指向None。

看看下面的图有助于更好地理解：

在这上图中，最后一个元素1指向None。虽然此图中每一个节点都是彼此引连着画的，但实际上，它们可能位于相连的内存地址中，也可能不在相连的内存地址中。

如何创建单链表？

创建类

要创建单链表，首先要创建节点。要创建节点，我们先创建一个类Node，此类有data和nextNode属性。data属性包含数据，nextNode只是指向此链表中的下一个节点。把nextNode的默认值设为None。可以使用getter和setter方法来实现。

创建完Node类，就可以创建LinkedList类了。它只有一个属性，head。默认情况下，它指向None。如果head指向None，表明此链表为空。要跟踪此链表中的节点数，可以向LinkedList类添加一个size属性，并将其默认值设为0

插入节点

这是LinkedList类的方法。为了让代码简单、高效，这里总向链表的开头添加新节点。如果向链表末尾添加新节点，需要做些额外的工作，去找到链表的末尾，然后添加此节点。此操作年似有点多余。但如果同时还维护着另一个指针（我们称其为尾指针，它指向链表的最后一个节点），这时就需要此尾指针来完成。可以在链表的任何位置插入新节点。但前面已经提到的方法是在链表的开始处插入节点。

假设需要在一个链表中插入7，则需要以下步骤：

创建一个节点对象，7作为其数据，下一节点指向头节点

将头指针指向此新节点

最后将size属性增1。通过如果插入成功，就返回True。这样用户就知道到底发生了什么。

打印节点

这是LinkedList类的方法。要打印链表中所有节点中的数据，需要一次经过一个节点，并打印每一个节点的数据部分

单向链表代码

单向链表的优缺点

优点

它是一种动态数据结构，插入与删除操作简单，不需要位移元素。只需更新下一个指针就可以完成。

使用链表可以轻松实现堆栈和附表数据结构。

缺点

下一指针会使用额外的内存。

不能随机访问。必须从开头遍历链表到达指定的节点。

叙述可能有不清之处，见谅。如果您喜欢，后面再一起讨论下如何从链表中删除元素。