define a node: 定义一个节点
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
define a double-linkedlist: 定义一个双向链表
class DoubleLinkedList:
'''
the index begins at 0
'''
def __init__(self):
self.head = None
self.tail = None
self.length = 0
judge whethe the linkedlist is empty or not: 判断是否是空表
def IsEmpty(self):
if self.head == None:#you can also judge the tail
return True
else:
return False
add node at the head of linkedlist:添加新的头结点
def AddHead(self, val):
nodeNew = Node(val)
#judge whethe the linkedlist is empty or not
# if the list is not Null
if self.head:
nodeNew.next = self.head
self.head.prev = nodeNew
#if the linkedlist is Null,just intialize the list
#which means the head and the tail is the same node
else:
self.tail = nodeNew
self.head = nodeNew
self.length += 1
delete node at the head of linkedlist:删除头结点
def DeleteHead(self):
#firstly,if the list is Null
#not Null
if self.head:
# use id can make the judgement faster
if id(self.head) != id(self.tail):
temp = self.head
self.head.next.prev = None
self.head = self.head.next
temp.next = None
else :
self.head = None
self.tail = None
self.length -= 1
#Null
else:
print("the linkedlist is Null")
add node at the tail of linkedlist:添加新的尾节点
def AddTail(self, val):
nodeNew = Node(val)
if self.tail:
nodeNew.prev = self.tail
self.tail.next = nodeNew
# if the linkedlist is Null,just intialize the list
# which means the head and the tail is the same node
else:
self.head = nodeNew
self.tail = nodeNew
self.length += 1
delete node at the tail of linkedlist：删除尾节点
def DeleteTail(self):
# if the list is Null
if self.tail:
if id(self.tail) != id(self.head):
temp = self.tail
self.tail.prev.next = None
self.tail = self.tail.prev
temp.prev = None
else:
self.head = None
self.tail = None
self.length -= 1
else:
print("the list is Null")
add node in the middle of the linkedlist：在链表中插入新的节点
def InsertNode(self,insert_value,index):
"""
:param insert_value: the value you want to insert：插入的值
:param index:the value needs to be inserted just before the index-th node：在哪个节点后插入值
:return:no return
"""
if index > self.length:
print("error, overflow")
elif index == 0:
self.AddHead(insert_value)
elif index == self.length:
self.AddTail(insert_value)
else:
nodeNew = Node(insert_value)
nodeFind = self.head
while(index != 0):
nodeFind = nodeFind.next
index -= 1
nodeNew.next = nodeFind
nodeFind.prev.next = nodeNew
nodeNew.prev = nodeFind.prev.next
nodeFind.prev = nodeNew
self.length += 1
delete node in the middle of the linkedlist：删除某个节点
def DeleteNode(self, index):
'''
:param after_node: the index-th node to be deleted：需要删除的节点
:return: None
'''
if index >= self.length:
print("error, overflow")
elif index == 0:
self.DeleteHead()
elif index == self.length - 1:
self.DeleteTail()
else:
nodeFind = self.head
while(index != 0):
index -= 1
nodeFind = nodeFind.next
nodeFind.prev.next = nodeFind.next
nodeFind.next.prev = nodeFind.prev
nodeFind.next = None
nodeFind.prev = None
self.length -= 1
search node at the index-th：查找某个节点
def SearchNode(self, index):
'''
:param after_node: the index-th node to be deleted：需要删除的节点
:return: None
'''
if self.length == 0:
print("it is a null list")
return None
else:
nodeFind = self.head
while(index != 0):
index -= 1
nodeFind = nodeFind.next
return nodeFind.val
show the linkedlist in the form of string：将链表以字符串的形式展开
def __str__(self):
nodeHead = self.head
print_str=[]
while(nodeHead):
print_str.append(str(nodeHead.val))
if nodeHead.next:
print_str.append('-->')
if nodeHead.next.prev:
print_str.append('<--')
nodeHead = nodeHead.next
return ''.join(print_str)
逆转列表
##可以使用recursive和iterative 解决
def reverse(self):
if self.length == 1:
return self.head
tail = self.head
changed_number = tail.next
while(changed_number != None):
tail.next = changed_number.next
if changed_number.next:
changed_number.next.prev = tail
changed_number.next = self.head
self.head.prev = changed_number
changed_number.prev = None
self.head = changed_number
changed_number = tail.next
test:测试
A = DoubleLinkedList()
A.AddHead(2)
A.AddTail(3)
A.DeleteHead()
A.InsertNode(4,0)
A.InsertNode(4,0)
A.InsertNode(4,3)
A.DeleteNode(2)
print(A.SearchNode(2))
print(A)
