Python代码实现双链表

本文实例为大家分享了Python代码实现双链表的具体代码，供大家参考，具体内容如下

双链表的每个节点有两个指针： 一个指向后一个节点，另一个指向前一个节点

class Node(object):
?? ?def __init__(self, item=None):
?? ??? ?#放数据
?? ??? ?self.item= item
?? ??? ?#指向后一个节点
?? ??? ?self.next = None
?? ??? ?#指向前一个节点
?? ??? ?self.prior =None

此时当前链表第一个节点就是头节点指向的节点 20就是第一个节点 下图
node.next = self.head 当前节点指向原第一个节点

头插法

如何插入呢

插入

p.next = curNode.next #指向后一个节点
curNode.next.prior = p #指向前一个节点

删除

双链表删除

考虑特殊情况删除的

正常删除

#双链表头插法

#停在前一个位置了
count < （pos -1 ）

#双向链表 ?从左往右读
class Node(object):
? ? ? ? """双向链表节点"""
? ? ? ? def __init__(self,item):
? ? ? ? ? ? ? ? #放数据的节点
? ? ? ? ? ? ? ? self.elem = item
? ? ? ? ? ? ? ? #指向后一个节点
? ? ? ? ? ? ? ? self.next = None
? ? ? ? ? ? ? ? #指向前一个节点
? ? ? ? ? ? ? ? self.prev = None
#双向链表
class LinkList(object):
? ? ? ? def __init__(self,node=None):
? ? ? ? ? ? ? ? #代表头节点
? ? ? ? ? ? ? ? self.__head = node

? ? ? ? #判断链表是否为空
? ? ? ? def is_empty(self):
? ? ? ? ? ? ? ? return self.__head == None

? ? ? ? def length(self):
? ? ? ? ? ? ? ? """返回链表的长度"""
? ? ? ? ? ? ? ? #cur游标移动，从而实现遍历元素的功能
? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? #count用来计数
? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? ? ? ? ? #让cur游标可以向下移动
? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? return count

? ? ? ? #遍历整个链表
? ? ? ? def travel(self):
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? return
? ? ? ? ? ? ? ? #建立游标等于起始节点
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? print(cur.elem,end=" ")
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ? print("")

? ? ? ? #头插法
? ? ? ? def add(self,item):
? ? ? ? ? ? ? ? #新节点
? ? ? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? #头节点指向了新的节点
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? #新节点指向原第一个节点
? ? ? ? ? ? ? ? ? ? ? ? node.next = self.__head
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? ? ? ? ? node.next.prev = node

? ? ? ? def append(self,item):
? ? ? ? ? ? ? ? """链表尾部添加元素"""
? ? ? ? ? ? ? ? node = Node(item) ?#定义新节点
? ? ? ? ? ? ? ? #链表是否为空链表
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? #如果为空，新的节点加了进去
? ? ? ? ? ? ? ? ? ? ? ? self.__head = node
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? #头节点 创建游标
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head ? #设置指向头结点的游标 ?此时的当前链表第一个节点，就是头节点指向的节点
? ? ? ? ? ? ? ? ? ? ? ? #cur到最后一个节点停下
? ? ? ? ? ? ? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ? #添加节点到尾部 cur道了最后一个结点 ?cur.next指向了新的节点node ?从左往右读 ?
? ? ? ? ? ? ? ? ? ? ? ? cur.next = node
? ? ? ? ? ? ? ? ? ? ? ? #当前的节点指向它前一个
? ? ? ? ? ? ? ? ? ? ? ? node.prev = cur

? ? ? ? #插入法 ?#pos从零开始
? ? ? ? def insert(self,pos,item):
? ? ? ? ? ? ? ? """在指定位置添加元素"""
? ? ? ? ? ? ? ? #指向不是头部元素，self.__head的地址
? ? ? ? ? ? ? ? # 为下一个元素，所以pre为下一个元素
? ? ? ? ? ? ? ? if pos <= 0:
? ? ? ? ? ? ? ? ? ? ? ? #认为是头插法
? ? ? ? ? ? ? ? ? ? ? ? self.add(item)
? ? ? ? ? ? ? ? #假如长度是3 pos大于2要特殊处理 ?
? ? ? ? ? ? ? ? elif pos > (self.length()-1):
? ? ? ? ? ? ? ? ? ? ? ? #尾插法
? ? ? ? ? ? ? ? ? ? ? ? self.append(item)
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ?? ??? ?#创建节点 新节点
? ? ? ? ? ? ? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? ? ? ? ? count = 0
? ? ? ? ? ? ? ? ? ? ? ? #动起来
? ? ? ? ? ? ? ? ? ? ? ? while count < pos:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? count+=1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? #把节点链接到中间任意位置 插入前一个节点 ? 此时，cur停在后一个节点
? ? ? ? ? ? ? ? ? ? ? ? node.next = cur
? ? ? ? ? ? ? ? ? ? ? ? node.prev = cur.prev
? ? ? ? ? ? ? ? ? ? ? ? cur.prev.next = node
? ? ? ? ? ? ? ? ? ? ? ? cur.prev = node

? ? ? ? def remove(self,item):
? ? ? ? ? ? ? ? """删除元素"""
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ?? ?return
? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? #查找所有的位置有没有要删除的，若有则删除
? ? ? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? ?? ??? ?#判断cur指向的数据,是否为要删除的数据 ? item要删除的元素
? ? ? ? ? ? ? ? ? ? ? ? if cur.elem == item:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #判断此节点是否为头节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #考虑特殊情况,恰好要删除是第一个元素 ? ?当前的元素就是我要删除的元素?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur == self.__head:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #如果删除中间, ?头节点指向后一个节点?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? self.__head = cur.next
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #考虑链表只有一个节点 ?直接指向None
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #是否只有一个节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #中间节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if cur.next != None:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #没有找到,cur游标向继续往下移动
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next

? ? ? ? def search(self,item):
? ? ? ? ? ? ? ? """查找结点是否存在"""
? ? ? ? ? ? ? ? #如果是一个空链表
? ? ? ? ? ? ? ? if self.is_empty():
? ? ? ? ? ? ? ? ? ? ? ? return False
? ? ? ? ? ? ? ? cur = self.__head
? ? ? ? ? ? ? ? while cur.next != self.__head:
? ? ? ? ? ? ? ? ? ? ? ? #cur数据是否为查找的数据 item是要查的数据?
? ? ? ? ? ? ? ? ? ? ? ? if cur.elem == item:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? #遍历完成 cur指向None
? ? ? ? ? ? ? ? return False

if __name__ == '__main__':
? ? ? ? ll = LinkList()
? ? ? ? #第一次的
? ? ? ? print(ll.is_empty())
? ? ? ? print(ll.length())

? ? ? ? ll.append(1)
? ? ? ? print(ll.is_empty())
? ? ? ? print(ll.length())

? ? ? ? ll.append(2)

? ? ? ? ll.append(3)
? ? ? ? ll.append(4)
? ? ? ? ll.append(5)
? ? ? ? ll.travel()
? ? ? ? ll.insert(-1,50)
? ? ? ? ll.travel()
? ? ? ? ll.insert(2,60)
? ? ? ? ll.travel()
? ? ? ? ll.insert(10,300)
? ? ? ? ll.travel()
? ? ? ? ll.remove(50)
? ? ? ? ll.travel()
? ? ? ? ll.remove(300)
? ? ? ? ll.travel()

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

查看更多关于Python代码实现双链表的详细内容...