News for hackers. Stuff that matters.

A comment on Drop millions of allocations by using a linked list (2015). Parent comment

Re:Drop millions of allocations by using a linked list (2015) by penetraitor69 on Friday March 12, 2021 @02:24PM (#26439763)
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.
[ Parent | on HN ]
Re:Drop millions of allocations by using a linked list (2015) by dragontamer on Friday March 12, 2021 @03:36PM (#26440579)
> 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
[ Parent | on HN ]
Re:Drop millions of allocations by using a linked list (2015) by penetraitor69 on Friday March 12, 2021 @04:05PM (#26440916)
Oh, gotcha; I just meant in the general case.
[ Parent | on HN ]