1、双向链表功能的定义方法说明size()返回链表中元素个数is_empty()判断链表是否为空insert(index, item)在指定位置插入元素append(item)在末尾插入元素remove(index)删除指定位置的元素set(index, item)修改指定位置的元素get(index)获取指定位置的元素find(item)查找链表中某个元素的位置for_each(func)遍历链表classNode:def__init__(self,item,prevNone,nextNone):self.itemitem self.prevprev self.nextnextclassDoublyLinkedList:# 初始化def__init__(self):self.__headNoneself.__tailNoneself.__size0# 返回链表中元素个数propertydefsize(self):returnself.__size# 判断链表是否为空defis_empty(self):returnself.__size0# 在末尾插入元素defappend(self,item):ifself.is_empty():# 单链表为空时新添加的元素既是 头结点也是尾结点new_nodeNode(item)self.__headnew_node self.__tailnew_nodeelse:# 往尾部添加new_nodeNode(item,self.__tail)self.__tail.nextnew_node self.__tailnew_node self.__size1# 在指定位置插入元素definsert(self,index,item):ifindex0orindexself.__size:raiseIndexError(下标越界!)ifindex0:# 头插new_nodeNode(item)new_node.nextself.__head self.__head.prevnew_node self.__headnew_nodeelifindexself.__size:# 尾插new_nodeNode(item)self.__tail.nextnew_node new_node.prevself.__tail self.__tailnew_nodeelse:# 中间插currentself.find_node_by_index(index)beforecurrent.prev new_nodeNode(item,prevbefore,nextcurrent)before.nextnew_node current.prevnew_node self.__size1# 删除指定位置的元素defremove(self,index):ifindex0orindexself.__size:raiseIndexError(下标越界。)ifindex0:# 删除头元素nodeself.__head self.__headnode.nextifnode.next:self.__head.prevNoneelifindexself.__size-1:# 删除尾元素nodeself.__tail self.__tailnode.previfnode.prev:self.__tail.nextNoneelse:nodeself.find_node_by_index(index)beforenode.prev afternode.nextbefore.nextafter after.prevbefore node.itemNonenode.prevNonenode.nextNoneself.__size-1deffind_node_by_index(self,index):ifindex0orindexself.__size:raiseIndexError(下标越界)ifindexself.__size/2:# 从头找nodeself.__headforiinrange(index):nodenode.next# 循环结束此时node为索引为index的元素else:nodeself.__tailforiinrange(self.__size-1,index,-1):# 从尾节点往回找时range 默认是递增的必须加上步长 -1nodenode.prev# 循环结束此时node为索引为index的元素returnnodedef__str__(self):result[]nodeself.__headwhilenode:result.append(node.item)nodenode.nextreturn-.join(result)if__name____main__:linkDoublyLinkedList()link.append(a)link.append(b)link.append(c) 09_双链表的实现
1、双向链表功能的定义方法说明size()返回链表中元素个数is_empty()判断链表是否为空insert(index, item)在指定位置插入元素append(item)在末尾插入元素remove(index)删除指定位置的元素set(index, item)修改指定位置的元素get(index)获取指定位置的元素find(item)查找链表中某个元素的位置for_each(func)遍历链表classNode:def__init__(self,item,prevNone,nextNone):self.itemitem self.prevprev self.nextnextclassDoublyLinkedList:# 初始化def__init__(self):self.__headNoneself.__tailNoneself.__size0# 返回链表中元素个数propertydefsize(self):returnself.__size# 判断链表是否为空defis_empty(self):returnself.__size0# 在末尾插入元素defappend(self,item):ifself.is_empty():# 单链表为空时新添加的元素既是 头结点也是尾结点new_nodeNode(item)self.__headnew_node self.__tailnew_nodeelse:# 往尾部添加new_nodeNode(item,self.__tail)self.__tail.nextnew_node self.__tailnew_node self.__size1# 在指定位置插入元素definsert(self,index,item):ifindex0orindexself.__size:raiseIndexError(下标越界!)ifindex0:# 头插new_nodeNode(item)new_node.nextself.__head self.__head.prevnew_node self.__headnew_nodeelifindexself.__size:# 尾插new_nodeNode(item)self.__tail.nextnew_node new_node.prevself.__tail self.__tailnew_nodeelse:# 中间插currentself.find_node_by_index(index)beforecurrent.prev new_nodeNode(item,prevbefore,nextcurrent)before.nextnew_node current.prevnew_node self.__size1# 删除指定位置的元素defremove(self,index):ifindex0orindexself.__size:raiseIndexError(下标越界。)ifindex0:# 删除头元素nodeself.__head self.__headnode.nextifnode.next:self.__head.prevNoneelifindexself.__size-1:# 删除尾元素nodeself.__tail self.__tailnode.previfnode.prev:self.__tail.nextNoneelse:nodeself.find_node_by_index(index)beforenode.prev afternode.nextbefore.nextafter after.prevbefore node.itemNonenode.prevNonenode.nextNoneself.__size-1deffind_node_by_index(self,index):ifindex0orindexself.__size:raiseIndexError(下标越界)ifindexself.__size/2:# 从头找nodeself.__headforiinrange(index):nodenode.next# 循环结束此时node为索引为index的元素else:nodeself.__tailforiinrange(self.__size-1,index,-1):# 从尾节点往回找时range 默认是递增的必须加上步长 -1nodenode.prev# 循环结束此时node为索引为index的元素returnnodedef__str__(self):result[]nodeself.__headwhilenode:result.append(node.item)nodenode.nextreturn-.join(result)if__name____main__:linkDoublyLinkedList()link.append(a)link.append(b)link.append(c)