def append(self, item):
# adds an item at the end of the list
new_node = DLinkedListNode(item,None,None)
current = self.__head
# Start the traversal
if self.__size == 0: # check if list is empty
self.add(item)
else:
while (current.getNext()!=None):
current= current.getNext() # traversing the list
new_node.setNext(None)
new_node.setPrevious(current)
current.setNext(new_node)
self.__size = self.__size +1
В этом методе, в частности, он будет иметь время выполнения O (n), так как я должен пройти по списку, чтобы получить доступ к концу списка. Тем не менее, это кажется ненужным, так как у меня есть атрибут self .__ tail. Тем не менее, когда я реализую это, он возвращает ошибку, что объекты типа None не имеют атрибута setNext. Ниже показано, как я это реализовал.
def append(self, item):
# adds an item at the end of the list
current=self.__tail
new_node = DLinkedListNode(item,None,None)
new_node.setPrevious(self.__tail)
self.__tail=new_node
current.setNext(new_node)
new_node.setNext(None)
self.__size+=1
Что, если это сработает, даст O (1), что является лучшим решением. Поэтому мне было интересно, что у меня за проблема и как ее исправить? Это для задания в классе, и они вынуждают меня использовать unpythoni c методы, поэтому, пожалуйста, имейте это в виду. Ниже остальная часть моего кода со второй версией метода добавления, включая тест. Любая помощь будет очень полезна вместе с объяснениями, так как я понимаю, что это очень важно для интервью.
class DLinkedListNode:
# An instance of this class represents a node in Doubly-Linked List
def __init__(self,initData,initNext,initPrevious):
self.data = initData
self.next = initNext
self.previous = initPrevious
if initNext != None:
self.next.previous = self
if initPrevious != None:
self.previous.next = self
def getData(self):
return self.data
def setData(self,newData):
self.data = newData
def getNext(self):
return self.next
def getPrevious(self):
return self.previous
def setNext(self,newNext):
self.next = newNext
def setPrevious(self,newPrevious):
self.previous = newPrevious
class DLinkedList:
# An instance of this class represents the Doubly-Linked List
def __init__(self):
self.__head=None
self.__tail=None
self.__size=0
def search(self, item):
current = self.__head
found = False
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
return found
def index(self, item):
current = self.__head
found = False
index = 0
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
index = index + 1
if not found:
index = -1
return index
def add(self, item):
new_node=DLinkedListNode(item,None,None)
new_node.setNext(self.__head)
self.__head=new_node
current=self.__head
new_node.setPrevious(None)
current=current.getNext()
self.__size+=1
def remove(self, item):
# remove the node containing the item from the list
if self.__size == 0:
raise Exception('List is Empty')
current = self.__head
previous = None
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if not found:
raise Exception('Item not in list')
else:
if previous == None: # the item is in the first node of the list
self.__head = current.getNext()
else: # item is not in the first node
previous.setNext(current.getNext())
self.__size = self.__size -1
def append(self, item):
# adds an item at the end of the list
current=self.__tail
new_node = DLinkedListNode(item,None,None)
new_node.setPrevious(self.__tail)
self.__tail=new_node
current.setNext(new_node)
new_node.setNext(None)
self.__size+=1
def insert(self, pos, item):
assert type(pos)==int,'Error:pos is not an integer'
assert pos>=0,'Error:pos must be positive'
current=self.__head
new_node= DLinkedListNode(item,None,None)
if pos==0:
self.add(item)
elif pos==self.__size:
self.append(item)
elif pos>self.__size:
raise Exception('Position attempted to enter is larger than the size of linked list.')
else:
current_pos=0
while(current.getNext()!=None):
if (pos)==current_pos:
right=current
left=current.getPrevious()
right.setPrevious(new_node)
left.setNext(new_node)
new_node.setPrevious(left)
new_node.setNext(right)
return True
current=current.getNext()
current_pos+=1
self.__size+=1
def pop1(self):
current = self.__head
previous = None
while (current.getNext() != None):
previous = current
current = current.getNext()
if (previous == None):
self.__head = None
else:
previous.setNext(None)
self.__size -= 1
return current.getData()
def pop(self, pos=None):
if pos!=None:
assert pos<=self.__size,'Pos must be within list'
assert type(pos)==int,'Pos must be an int'
assert pos>=0,'Pos must not be negative'
current=self.__head
current_pos=0
if pos==(self.getSize()-1) or pos==None:
data_from_method=self.pop1()
return data_from_method
else:
while current.getNext()!=None:
if pos==current_pos:
data=current.getData()
left=current.getPrevious()
right=current.getNext()
left.setNext(right)
right.setPrevious(left)
return data
current_pos+=1
current=current.getNext()
def searchLarger(self, item):
current=self.__head
current_pos=0
while current.getNext()!=None:
if item<current.getData():
return current_pos
current=current.getNext()
current_pos+=1
return -1
def getSize(self):
return self.__size
def getItem(self, pos):
assert type(pos)==int,'position must be type int'
assert abs(pos)<=self.__size,'Position is outside of the list'
if pos>=0:
current=self.__head
current_pos=0
while current!=None:
if current_pos==pos:
return current.getData()
current_pos+=1
current=current.getNext()
elif pos<0:
current_pos=0
current=self.__tail
while current!=None:
if current_pos==pos:
return current.getData()
current_pos-=1
current=current.getPrevious()
def __str__(self):
# returns a string representation of the list
current = self.__head
string = ''
while current != None:
if current.getNext()==None:
string = string + str(current.getData())+''
else:
string=string+str(current.getData())+' '
current = current.getNext()
return string
def test():
int_list=DLinkedList()
for i in range(0, 1000):
int_list.append(i)
print(int_list)
if __name__ == '__main__':
test()