前言
本文主要介绍有关单链表的基本操作，包括但不限于创建一个单链表、单链表的遍历、单链表的插入操作以及单链表的删除操作，Python中并不存在指针，本章主要通过列表实现模拟指针的方法来实现链表以及用类方法实现单链表。
模拟指针
1. 单链表的创建
创建一个单链表需要运用两个列表，其中一个列表用来存储链表中的每一个元素，另一个链表用来存储它们的指针，创建单链表算法如下：
ListValue=[1,5,6,2,4,3] ListPointer=[3,2,-1,5,1,4]
第一个列表保存了链表中的每一个元素，头指针为0，第一个元素是1，表示1的数据域，与1下标相同的在另一个列表中的元素是3，这个表示元素1的指针域，我们回到第一个列表，找下标为3的元素，是2，代表元素2的数据域，而和元素二下标（3）相同的在另一个列表中的元素是5，表示2的指针域，指向了3，依次循环直到某个元素的指针域为-1
2. 单链表的遍历
单链表的遍历算法如下：
ListValue=[1,5,6,2,4,3] ListPointer=[3,2,-1,5,1,4] head=0 next=head while next!=-1: print(ListValue[next]) next=ListPointer[next]
首先初始化头结点，然后开始循环遍历，每次打印数据域，然后让指针指向下一个元素即可
3. 单链表的插入
单链表的插入算法如下：
ListValue=[1,4,5,2] ListRight=[3,2,-1,1] head=0 num=3 （1） next,last=head,head （2） def Output(): next=head while next!=-1: print(ListValue[next],end=' ') next=ListRight[next] print() Output() while ListValue[next]<=num and next!=-1: （3） last=next next=ListRight[next] ListValue.append(num) （4） ListRight.append(ListRight[last]) （5） ListRight[last]=len(ListValue)-1 （6） Output()
（1）要插入的元素
（2）初始化插入位置的下一个元素和上一个元素的指针
（3）找到要插入的位置
（4）将插入元素放在列表最后
（5）获得插入元素的指针域
（6）将原来位置的指针域指向插入元素，完成插入操作
4. 单链表的删除
单链表的删除算法如下：
ListValue=[1,5,6,2,7,3] ListRight=[3,2,4,5,-1,1] head=0 prepos=5 （1） ListRight[prepos]=ListRight[ListRight[prepos]] （2）
（1）找到要删除元素的前一个元素的指针域
（2）让其指针域直接指向要删除元素后一个元素即可
类方法
1. 创建结点
#创建一个结点
class LNode:
def __init__(self,data):
self.data=data
self.next=None
2. 头结点
#头结点
head=LNode(0)
3. 创建一个单链表
#创建一个单链表
def create(n):
head=LNode(0)
tail=head
for i in range(n):
data=int(input())
new=LNode(data)
tail.next=new
tail=new
return head
4. 求单链表长度
#求链表长度
def lenth(head):
n=0
p=head.next
while p:
p=p.next
n+=1
return n
5. 遍历单链表
#遍历单链表
def printf(head):
p=head.next
while p:
print(p.data,end=' ')
p=p.next
6. 插入
#插入
def insert(head,pos,val):
if pos<1 or pos>lenth(head)+1:
return 0
p=head
i=0
while i<pos-1 and p:
p=p.next
i+=1
new=LNode(val)
new.next=p.next
p.next=new
return 1
7. 删除
#删除
def pop(head,pos):
p=head
if pos<1 or pos>lenth(head):
return 0
i=0
while i<pos-1 and p:
p=p.next
i+=1
t=p.next.data
p.next=p.next.next
return t
8. 删除单链表重复元素
#删除单链表重复元素
def delsame(head):
p=head
while p:
q=p.next
r=p
while q:
if q.data==p.data:
r.next=q.next
q=q.next
else:
r=r.next
q=q.next
p=p.next
return 1
总结
本章主要介绍了单链表的基本操作，具体有创建单链表、遍历单链表、单链表的插入以及删除等算法。
