双链无序表
class DoublyLinkedList():
def __init__(self,it=None):
self.head = None #表头作为index(0)
self.tail = None #表尾作为index(-1)
self.length = 0
if it is not None:
for d in it:
self.append(d)
def isEmpty(self):
return self.head is None
def size(self):
return self.length
__len__ = size
def getTail(self):
return self.tail
def add(self,item):#加为第一个
idx0 = Node(item)
if self.head is None:
# 第一个加入列表
self.head = self.tail = idx0
else:
# 原0的前一个设为idx0,idx0的后一个设置为原0
self.head.setPrev(idx0)
idx0.setNext(self.head)
#头指向idx0
slf.head = idx0
self.length += 1
def append(self,item):#加为最后一个
idx_1 = Node(item)
if self.head is None:
#第一个添加到列表
self.head= self.tail = idx_1
else:
#原最后一个的后一个设为idx_1,idx_1的前一个设置为原最后一个
self.tail.setNext(idx_1)
idx_1.setPrev(self.tail)
#尾指向idx_1
self.tail = idx_1
self.length += 1
def insert(self,idx,item):#加为idx个
current,n = self.head, 0
while n < idx:
current = current.getNext()
n += 1
#插入在current的前面
if current is None:
if self.head is None:
#这是第一个插入到列表的
self.add(item)
else:
#这是加为最后一个
self.append(item)
else:
#加在中间，idx节点添加到current的前一个
idx = Node(item)
idx.setNext(current)
idx.setPrev(current.getPrev())
if idx.getPrev() is not None:
idx.getPrev(.setNext(idx))
current.setPrev(idx)
self.length += 1
def index(self,item):
current, n = self.head, 0
while current is not None:
if current.getData() == item:
break
current = current.getNext()
n += 1
else:
return None
return n
def search(self,item):
return self.index(item) is not None
def delete(self,current):#删除current所引用的节点
#删除本节点
if self.head == current:
# 删除了第一个节点
self.head = current.getNext()
if self.tail == current:
#删除了最后一个节点
self.tail = current.getPrev()
if current.getPrev() is not None:
current.getPrev().setNext(current.getNext())
if current.getNext() is not None:
current.getNext().setPrev(current.getPrev())
self.length -= 1
def remove(self,item):
current = self.head
while current is not None:
if current.getData() == item:
self.delete(current)
break
current = current.getNext()
def pop(self, n = None):
if n is None:
n = self.length - 1
current,i = self.head, 0
while i < n:
current = current.getNext()
i += 1
dat =current.getData()
self.deleta(current)
return dat
def __str__(self):
tlist = []
current = self.head
while current is not None:
tlist.append(current.getData())
current = current.getNext()
return str(tlist)
__repr__ = __str__
#lst[9],lst[1:3:2]
def __getitem__(self,key):
if isinstance(key,int):
#按照下标
current, i = self.head,0
while i < key:
current = current.getNext()
i += 1
if current is not None:
return current.getData()
else:
raise StopIteration
elif isinstance(key,slice):
start = 0 if key.start is None else key.start
stop = self.lenth if key.stop is None else key.stop
step = 1 if key.step is None else key.step
current, i = self.head, 0
#定位到strat
while i < strat:
current = current.getNext()
i += 1
#开始拷贝
dcopy = DoublyLinkedList()
while i < stop:
dcopy.append(current.getData())
s = step
while current is not None and s > 0:
current = current.getNext()
s -=1
i += step
#返回拷贝
return dcopy
def __eq__(self, other):
if other is None or not isinstance(other,DoublyLinkedList):
return False
if len(self) != len(other):
return False
for s,o in zip(self, other):
if s != o:
return False
else:
return True
