1-2 线性表的链式存储(单链表)
定义:线性表的链式存储又称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点,除存放元素本身的信息外,还需要存放一个指向后继的指针。
特点:利用单链表可以解决顺序表需要大量连续存储单元的缺点,但也存在浪费存储空间的问题。单链表是非随机存取的存储结构,在查找某个特定的节点时,需要从表头开始遍历,依次查找。
代码:
class SingleNode(object): def __init__(self,data,next=None): self.data=data self.next=next """ 单链表 """ class SingleList(object): def __init__(self,node=None): self.head=node def length(self)->int: count=0 while self.head!=None: count+=1 self.head=self.head.next return count def ListHeadInsert(self,value:int): newNode=SingleNode(value) newNode.next=self.head self.head=None def ListTailInsert(self,value:int): newNode=SingleNode(value) if self.isEmpty(): self.head=newNode else: while self.head.next: self.head=self.head.next self.head.next=newNode def isEmpty(self): if self.head==None: return True else: return False def getElem(self,i:int): j=1 while self.head!=None and j<i: self.head=self.head.next j+=1 return self.head def locateElem(self,i:int): while self.head and self.head.data!=i: self.head=self.head.next return self.head def insertNode(self,value,i): prior=SingleList(self.head).getElem(i-1) newNode=SingleNode(value) newNode.next=prior.next prior.next=newNode def deleteNode(self,i:int)->bool: if i<1 or i>SingleList(self.head).length(): return False tem=SingleList(self.head).getElem(i-1) tem.next=tem.next.next return True