链接表：链接表是线性表的另一种实现技术
线性表的基本要求：
- 能够找到表中的首元素（无论直接过着间接，这件事通常很容易做到）
- 从表中的任一元素出发，可以找到它之后的下一个元素
基于链接技术实现的线性表称为链接表或者链表，实现的基本想法如下：
- 把表中的元素分别存储在一批独立的存储块（称为表的节点）里
- 保证从组成的表结构中的任一节点可 以找到与其相关的下一个节点
- 在前一节点里用链接的方式显式的记录与下一节点之间的关联
这样，只要能够找到组成一个表结构的第一个节点，就能顺序的找到属于这个 表的其他节点，从这些节点里可以看到这个表中的所有元素。
单链表
单向链接表，简称单链表或者链表，它的节点是一个二元组，形式如下图所示，其表元素域elem保存着作为表元素的数据项，链接域next里保存同一个表里的下一个节点的标识。
总结：
- 一个单链表有一些具体的表节点构成
- 每个节点 是一个对象，有自己的标识，也常称为该节点的链接
- 节点之间通过节点链接建立其单向的顺序联系
下面定义一个简单的表节点的类：
calss LNode():
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_
链表的基本操作：
- 创建空链表：只需要把相应的表头标量设置为空链接，在python语言中将其设置为None
- 删除链表：应丢弃这个链表里面的所有节点，在python语言中只需要将表的指针赋值为None,就可以了
- 判断表是否为空：将表头变量的值与空链接比较。
- 判断表是否满：一般而言链表不会满，除非程序用完了所有可用的存储空间。
- 插入元素：首端插入、尾端插入、定位插入。在链表中加入新元素，并不需要移动已有的表数据，只需要为新元素安排一个新节点，然后根据要求，把新节点连载表中的正确位置。也就是说，插入新元素的操作是通过修改链接，接入新结点，从而改变表结构的方式实现的。
-
- 表首端插入 ：首端插入元要求把新数据元素插入表中，作为表的第一个元素，这是最简单的情况，这一步需要三个步骤，如下图 ：
- 创建一个新结点并存入数据
- 把原链接表首结点的链接存入新结点的链接域next，这一操作 将原表的一串结点链接在新结点之后
- 修改表头变量，使之指向新结点
- 示例代码段
q = LNode(13)
q.next = head.next
head = q
-
- 一般情况的元素插入：想要在单链表里的某位置插入一个新结点，必须先找到这个位置之前的那个结点，因为新结点需要插入在它之后，需要修改他的next域，步骤也分为三步，如下图，假设变量pre已指向要插入元素的前一结点：
- 创建一个新结点并存入数据
- 把pre所指向结点next域的值存入新结点的链接域 next
- 修改pre的next域，使之指向新结点
- 示例代码段
q = LNode(13)
q.next = pre.next
pre.next = q
6.删除元素：删除链表中的元素，可以通过调整表结构删除表中结点的方式完成。
-
- 删除表首元素：删除表中第一个元素对应删除表的第一个结点，为此只需要修改表头指针，令其指向表中第二个结点。
- 一般情况的元素删除：一般情况删除须先找到要删元素所在结点的前一结点，假设用pre指向，然后修改pre的next域，使之指向被删结点的下以结点。
- 如下图
7.扫描、定位和遍历
-
- 由于单链表只有一个方向的链接，开始情况下只有表头变量在掌握中，所以对表内容的一切检查都只能从表头变量开始，沿着表中链接逐步进行，这种操作过程称为扫描这种过程的基本模式是：
-
p = head
while p is not None and 其他条件:
# 对结点里的数据所作的操作
p = next
循环中辅助变量p被称为扫描指针
- 按下标定位：
p = head
while p is not None and i > 0:
i -= 1
p = p.next
- 按元素定位
p = head
while p is not None and not pred(p.elem):
p = p.next
- 完整的扫描称为遍历，这样做通常需要对表中每个元素做一些事情
p = head
while p is not None:
print(p.elem)
p = p.next
链表的时间复杂度：
- 创建空表：O(1)
- 删除表：O(1)
- 判断空表：O(1)
- 加入元素：
- 首端加入：O(1)
- 尾端加入：O(n)
- 定位加入：O(n)
- 删除元素:
- 首端删除：O(1)
- 未端删除：O(n)
- 定位删除：O(n)
- 其他删除：O(n)
单链表
原文：https://www.cnblogs.com/moleo/p/13430400.html
