和单链表类似，只不过是增加了一个指向前面一个元素的指针而已。
示意图：
2. 单链表代码实现
def __init__(self,val,p=0):
'''
创建双链表的数据结构 数据节点--下一个节点--上一个节点
:param val: 数据节点
:param p:
'''
self.data = val
self.next = p
self.prev = p
class LinkDBList(object):
def __init__(self):
'''
初始化 默认指向0
'''
self.head = 0
def __getitem__(self, key):
'''
取到对应的值
:param key:
:return:
'''
if self.is_empty():
print('linkList is empty')
elif key < 0 or key > self.getLength():
print("the given key is error")
else:
self.getItem(key)
def __setitem__(self, key, value):
'''
根据传入的参数 设置对应的key-value
:param key: 索引
:param value: 对应的值
:return:
'''
if self.is_empty():
print('linkList is empty')
elif key < 0 or key > self.getLength():
print("the given key is error")
else:
self.delete(key)
self.insert(key,value)
def initlist(self,data):
'''
传输的数组 转换成双链表
:param data: 待转换的数组
:return: 双链表
'''
self.head = Node(data[0])
p = self.head
for i in data[1:]:
node = Node(i)
p.next = node
node.prev = p
p = p.next
def getLength(self):
p = self.head
length = 0
while p != 0:
length += 1
p = p.next
return length
def is_empty(self):
if self.getLength() == 0:
return True
else:
return False
def clear(self):
self.head = 0
def append(self,value):
'''
将key-value 添加到链表的尾部
:param key:
:param value:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
p = self.head
while p.next != 0:
p = p.next
node = Node(value)
p.next = node
node.prev = p
def getItem(self,key):
'''
根据提供的key索引 获取对应的值value
:param key:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
p = self.head
length = 0
while p.next != 0 and length < key:
p = p.next
length += 1
if length == key:
return p.data
else:
print("the data is not exist")
def insert(self,key,value):
'''
根据提供的key,value 插入到对应的链表中
:param key:
:param value:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
if key < 0 or key > self.getLength():
print("the given key is error")
return
if key == 0:
q = self.head
node = Node(val=value,p=key)
self.head = node
node.next = q
q.prev = node
return
p = self.head
post = self.head
length = 0
while p.next != 0 and length < key:
post = p
p = p.next
length += 1
if key == length:
node = Node(key,value)
post.next = node
node.prev = post
node.next = p
p.prev = node
def delete(self,key):
'''
删除对应索引的节点
:param key:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
if key < 0 or key > self.getLength():
print("the given key is error")
return
if key == 0:
self.head = self.head.next
return
p = self.head
post = self.head
length = 0
while p.next != 0 and length < key:
post = p
p = p.next
length += 1
if key == length:
p = p.next
post.next = p
p.prev = post
def index(self,value):
'''
根据value匹配链表中的index
:param value:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
p = self.head
index = 0
while p.next != 0 and not p.data == value:
p = p.next
index +=1
if p.data == value:
return index
else:
return -1
def node(self,key):
'''
根据索引查找对应的节点
:param key:
:return:
'''
if self.is_empty():
print("linkList is empty")
return
p = self.head
index = 0
while p.next != 0 and index < key:
p = p.next
index += 1
if index == key:
return p
def allData(self):
'''
返回所有的链表data
:return:
'''
if self.is_empty():
print("linkList is empty")
return
p = self.head
index = 0
datas = []
while p.next != 0 and index < self.getLength():
datas.append(p.data)
p = p.next
index += 1
return datas
网友评论