链表1-单链表（Python实现）

一、链表定义

1、线性表需求

线性表的基本需求有两点：

• 能够找到线性表的首元素(head)。
• 从线性表的任何一个元素开始，能够找到它之后的下一个元素(next)。

2、什么是链表(链接表)

基于链接技术实现的线性表称为链接表（简称 链表）。链接技术实现原理：

• 把表中的元素 分别 存储在 独立的存储块(称为链表的 结点 )中。
• 在前一节点中 显示 的记录下一节点。

二、单链表(single linked list)

1、定义

单向链表 是链接方向为单向的链表。简称 单链表 或者 链表，一般情况下，我们说的链表也是指单向链表。一个单链表的 结点 包含两个部分，第一个部分（元素域）存储关于节点的信息(如表示元素的数据项)，第二部分（链接域）存储下一个节点的地址。

(图来自维基百科)

(1)表头变量(表头指针)

可以用一个变量表示单链表的首结点的引用(如上图的head)，这样的变量称为表头变量或者表头指针。

(2)空链接

为了表示一个单链表的结束，最后一个节点的第二个部分需设置一个表示结束的值在Python里，用None表示，这个值称为 空链接。

2、节点的算法实现

class LNode :
    def __init__(self, elm, nxt):
        self.elem = elm
        self.next = nxt

3、单链表的算法实现

这是一个最简单的单链表。

class LList:
    def __init__(self):
        """
        实例属性head表示首结点的引用
        """
        self.head = None

三、单链表的操作

操作都在类LList里面定义为方法。

1、初始化单链表

把表头变量head的值设置为None。

2、判断表是否为空

将表头变量head的值与空值进行比较。

 def is_empty(self):
        """判断单链表是否为空"""
        return self.head is None

3、插入元素

插入元素可以分为表头插入，定位插入，表尾插入。和顺序表的不同的是，在单向链表中插入元素时，并不需要移动已有的元素，而是修改链接，接入新的节点。

(1)表头插入

表头插入元素只需要两步即可完成。第一步：将原单链表首节点的链接存入新节点的链接域next。第二步：修改表头变量，使之指向新节点。

代码实现：

    def prepend(self, elem):
        """
        表头插入元素。
        :param elem: element
        """
        self.head = LNode(elem, self.head)

时间复杂度分析：

因为可以通过head直接找到首结点，所以时间复杂度为常量时间复杂度O(1)。

(2)定位插入

定位插入是指在链表的某个位置插入一个新结点。一般需要三步可以完成。第一步：从首结点开始找，找到该位置的前一个节点(pre)。第二步：将前一个节点原来所指向的链接域next存入新结点的链接域next。第三步：修改前一个结点的链接域next，使之指向新结点。

代码实现：

q = LNode(13) # 创建一个新节点
q.next = pre.next # 将前一个节点原来所指向的链接域next存入新结点的链接域next
pre.next = q # 修改表头变量，使之指向新节点。

时间复杂度：

定位插入元素的时间主要消耗在查找元素。假设单链表有n个结点，在各位置插入时，查找元素次数如下：