单向链表:
classlistNode:#链表中的结点def__init__(self,x):self.val=xself.next=NoneclassLinkedList:#链表类def__init__(self):self.head=Nonel1=LinkedList()l1.add(1)l1.add(2)
size()——返回链表中数据元素的个数/链表长度
defsize(self):size=0head=self.headwhilehead:size+=1head=head.nextturnsize
empty()——若链表为空则返回一个布尔值true
defempty(self):turnTrueifself.headelseFalse
value_at(index)——返回第n个元素的值（从0开始计算），若索引超过链表长度则报错
defvalue_at(self,index):ifnotself.head:raiseIndexError("Indexoutofrange.")head=self.headwhileindex0:ifnothead:raiseIndexError("Indexoutofrange.")head=head.nextindex-=1turnhead.val
add(value)——添加元素到链表的首部
defadd(self,value):new_node=listNode(value)new_node.next=self.headself.head=new_node
pop_front()——删除首部元素并返回其值，若链表为空则报错
defpop_front(self):ifnotself.head:raiseIndexError("Popfromemptylist")value=self.head.valself.head=self.head.nextturnvalue
append(value)——添加元素到链表的尾部
defappend(self,value):new_node=listNode(value)ifnotself.head:self.head=new_nodeturnhead=self.headwhilehead.next:head=head.nexthead.next=new_node
pop_back()——删除尾部元素并返回其值，若链表为空则报错
defpop_back(self):ifnotself.head:raiseIndexError("Popfromemptylist")ifnotself.head.next:value=self.head.valself.head=Noneturnvaluehead=self.headwhilehead.next.next:head=head.nextvalue=head.next.valhead.next=Noneturnvalue
front()——返回首部元素的值，若链表为空则报错
deffront(self):ifnotself.head:raiseValueError("Linkedlistisempty")turnself.head.val
back()——返回尾部元素的值，若链表为空则报错
defback(self):ifnotself.head:raiseValueError("Linkedlistisempty")head=self.headwhilehead.next:head=head.nextturnhead.val
insert(index,value)——插入值到指定的索引，若索引超出链表长度则报错
definsert(self,index,value):ifnotself.head:raiseIndexError("Indexoutofrange")head=self.headnew_node=listNode(value)ifindex==0:new_node.next=headself.head=new_nodeturnwhileindex-10:head=head.nextifnothead:raiseIndexError("Indexoutofrange")index-=1temp=head.nexthead.next=new_nodenew_node.next=temp
erase(index)——删除指定索引的节点，若索引超出链表长度则报错
deferase(self,index):ifnotself.head:raiseIndexError("Indexoutofrange")head=self.headifindex==0:self.head=head.nextwhileindex-10:index-=1head=head.nextifnothead:raiseIndexError("Indexoutofrange")temp=head.nexthead.next=temp.next
verse()——逆序链表
defverse(self):pv=Nonehead=self.headwhilehead:temp=head.nexthead.next=pvpv=headhead=tempself.head=pv
move(value)——删除链表中指定值的第一个元素
defmove(self,value):ifnotself.head:turnhead=self.headifhead.val==value:self.head=head.nextturnwhilehead.next:ifhead.next.val==value:temp=head.next.nexthead.next=tempturnhead=head.next
时间复杂度：
在链表的首部插入/移除结点、获得链表首部的值，都是O(1)时间复杂度 获取/移除/插入任一结点、尾部结点，都是O(n)时间复杂度