3 ms·
My understanding is that push/pop from the front/back of linked lists are constant time, but that inserts in the middle necessitate looping through the linked l
by penetraitor69 6y ago
My understanding is that push/pop from the front/back of linked lists are constant time, but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.
- dragontamer 6y ago> but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation. Not if you save the node you are working on. Inserting (when you have a node) is simply: NewNode = malloc(...) or new or something. NewNode.next = node.next node.next = NewNode
- penetraitor69 6y agoOh, gotcha; I just meant in the general case.