链表是一种线性列表，其中许多相同数据类型的数据项按特定顺序排列。插入和删除数据更方便。如果有新的数据，申请一块内存空间，数据删除后将这块内存归还给系统。链表的优点是可以灵活的进行插入和删除操作，不需要连续的存储单元。查找、更新、插入、删除数组O(1)O(1)O(n)O(n)链表O(n)O(n)O(1)O(1)数组适用于有很多的场景读操作和很少的写操作。链表则相反。注：cur_node：当前节点，head：头节点，tail：尾节点，ptr：“穿针的针”，一般在遍历修改时使用，new_node：创建的新节点。1.单向链表classlinked_list:def__init__(self):self.data=None#用来存放每个节点的具体数据信息self.next=None#用来指向下一个节点1.1创建one-单向链表head=linked_list()#创建头节点new_node=linked_list()#创建新节点head.next=new_node#新节点链接在头节点之后1.2遍历单向链表ptr=headwhileptr!=None:print("nodeinformation")1.3在单向链表中插入新节点1.3.1Insertnew_node.next=headatthehead#原头节点链接在新节点之后head=new_node#更新head节点信息1.3.2在中间插入ptr=head通过遍历Node找到之前插入的位置，positon可以用来标识数字等whileptr!=None:ifptr.next=positon:breakptr=ptr.nextnew_node.next=ptr.nextptr.next=new_node1.3.3在最后插入寻找尾节点whileptr!=None:ifptr.next==None:breakptr=ptr.nextptr.next=new_nodenew_node.next=None1.4单向链表的反转由于单向链表不知道当前节点的前一个节点信息，如果要反转一个单向链表，需要3个指针，在遍历过程中还需要一个保留前一个节点位置的pre指针。ptr=headpre=Nonewhielptr!=None:r=prepre=ptrptr=ptr.nextpre.next=rhead=ptr1.5单向链表的链接ptr=head1whielptr!=None:ifptr.next==None:breakptr=ptr.nextptr.next=head2head=head11.6删除单向链表1.6.1删除头节点head=head.next1.6.2删除中间节点ptr=headwhileptr.next!=positon:ptr=ptr.nextptr.next=ptr.next.next2。环形链表在单向链表中，需要维护链表的头指针。如果链表的头指针损坏或丢失，整个链表就会丢失。在循环链表中，可以从任意一个节点开始遍历其他节点。循环链表通常应用于内存工作区和输入/输出缓冲区。classcircular_linked_list:def__init__(self):self.data=Noneself.next=None2.1建立循环链表和单向链表的唯一区别是尾节点指向头节点new_node=circular_linked_list()head.next=new_nodenew_node.next=head2.2循环链表遍历ptr=headwhileTrue:print("nodeinformation")ifptr.next=head:break2.3在循环链表中插入新节点2.3.1在第一个插入new_node.next=headheadptr=headwhileptr.next!=head:ptr=ptr.nextptr.next=new_nodehead=new_node2.3.2insertptr=headwhileptr.next!=position:ptr=ptr.nextnew_node.next=ptr.nextptr.next=new_node2.3.3在末尾插入ptr=headwhileptr.next!=head:ptr=ptr.nextptr.next=new_nodenew_node.next=head2.3环链表删除节点2.3.1删除headnodeptr=headwhileptr.next!=head:ptr=ptr.nextptr.next=head.nexthead=head.next2.3.2删除head节点以外的节点ptr=headwhileptr.next!=positon:ptr=ptr.nextptr.next=ptr.next.next3。双向链表和循环链表都是有向链表，只能单向遍历。双向链表有一个左指针和一个右指针。如果中间链接坏了，可以反向遍历整个链表，从而快速重建完整的链表。classdouble_linked_list:def__init__(self):self.data=Noneself.llink=Noneself.rlink=None3.1创建双向链表head=double_linked_list()new_node=double_linked_list()head.rlink=new_nodenew_node.llink=head3.2在双向链表中插入一个新节点3.2.1Insertnew_node.rlink=headhead.llink=new_nodehead=new_node3.2.2在中间插入ptr=headwhileptr.next!=positon:ptr=ptr.nextptr.rlink.llink=new_nodenew_node.rlink=ptr.rlinknew_node.llink=ptrptr.rlink=new_node3.3.3insertptrattheend=headwhileptr.next!=None:ptr=ptr.nextptr.rlink=new_nodenew_node.llink=ptrnew_node.rlink=None3.3双向链表删除节点3.3.1删除头节点head=head.rlinkhead.llink=None3.3.2删除中间节点ptr=headwhileptr!=position:ptr=ptr.nextptr.rlink.llink=ptr.llinkptr.llink.rlink=ptr.rlink
