# Python数据结构（双向列表、单项循环列表）

1546-王同学

双向链表

python
class Node(object):
def __init__(self, item):
# _item存放数据元素
self.item = item
# _next是下一个节点的标识
self.next = None

#单链表
def __init__(self,node=None):

def is_empty(self):
#链表是否为空

def length(self):
#链表长度
count = 0
while cur != None:
count += 1
cur = cur.next
return count

def travel(self):
#遍历整个链表
while cur != None:
print(cur.item,end=" ")
cur = cur.next
print("遍历完成")

#链表头部添加元素
node = Node(item)

def append(self,item):
#链表尾部添加元素
node=Node(item)
if self.is_empty() :
else:
while cur.next != None:
cur = cur.next
cur.next = node

def insert(self,pos,item):
#指定位置添加元素
if pos <= 0:
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
count = 0
while count < (pos-1):
count += 1
pre = pre.next
node.next = pre.next
pre.next = node

class Node(object):
def __init__(self,item):
self.item = item
self.next = None
self.prev = None

def __init__(self,node=None):

def is_empty(self):
#链表是否为空

def length(self):
#链表长度
count = 0
while cur != None:
cur = cur.next
count += 1
return count

def travel(self):
#遍历链表
while cur != None:
print(cur.item,end=" ")
cur = cur.next
return ("遍历完成")

#链表头部添加
node = Node(item)
else:

def append(self,item):
#链表尾部添加
node = Node(item)
if self.is_empty():
else:
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur

def insert(self,pos,item):
#指定位置添加
if pos <0:

elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
count = 0
while count < (pos-1):
count += 1
cur = cur.next
print("count:",count)
node.next = cur.next
cur.next = node
cur.next.prev = node
node.prev = cur

def remove(self,item):
#删除节点
if self.is_empty():
print("o")
else:
if cur.item == item:
# 如果首节点的元素即是要删除的元素
if cur.next == None:
# 如果链表只有这一个节点
else:
# 将第二个节点的prev设置为None
cur.next.prev = None
#return
while cur != None:
if cur.item == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next

def search(self,item):
#查找节点是否存在
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False

if __name__ == "__main__":
DD.remove(3)
print("*****************")
DD.append(1)
DD.append(2)
DD.append(3)
DD.append(4)
DD.travel()
print("*****************")
DD.insert(3,9)
DD.travel()
print("*****************")
DD.remove(2)
DD.travel()

单向循环链表

python

python

python

python
class Node(object):
"""节点"""
def __init__(self, item):
self.item = item
self.next = None

"""单向循环链表"""
def __init__(self):

def is_empty(self):
"""判断链表是否为空"""

def length(self):
"""返回链表的长度"""
# 如果链表为空，返回长度0
if self.is_empty():
return 0
count = 1
count += 1
cur = cur.next
return count

def travel(self):
"""遍历链表"""
if self.is_empty():
return
print cur.item,
cur = cur.next
print cur.item,
print ""

"""头部添加节点"""
node = Node(item)
if self.is_empty():
else:
# 移到链表尾部，将尾部节点的next指向node
cur = cur.next
cur.next = node

def append(self, item):
"""尾部添加节点"""
node = Node(item)
if self.is_empty():
else:
# 移到链表尾部
cur = cur.next
# 将尾节点指向node
cur.next = node

def insert(self, pos, item):
"""在指定位置添加节点"""
if pos <= 0:
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
count = 0
# 移动到指定位置的前一个位置
while count < (pos-1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node

def remove(self, item):
"""删除一个节点"""
# 若链表为空，则直接返回
if self.is_empty():
return
# 将cur指向头节点
pre = None
# 若头节点的元素就是要查找的元素item
if cur.item == item:
# 如果链表不止一个节点
# 先找到尾节点，将尾节点的next指向第二个节点
cur = cur.next
# cur指向了尾节点
else:
# 链表只有一个节点
else:
# 第一个节点不是要删除的
# 找到了要删除的元素
if cur.item == item:
# 删除
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur 指向尾节点
if cur.item == item:
# 尾部删除
pre.next = cur.next

def search(self, item):
"""查找节点是否存在"""
if self.is_empty():
return False
if cur.item == item:
return True
cur = cur.next
if cur.item == item:
return True
return False

if __name__ == "__main__":
ll.append(3)
ll.insert(2, 4)
ll.insert(4, 5)
ll.insert(0, 6)
print "length:",ll.length()
ll.travel()
print ll.search(3)
print ll.search(7)
ll.remove(1)
print "length:",ll.length()
ll.travel()




`

Vieu3.3主题

Q Q 登 录