数据结构之双链表
一、双链表的结构
双链表由具有特定属性的节点构成，其中每个节点包含三个属性，一个信息属性和两个链接属性。信息属性指向该节点元素， 一个链接属性指向前一个节点，当此节点为第一个节点时，指向空值；而另一个链接属性指向下一个节点，当此节点为最后一个节点时，指向空值
class DoubleLinkedNode:
'''
双链表节点类
'''
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
二、一个双链表对象包含的操作
# is_empty() 链表是否为空
#
# length() 链表长度
#
# travel() 遍历链表
#
# add(item) 链表头部添加
#
# append(item) 链表尾部添加
#
# insert(pos, item) 指定位置添加
#
# remove(item) 删除节点
#
# search(item) 查找节点是否存在
三、实现一个双链表
class DoubleLinkedList:
'''
双链表类
'''
def __init__(self):
self.head = None
self.length = 0
def is_empty(self):
'''
判断链表是否为空
:return:
'''
return self.length == 0
def length(self):
'''
返回链表长度
:return:
'''
return self.length
def travel(self):
'''
遍历输出链表值
:return:
'''
cur = self.head
while cur is not None:
print(cur.item, " ")
cur = cur.next
def add(self, item):
'''
在链表头部插入item
:param item:
:return:
'''
node = DoubleLinkedNode(item)
if self.is_empty():
self.head = node
else:
node.next = self.head
self.head.prev = node
self.head = node
self.length += 1
def append(self, item):
'''
在链表尾部插入item
:param item:
:return:
'''
node = DoubleLinkedNode(item)
if self.is_empty():
self.head = node
else:
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = node
node.prev = cur
self.length += 1
def insert(self, pos, item):
'''
在链表pos位置插入item
:param pos:
:param item:
:return:
'''
if pos <= 0:
self.add(item)
elif pos >= self.length:
self.append(item)
else:
cur = self.head
node = DoubleLinkedNode(item)
while pos > 1:
cur = cur.next
pos -= 1
node.next = cur.next
cur.next.prev = node
cur.next = node
node.prev = cur
self.length += 1
def remove(self, item):
'''
删除链表中值=item的第一个元素
:param item:
:return:
'''
if self.is_empty():
return None
cur = self.head
# 删除链表第一个元素
if op.eq(cur.item, item):
# 链表只有一个元素
if cur.next is None:
self.head = None
# 链表有多个元素
else:
self.head = cur.next
cur.next.prev = None
self.length -= 1
return None
else:
while cur is not None:
if op.eq(cur.item, item):
cur.prev.next = cur.next
# 删除元素非链表最后一个元素
if cur.next is not None:
cur.next.prev = cur.prev
self.length -= 1
break
else:
cur = cur.next
| 
转播
