Hacker News Reader

Comment by e19293001 | Hacker News Reader

e19293001

I've gone through a lot of exercises[0][1] from this site especially on how to implement a linked list in C. The time spent from the tutorial was absolutely worth while. I feel happy and satisfied with my self after solving one problem at a time.

For those who already know the syntax of C but wanted to learn more, the links I mentioned is a good exercise and opens up a lot of possibilities on what you can implement. You'll soon be able to realize the importance of linked list and why you'll want to use a linked list instead of just plain arrays.

[0] - http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

[1] - http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

View on HN

My favourite language is Lisp, in which I use "linked" lists all the time, but I never use them in C. Use of lists without a garbage collector and either dynamic typing (as in Lisp) or strong static typing (as in Haskell) is a pain, and C has none of these built in. This means that, in C, you need to allocate memory every time you add something to your list, and hold the pointer to it in order to free it later. You also need to keep track of which types are stored, and where.

If your problem requires a lot of list processing, use a language more suitable for it. Otherwise, use extensible arrays, which are easy to implement in C.

conceit also pointed out that lists also increase the likelihood of cache misses, which slows down the program a little bit. Many C programmers care about that. I don't share their priorities - it is important to me, but less so than correctness, ease of programming (allowing more time for exploration and finding a more efficient algorithm), and response times.

Meh, sometimes there are easier ways than GC.

Just allocate all the list items from a big pool of memory that you own. When you're done, throw the whole lot away in one go. Languages like C++ tend to encourage micromanagement of data but it's not the only way to do things.

To the contrary, linked lists are cache killers and hardly used nowadays. Or so they say on here, if I understand correctly.

> hardly used nowadays

https://github.com/torvalds/linux/search?utf8=%E2%9C%93&q=IN...

That's unbearable. They should just redo this in JavaScript. That's what everyone uses nowadays. Or so they say on here, if I understand correctly.

https://github.com/charliesome/jsos

I tried to appreciate your response, but I cannot fairly judge the code. For example, those could be performance uncritical parts of code or remnants of 20 year old code where the cache was less effective than now. Are 2000 search results a lot in a source of this size?

Cache, as opposed to 20+ years ago, or whenever the pattern was developed, is indeed a thing that everyone is using just now.

Linked lists are the default "goto" data structures for Haskell and many other functional languages, such as Lisp.

Storing strings as a linked list of characters in Haskell was a design mistakes imho, which lead to the proliferation of various efficient string types implemented in libraries.

Some operations are faster on linked list than on vectors (insert on beginning, or on specified iterator position, delete iterator position). They also use less memory in some use cases. I was once optimizing transactional tree structure which internally used std::vector in each node. In most real use cases there was just one item in each vector, but vector preallocated 16 items. So changing to linked list lowered memory consumption significantly without measurable performance impact. The same applied for hash table vs. RB tree. All basic data structures can be useful, you just have to choose proper one.

IMHO, linked lists can be useful in conjunction with other data structures without hurting performance too much. An open hash table with a linked list in each bucket need only involve pointer chasing in case of collisions, which can be made arbitrarily rare by making the number of buckets large enough. In this way, there's a graceful performance degradation under unexpectedly heavy loads rather than hard limitations. I would be interested to read well informed contrasting opinions.

Sweeping statements like this are almost always unilaterally false.

The best data structure or algorithm to use is usually problem-dependent.

Do you mean mine or the OP's, which evoked my response?

> ... why you'll want to use a linked list instead of just plain arrays

How on earth can you make such a statement about a fundamental data structure? Please, take CS101 before you you start throwing these kind of assertions around.

Reply on news.ycombinator.com