3 ms·
A lot of the focus in the HN comments is on ArrayLists, but I'm curious why the author chose to give linked lists an O(1) insert time. In some implementations (
by altendo 10y ago
A lot of the focus in the HN comments is on ArrayLists, but I'm curious why the author chose to give linked lists an O(1) insert time. In some implementations (doubly linked list, inserting at the head of the list) I can see the O(1) time, but when appending to the end it also is O(n) because one has to traverse the entire list of elements before updating the link at the end of the list. Might just be nitpicking here but that might also be affecting the author's results.
- tbirdz 10y agoJust keep a pointer to the head and tail of the list. You can then append to either end of the list in O(1). When you put a new node at the tail end, use the tail pointer to get to the tail node instead of walking the whole list. Of course, you need to make sure the head/tail pointers are always updated to point to the current head/tail of the list.