python实现单链表,单链表python基本操作
本文主要详细介绍python对双向链表的实现。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。
本文分享python实现双向链表的具体代码,供大家参考。具体内容如下
实现双向链表需要注意什么
1.如何插入元素,考虑特殊情况:头节点位置和尾节点位置;一般情况:中间位置
2.如何删除元素,考虑特殊情况:头节点的位置和尾节点的位置;一般情况:中间位置
代码实现
1.构造一个节点类和一个链表类。
类别节点:
def __init__(self,data):
self.data=数据
self.next=无
self.previous=None
类双链接表:
双向链表
def __init__(self,node=None):
自我。_head=node
以下方法在链表类中实现。
2.确定链表是否为空。
定义为_空(自身):
回归自我。_head无
3.输出链表的长度
定义长度(自身):
计数=0
if self.is_empty():
返回计数
else:
当前=自身。_head
虽然当前不是:
计数=1
当前=当前。下一个
返回计数
4.遍历链表
定义差旅(自助):
当前=自身。_head
虽然当前不是:
打印(“{0}”。format(current.data),end= )
当前=当前。下一个
打印()
5.通过头部插入添加新元素。
定义添加(自身,项目):
节点=节点(项目)
#如果链表为空,让头指针指向当前节点
if self.is_empty():
自我。_head=node
#注意插入顺序,
else:
node.next=self。_head
自我。_head.previous=node
自我。_head=node
6.通过尾部插入添加新元素。
定义附加(自身,项目):
节点=节点(项目)
#如果链表为空,让头指针直接指向节点。
if self.is_empty():
自我。_head=node
#你需要找到尾节点,然后把它和新节点连接起来。
else:
当前=自身。_head
而current.next不是None:
当前=当前。下一个
current.next=节点
node.previous=当前
7.找出该元素是否存在于链表中。
定义搜索(自身,项目):
当前=自身。_head
发现=假
而当前不是没有和没有发现:
if current.data==item:
发现=真
else:
c
urrent = current.next
return found
8. 在某个位置中插入元素
def insert(self, item, pos):# 特殊位置,在第一个位置的时候,头插法
if pos <= 0:
self.add(item)
# 在尾部的时候,使用尾插法
elif pos > self.length() - 1:
self.append(item)
# 中间位置
else:
node = Node(item)
current = self._head
count = 0
while count < pos - 1:
current = current.next
count += 1
# 找到了要插入位置的前驱之后,进行如下操作
node.previous = current
node.next = current.next
current.next.previous = node
current.next = node
# 换一个顺序也可以进行def insert2(self, item, pos):
if pos <= 0:
self.add(item)
elif pos > self.length() - 1:
self.append(item)
else:
node = Node(item)
current = self._head
count = 0
while count < pos:
current = current.next
count += 1
node.next = current
node.previous = current.previous
current.previous.next = node
current.previous = node
9. 删除元素
def remove(self, item):current = self._head
if self.is_empty():
return
elif current.data == item:
# 第一个节点就是目标节点,那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点
current.next.previous = None
self._head = current.next
else:
# 找到要删除的元素节点
while current is not None and current.data != item:
current = current.next
if current is None:
print("not found {0}".format(item))
# 如果尾节点是目标节点,让前驱节点指向None
elif current.next is None:
current.previous.next = None
# 中间位置,因为是双链表,可以用前驱指针操作
else:
current.previous.next = current.next
current.next.previous = current.previous
# 第二种写法def remove2(self, item):
"""删除元素"""
if self.is_empty():
return
else:
cur = self._head
if cur.data == item:
# 如果首节点的元素即是要删除的元素
if cur.next is None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的prev设置为None
cur.next.prev = None
# 将_head指向第二个节点
self._head = cur.next
return
while cur is not None:
if cur.data == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
10. 演示
my_list = DoubleLinkList()print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))
print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))
print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))
print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))
print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))
print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))
print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。