单链表尾指针示意图（链表的节点图解） - 原点资讯

步骤：

查找结点并由指针指向该结点。

生成一个新结点*s。
将新结点*s 的数据域置为 e。
将新结点*s 的指针域指向结点 a
将结点 p 的指针域指向新结点 s。

时间复杂度为

def insert(self, pos, elem): node = LNode(elem) count = 0 # p用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置 p = self.__head while count < (pos-1): count = 1 p = p.next # 先将新节点node的next指向插入位置的节点 node.next = p.next # 将插入位置的前一个节点的next指向新节点 p.next = node

删除

要删除单链表中指定位置的元素，同插人元素一样，首先应该找到该位置的前驱结点。如图所示，在单链表中删除元素b时，应该首先找到其前驱结点a。为了在单链表中实现元素a、b和c之间逻辑关系的变化,仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为

单链表尾指针示意图,链表的节点图解(5)

时间复杂度为

# 按值删除 def remove_1(self, elem): cur = self.__head pre = None while cur != None: if cur.elem == elem: # 先判断此结点是否是头节点 # 头节点 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next # 按位置删除 def remove_2(self,i): p = self.__head count = 0 while p != None: if count != i-1: p = p.next count = 1 else: p.next = p.next.next break

创建单链表

头插法

(1) 创建一个只有头结点的空链表。

(2) 根据待创建链表包括的元素个数, 循环次执行以下操作:

生成一个新结点*p;
输入元素值赋给新结点*p 的数据域;
将新结点*p 插人到头结点之后。
尾插法

(1) 创建一个只有头结点的空链表。

(2) 尾指针 r 初始化，指向头结点。

(3) 根据创建链表包括的元素个数, 循环次执行以下操作:

生成一个新结点*p;
输入元素值赋给新结点*p 的数据域;
将新结点 p 插入到尾结点 r之后;
尾指针 r 指向新的尾结点*p。。

单链表尾指针示意图,链表的节点图解(6)

# 头插法 def add(self, elem): # 先创建一个保存item值的节点 node = LNode(elem) # 将新节点的链接域next指向头节点，即__head指向的位置 node.next = self.__head # 将链表的头_head指向新节点 self.__head = node

# 尾插法 def append(self, elem): node = LNode(elem) # 先判断链表是否为空，若是空链表，则将_head指向新节点 if self.is_empty(): self.__head = node # 若不为空，则找到尾部，将尾节点的next指向新节点 else: p = self.__head while p.next != None: p = p.next p.next = node顺序表与单链表的对比

单链表尾指针示意图,链表的节点图解(7)