It is my question in midterm. I know to used recursion, loop to find length of cstring but its complexity time is not o(1). Moreover, i have to find length of cstring of all node then add them, so is it possible it has complexity time is o(1)?
CodePudding user response：
If the problem is "given a linked list of N nodes, find the sum of length of the string in each node", then you can't achieve better time complexity than O(N) because you need to look at each node at least once - assuming finding the length of a string is O(1).
However, if the problem is "given an empty linked list and a sequence of insert/delete/query operations", then you can maintain the sum of length of strings throughout the operations.
CodePudding user response：
Singly linked list with cstring, how to find sum of length of all nodes in singly linked list with complexity time is o(1)?
The time to traverse N nodes of a linked list scales as o(N), without even considering what work you do with each node. It follows, then, that if you want to be able to compute anything about a linked list in o(1) time then you need to be able to do it without traversing more than o(1) of the nodes (necessary but not sufficient condition).
Therefore, no, it is not possible to perform the computation in o(1) time. But it is possible to amortize the cost of the computation across the linked-list insertions and deletions so that you can retrieve the result in o(1) time. However, this does require a data structure that supports it.
For example, if you have a structure representing the whole list then you can track a running sum there, and update it with each insertion and deletion. Or if you have only nodes then you can give the node structure a dynamically-allocated pointer to storage for the sum. With proper management, that would access the same running sum from any node.
But if you are not in control of the data structures involved or at least of the data stored in them (e.g. to mangle the stored strings to carry extra data) then you would need to compute the wanted length sum on demand, and that costs ω(N), which means it is not o(1).