Хорошо, чтобы предисловие, это, чтобы помочь с школьным заданием. Я понимаю, что в следующем коде есть методы unpythoni c, но на этом они настаивают. В моем методе вставки у меня есть 4 случая для учета. Все они рассматриваются должным образом, кроме как иначе, и я не уверен, почему. По какой-то причине метод insert не обновляет связанный список, чтобы включить new_node, когда этот new_node не помещается в конец или начало списка. Я не уверен, почему это так, поскольку в соответствующей позиции мы сохраняем старое значение current, затем мы сохраняем его предыдущее и устанавливаем current = new_node, затем мы устанавливаем new_node next, чтобы быть старым значением current, а предыдущий new_node равным старые токи предыдущие. Я не понимаю, почему это не сработает.
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
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
def insert(self, pos, item):
# inserts the item at pos
# pos should be a positive number (or zero) of type int
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:
# storage is a holder variable
storage=current
right=current.getNext()
left=current.getPrevious()
current=new_node
new_node.setPrevious(left)
new_node.setNext(storage)
return True
current=current.getNext()
current_pos+=1
self.__size+=1
# doubly linked list
#Hello(prev)<-->World(store data)-->None
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()
# doubly linked list
#Hello(prev)<-->World(store data)-->None
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 pos<=self.__size,'Position is outside of the list'
current=self.__head
current_pos=0
if pos>=0:
while current!=None:
if current_pos==pos:
return current.getData()
current_pos+=1
current=current.getNext()
else:
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():
new_list=DLinkedList()
for i in range(20):
new_list.insert(i,i)
new_list.insert(1,90)
print(new_list)
test()