Linked lists in C, with open source ADT • Hacker News Board

Re: Linked lists in C, with open source ADT

#11

Post by AncoraImparo » Sun, Jan 20, 2013, 2:31 AM UTC

stuffihavemade wrote: post #8

AncoraImparo wrote: post #3

Earlier quoted context omitted.

Not everyone went to university, and people have to learn from somewhere. It is also only an introduction, there will be more complicated data structures shown soon, and algorithms. No point in jumping into the heavier stuff. Trying to help people who are new to C.

Is it appropriate for Hacker News though? It fits better on http://www.reddit.com/r/learnprogramming

See, thats more constructive! :) I figured it belonged here, especially since a lot of people are probably still interested in learning things like this, I was not aware of a reddit for this.

Re: Linked lists in C, with open source ADT

#12

Post by AncoraImparo » Sun, Jan 20, 2013, 2:32 AM UTC

afhof wrote: post #4

On the front page, "test.c" is listed twice. Should it be "list.c" ?

I will fix, I hadn't realized! Thankyou!

Re: Linked lists in C, with open source ADT

#13

Post by tptacek » Sun, Jan 20, 2013, 2:38 AM UTC

gosu wrote: post #10

This isn't how I'd do a linked list in C. Having to malloc separate storage for the next/prev pointers imposes a big cost in terms of performance (it's hardly O(1)) and robustness. Your linked list operations can all fail now - sooner or later, that's going to put you in a very tight spot. I prefer to store next/prev pointers with the data itself, and to use offsetof/containerof to find a pointer to the data struct w…

This problem is why you're better off with something like a C++ vector (a variable-length array).

Re: Linked lists in C, with open source ADT

#14

Post by tptacek » Sun, Jan 20, 2013, 2:39 AM UTC

afhof wrote: post #7

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.

Someone wants to know about linked lists, and your comment is to use some other data structure that has a different purpose?

Different purpose?

Re: Linked lists in C, with open source ADT

#15

Post by AncoraImparo » Sun, Jan 20, 2013, 2:43 AM UTC

tptacek wrote: post #13

gosu wrote: post #10

This isn't how I'd do a linked list in C. Having to malloc separate storage for the next/prev pointers imposes a big cost in terms of performance (it's hardly O(1)) and robustness. Your linked list operations can all fail now - sooner or later, that's going to put you in a very tight spot. I prefer to store next/prev pointers with the data itself, and to use offsetof/containerof to find a pointer to the data struct w…

This problem is why you're better off with something like a C++ vector (a variable-length array).

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.

Re: Linked lists in C, with open source ADT

#16

Post by afhof » Sun, Jan 20, 2013, 2:45 AM UTC

tptacek wrote: post #14

afhof wrote: post #7

Earlier quoted context omitted.

Someone wants to know about linked lists, and your comment is to use some other data structure that has a different purpose?

Different purpose?

Linked lists are good for adding and removing elements. Variable length arrays are good for allocating a known amount of space at runtime.

Re: Linked lists in C, with open source ADT

#17

Post by tptacek » Sun, Jan 20, 2013, 2:45 AM UTC

AncoraImparo wrote: post #15

tptacek wrote: post #13

Earlier quoted context omitted.

This problem is why you're better off with something like a C++ vector (a variable-length array).

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.

Re: Linked lists in C, with open source ADT

#18

Post by tptacek » Sun, Jan 20, 2013, 2:46 AM UTC

afhof wrote: post #16

tptacek wrote: post #14

Earlier quoted context omitted.

Different purpose?

Linked lists are good for adding and removing elements. Variable length arrays are good for allocating a known amount of space at runtime.

The "variable" in "variable length" describes the fact that you don't know how much space you need, and insertions to the end of a variable-length array are very fast. I can see why you thought my comment was weird, now.

Re: Linked lists in C, with open source ADT

#19

Post by AncoraImparo » Sun, Jan 20, 2013, 2:49 AM UTC

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.

Re: Linked lists in C, with open source ADT

#20

Post by spinlocked » Sun, Jan 20, 2013, 2:53 AM UTC

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.