Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linked lists in C, with open source ADT

xanthu.com

Post reply on HN
Print view View original

21–30 of 43 posts

Re: Linked lists in C, with open source ADT

#21

Post by spinlocked »

AncoraImparo wrote: post #19

Sorry for posting this, it appears that HN is not the place to post content if your only goal is to help people to learn. The hacker ethic is dead I guess, Richard Stallman really was the last man standing then. Remind me to come and post something when I decide to make some silly iPhone / android app when I want to make money rather than sharing knowledge. Thanks.

Not at all. Thanks for posting OP. Any technical discussion is welcome here. Ignore the haters who think STL vectors are a drop in replacement for lists.

Re: Linked lists in C, with open source ADT

#22

Post by spinlocked »

tptacek wrote: post #17
AncoraImparo wrote: post #15

Earlier quoted context omitted.

It really does depend on what you need to be doing in order to make the assumption of what data structure is needed. A vector is all well and good for certain tasks, but sometimes, a list is what you need. I will cover vectors too, but for now I am focused on C. not C++. Thanks though.

You need a list when you have routine insertions somewhere besides the front or the back of the container, and you don't have routine random-access reads. The vector covers more cases and is generally more performant. Use whatever you like, though.

i disagree.

Re: Linked lists in C, with open source ADT

#23

Post by tptacek »

spinlocked wrote: post #22
tptacek wrote: post #17

Earlier quoted context omitted.

You need a list when you have routine insertions somewhere besides the front or the back of the container, and you don't have routine random-access reads. The vector covers more cases and is generally more performant. Use whatever you like, though.

i disagree.

... do go on.

Re: Linked lists in C, with open source ADT

#25

Post by tptacek »

spinlocked wrote: post #24
tptacek wrote: post #23

Earlier quoted context omitted.

... do go on.

see my post below your second highest voted comment on this thread.

http://yaserzt.com/blog/archives/615

"This result should not surprise any experienced programmers, but unfortunately it does many of us."

whistles

Re: Linked lists in C, with open source ADT

#28

Post by spinlocked »

spinlocked wrote: post #24
tptacek wrote: post #23

Earlier quoted context omitted.

... do go on.

see my post below your second highest voted comment on this thread.

This result should not surprise any experienced programmers, but unfortunately it does many of us.

1. for that workload the result should not really surprise anyone.

2. you are pointing to one pathological workload to make a point that vector performance is always better than lists?

Re: Linked lists in C, with open source ADT

#30

Post by marshray »

spinlocked wrote: post #20
tptacek wrote: post #5

The book _C Interfaces and Implementation_ is nothing but library interfaces like this and their implementations. You are, for whatever it's worth, better off defaulting to a variable-length array than to a linked list.

"insertions to the end of a variable-length array are very fast" really tptacek? its O(1) ammortized over time, and when N grows it becomes really slow because it involves reallocation and a linear copy of all elements.

You have a magic allocator for your list nodes that does better than O(1) amortized?
Post reply on HN