linked list, big O
I am learning linked list, some sites are saying that insertion and deletion are O(1) and others are saying O(n). I understood why it is saying O(n) because It need to go through all the list to get to where you want to insert or delete, and I also understood O(1) since it is the one step when you are at the position you want to insert or delete. But I want to know, what is right to say? If i was in job interview or something like, what would be the correct answer, what would the interviewer expect me to say? Should I say O(n) or O(1).
The correct answer is to ask for more information.
-What's the time complexity of inserting into a linked list?
-Do you have a pointer to the node adjacent to the insertion point, or do you have to search for it?
IMO I'd say insertion before or after a node and search are two distinct operations, so insertion should be said to be O(1) and search to be O(n), period.
-What's the time complexity of inserting into a linked list?
-Do you have a pointer to the node adjacent to the insertion point, or do you have to search for it?
IMO I'd say insertion before or after a node and search are two distinct operations, so insertion should be said to be O(1) and search to be O(n), period.
it depends!
an unsorted / unordered list is O(1). you *always* just insert at head**: new guy, new guy -> next = old head, head = new guy, done!
a sorted / ordered list, though, is "while not at the place you want to be, current = current-> next" followed by the insert.
so the correct answer on an interview is that it depends on whether it is sorted or not. If they say one or the other, give the right answer.
... do interviewers still ask this stuff frequently? This is not the sort of thing I have seen in a very long time.
**ok, you can do the tail too, if you want to hold an extra pointer.
an unsorted / unordered list is O(1). you *always* just insert at head**: new guy, new guy -> next = old head, head = new guy, done!
a sorted / ordered list, though, is "while not at the place you want to be, current = current-> next" followed by the insert.
so the correct answer on an interview is that it depends on whether it is sorted or not. If they say one or the other, give the right answer.
... do interviewers still ask this stuff frequently? This is not the sort of thing I have seen in a very long time.
**ok, you can do the tail too, if you want to hold an extra pointer.
Last edited on
| do interviewers still ask this stuff frequently? |
Yes - but usually only in the context of an incomplete problem/question. At an interview, given the limited info given, the correct answer would be to ask for further details as per other comments above. Someone who actually gave a straight answer any answer - would probably fail. Asking a question without giving the context or required info to answer the question is a used interview technique. It tests that the candidate can think, see what's missing and ask the relevant question(s).
The other way to answer this type of question is to start by stating assumptions and giving an answer for different assumptions/situations.
In either case, its to make you think and not just to quote answer(s) from a book without understanding.
Topic archived. No new replies allowed.