class Node(object):
def __init__(self,elem):
self.elem = elem
self.next = None
self.prev = None
#属性
class DoubleLinkList(object):
def __init__(self,node = None):
self._head = node
#一个单链表的私有方法头结点指向空
def is_empty(self):
return self._head ==None
def length(self):
Cur = self._head
count = 0
while Cur != None:
count+=1
Cur = Cur.next
return count
#已经包含空链表的情况
def travel(self):
#遍历
Cur = self._head
while Cur != None:
print(Cur.elem,end=' ')
Cur = Cur.next
print('')
def append(self,item):
node = Node(item)
if self.is_empty():
self._head = node
else:
Cur = self._head
while Cur.next != None:
Cur = Cur.next
Cur.next = node
node.prev = Cur
def add(self,item):
node = Node(item)
node.next = self._head
self._head.prev = node
self._head = node
def insert(self,pos,item):
node = Node(item)
cur = self._head
if pos<=0:
self.add(item)
return
elif pos > self.length():
self.append(item)
else:
curpos = 0
while curpos != pos:
curpos+=1
cur = cur.next
cur.prev.next = node
node.prev = cur.prev
node.next = cur
cur.prev = node
def Search(self,item):
cur = self._head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
def remove(self,itme):
cur = self._head
if self.Search(itme):
while cur != None:
if cur.elem == itme:
if cur == self._head:
#正好是第一个节点
self._head = cur.next
if cur.next:
#判断链表是否只有一个节点
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
return
else:
cur = cur.next
else:
raise Exception('Not include !!!')
if __name__ == '__main__':
ll = DoubleLinkList()
for i in range(5):
ll.append(i)
ll.travel()
ll.insert(2,52)
ll.travel()
print(ll.Search(52))
ll.remove(52)
ll.travel()
ll.remove(4)
ll.travel()
ll.remove(0)
ll.travel()
要多考虑特殊情况。
