# Untitled

unknown

plain_text

a year ago

1.3 kB

1

Indexable

Never

^{}

void Stack::push(int inputData){ auto *newNode = new StackNode(); //O(1) newNode->next = nullptr; //O(1) newNode->data = inputData; //O(1) if(head) { //In the worst case, this loop goes through every node till it reaches the last node. //Thus, the time complexity is O(n) where n is the number of elements in the linked list. StackNode* current = head; while(current->next){ current = current->next; } current->next = newNode; }else{ head = newNode; //O(1) } } //The time complexity for the push method (based on the worst possible scenario) is O(n) bool Stack::pop(){ if(!head){ //O(1) return false; } StackNode* previous{}; //O(1) StackNode* deletedNode = head; //O(1) //In the worst-case scenario, this loop will run n times(number of nodes in the list). This makes it O(n) for time complexity. while(deletedNode->next){ previous = deletedNode; deletedNode = deletedNode->next; } delete deletedNode; //O(1) //all O(1) since the below are just comparisons. if(previous) { previous->next = nullptr; }else{ head = nullptr; } return true; } //The time complexity for the pop method (based on the worst possible scenario) is O(n)