Doubly Linked Lists and Trees: To use or not to use?

Question

I've always been taught that the more pointers you need in a piece of code, the less elegant it is. Also, I know that the only data structure that you 'need' is a singly linked tree. As a result, I've always tried my best to avoid such atrocities as doubly linked lists and doubly linked trees.

Is this true? Is code really inelegant if you use pointers and doubly linked structures where fewer pointers or a singly linked structure is sufficient?

EDIT: Turns out there IS a clever way to avoid the doubly linked tree, by the way.

Answer 1

Your question has a semantic flaw: excessive X is too much. Too much is always a bad thing.

Any operation which can be done with pointers can also be done with arrays. That doesn't mean it should be. Lists, trees, queues: all have elegance when applied to suitable problems. Just because pointers were the last and most advanced topic in a CS class doesn't mean they should be used in all programs.

While pointers are a frequent source of programming errors, so are integer assignments. That doesn't mean we should avoid using either of them. Just write code which uses them in a straightforward and understandable manner.

Answer 2

The elegance is not not from the layout of the code, but also from the underlying functionality in the code.

Tree structures(e.g. a lot of famous binary search trees, disjoint sets) are actually very elegant and efficient.

Answer 3

I'd say that your code is inelegant if it's got pointers sprinkled throughout.

However, a well written data structure will abstract the fact that it's using pointers away from you, the client. As long as YOUR code isn't littered with pointers, and the data structure's API is minimal yet complete, I would have no qualms about using them.

As a matter of fact, I'd criticize anybody who eschewed data structures for a reason such as "too many pointers". I don't know who taught you that, but I'd unlearn it quickly. Use the right data structure for the task at hand and don't worry about pointers.