Python双向链表的操作
目录
一、双向链表
双向链表示例图
二、双向链表的操作
1、判断链表是否为空
2，链表长度
3，遍历整个链表
4，在链表头部添加元素
5、链表尾部添加元素
6，在指定位置插入元素
7，修改指定位置的元素
8，删除元素
9、查找元素是否存在
三、完整代码
一、双向链表
双向链表示例图
结点node里有三个部分：pre(指向上一结点next的指针)、elem(元素)和next(指向下一结点的指针)，head指针指向头结点
二、双向链表的操作
1、判断链表是否为空
def is_empty(self):# 链表是否为空if self.__head is None:return Trueelse:return False2，链表长度
def length(self):# 链表长度if self.is_empty():return 0count = 0cur = self.__headwhile cur.next is not None:count += 1cur = cur.nextreturn count3，遍历整个链表
def travel(self):# 遍历整个链表if self.is_empty():returncur = self.__headwhile cur.next is not None:print(cur.elem, end=' ')cur = cur.nextprint(cur.elem)4，在链表头部添加元素
def add(self, item):# 链表头部添加元素node = Node(item)if self.is_empty(): # 原本是空链表的就让头指针直接指向这个新添加的元素结点self.__head = nodeelse: # 链表不为空时node.next = self.__head # 新结点的next指针指向头指针所指的结点self.__head.pre = node.next # 再将头指针结点的pre指针指向新结点的nextself.__head = node # 最后修改头指针指向新结点5、链表尾部添加元素
def append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next is not None: # 循环找到尾部结点的指向，当退出循环时指针已指向最后一个结点cur = cur.nextcur.next = node # 将尾部结点的next指向新结点node.pre = cur.next # 新结点的pre指向尾结点的next6，在指定位置插入元素
因为插入的代码比较难理解，所以这里画了个图帮助理解
新结点node值是100，要插入到原链表11，22，33的下标为2的位置（也就是pos为2的位置插入100），所以就要修改指针的指向做到插入结点的目的
步骤：
根据给定的pos位置去遍历让指针指向要插入的位置的上一个结点cur.next
按红色箭头和数字顺序修改指针指向即可：
1.cur.next.pre现让它指向新结点100的next区域
2.新结点100的next区域指向33这个结点（不是pre区域）
3.新结点pre区域指向结点22的next区域
4.结点22的next区域指向新结点100（不是pre区域）
重新改变这四个指针的指向后就完成了插入
def insert(self, pos, item):# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素# 创建新结点node = Node(item)count = 0cur = self.__head # 当时指针while count < (pos-1): # 循环找到指向pos位置结点的指针count += 1cur = cur.next# 当上面退出循环时，说明cur已经指向了pos的位置# 所以接下来修改四个指针的指向来实现插入元素cur.next.pre = node.next # 1.将cur的下一结点的pre指向新结点nextnode.next = cur.next # 2.将新结点的next指向cur的下一结点cur.next = node # 3.将cur的next指向新结点node.pre = cur.next # 4.将新结点的pre指向cur的next7，修改指定位置的元素
def modify(self, pos, item):"""修改指定位置的元素"""# 当指定的位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 当pos大于等于链表总长度时，则修改尾部元素elif pos >= self.length():tail = self.__head# 循环让指针指向尾部元素while tail.next is not None:tail = tail.nexttail.elem = item # 修改尾部元素else:count = 0tail = self.__head# 循环指针找到指定的位置while count < pos: # 1.当不满足条件退出循环时，说明指针已经指向了给定的pos位置tail = tail.nextcount += 1tail.elem = item # 2.将pos位置的元素修改8，删除元素
def remove(self, item):# 删除节点cur = self.__head # cur当前指针forword = None # 前一个指针# 遍历链表当时指针while cur is not None:# 如果找到了要删除的元素if cur.elem == item:# 要删除的元素刚好是头部元素，就把头指针指向当前的下一个结点if cur == self.__head:self.__head = cur.nextelse:forword.next = cur.next # 如果不是头元素指针就继续向后走returnelse: # 未找到要删除的元素，指针向后走，继续遍历forword = curcur = cur.next9、查找元素是否存在
def search(self, item):# 查找节点是否存在cur = self.__headwhile cur.next is not None:# 找到了返回True,未找到指向下一个继续遍历if cur.elem == item:return Truecur = cur.next# 查找的元素在最后一个，遍历后指向最后一个，但是没有进入循环，所以需要在循环体外判断一次if cur.elem == item:return Truereturn False三、完整代码
class Node():def __init__(self, elem):# 双向链表结点self.pre = Noneself.elem = elemself.next = Noneclass DoubleLinkList():def __init__(self, node=None):self.__head = nodedef is_empty(self):# 链表是否为空if self.__head is None:return Trueelse:return Falsedef length(self):# 链表长度if self.is_empty():return 0count = 0cur = self.__headwhile cur.next is not None:count += 1cur = cur.nextreturn countdef travel(self):# 遍历整个链表if self.is_empty():returncur = self.__headwhile cur.next is not None:print(cur.elem, end=' ')cur = cur.nextprint(cur.elem)def add(self, item):# 链表头部添加元素node = Node(item)if self.is_empty(): # 原本是空链表的就让头指针直接指向这个新添加的元素结点self.__head = nodeelse: # 链表不为空时node.next = self.__head # 新结点的next指针指向头指针所指的结点self.__head.pre = node.next # 再将头指针结点的pre指针指向新结点的nextself.__head = node # 最后修改头指针指向新结点def append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next is not None: # 循环找到尾部结点的指向，当退出循环时指针已指向最后一个结点cur = cur.nextcur.next = node # 将尾部结点的next指向新结点node.pre = cur.next # 新结点的pre指向尾结点的nextdef modify(self, pos, item):"""修改指定位置的元素"""# 当指定的位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 当pos大于等于链表总长度时，则修改尾部元素elif pos >= self.length():tail = self.__head# 循环让指针指向尾部元素while tail.next is not None:tail = tail.nexttail.elem = item # 修改尾部元素else:count = 0tail = self.__head# 循环指针找到指定的位置while count < pos: # 1.当不满足条件退出循环时，说明指针已经指向了给定的pos位置tail = tail.nextcount += 1tail.elem = item # 2.将pos位置的元素修改def insert(self, pos, item):# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素# 创建新结点node = Node(item)count = 0cur = self.__head # 当时指针while count < (pos-1): # 循环找到指向pos位置结点的指针count += 1cur = cur.next# 当上面退出循环时，说明cur已经指向了pos的位置# 所以接下来修改四个指针的指向来实现插入元素cur.next.pre = node.next # 1.将cur的下一结点的pre指向新结点nextnode.next = cur.next # 2.将新结点的next指向cur的下一结点cur.next = node # 3.将cur的next指向新结点node.pre = cur.next # 4.将新结点的pre指向cur的nextdef remove(self, item):# 删除节点cur = self.__head # cur当前指针forword = None # 前一个指针# 遍历链表当时指针while cur is not None:# 如果找到了要删除的元素if cur.elem == item:# 要删除的元素刚好是头部元素，就把头指针指向当前的下一个结点if cur == self.__head:self.__head = cur.nextelse:forword.next = cur.next # 如果不是头元素指针就继续向后走returnelse: # 未找到要删除的元素，指针向后走，继续遍历forword = curcur = cur.nextdef search(self, item):# 查找节点是否存在cur = self.__headwhile cur.next is not None:# 找到了返回True,未找到指向下一个继续遍历if cur.elem == item:return Truecur = cur.next# 查找的元素在最后一个，遍历后指向最后一个，但是没有进入循环，所以需要在循环体外判断一次if cur.elem == item:return Truereturn Falseif __name__ == '__main__':ll = DoubleLinkList()print(ll.is_empty())print(ll.length())ll.travel()print('add')ll.add(9)ll.travel()ll.add(10)ll.travel()print('append')ll.append(13)ll.travel()print('insert')ll.insert(1, 33)ll.travel()print('remove')ll.remove(10)ll.travel()print('modify')ll.modify(2, 100)ll.travel()print(ll.search(9))