Is linkage within an object considered an anti-pattern?

Question

Suppose you have a class that is frequently (or even exclusively) used as part of a linked list. Is it an anti-pattern to place the linkage information within the object?

For example:

   public class Item
   {
       private Item prev; 
       private Item next;
       ...
   }

An often-cited recommendation is to simply use a generic container class (such as java.util.LinkedList in Java), but this creates the overhead of having a separate node object (and the linked object cannot readily refer to its siblings).

Thoughts?

Haywoodhayyim

Answer 1

It is not necessarily an anti-pattern. Anti-patterns must have negative side-effects to earn the right to the "anti".

For example, a Node in a Tree data structure would need it's linkage cached inside of the Node. Anything else would violate the much more important concept of encapsulation and localization of data and code based on responsibility of the object.

On the other hand, a Customer data structure that embeds its "next" customer would imply that the Customer data structure is handling two unrelated responsibilities, that of maintaining the Customer data, and that of maintaining the Customer's list data structure. In such a scenario, the two responsibilities could intermingle in ways that impact the ease of maintenance; and hence, would be seen as an anti-pattern.

Hindu

Answer 2

I think so. It seems to me that you're mixing responsibilities (e.g. if your objects reflect employees, I'd expect to only see employee related properties and methods, not methods and properties related to linked lists).

Sometimes a little overhead is the cost of having "cleaner" designs. Whether or not you're willing to pay for that overhead is a different question. In my opinion, the little overhead added by using utilities like the built-in linked lists is worth it... it saves development time, is thoroughly tested and makes for a cleaner design.

Glandulous

Answer 3

It's an anti pattern if it's not always used in a linked list. You'll end up with a swiss army if you add properties/methods to your classes that you might need. Read about YAGNI.

Adding those methods will also break SRP since the item will also be responsible of keeping track of it's siblings.

Ibadan

Answer 4

In general this is a recommended against because of the creep of features you will need in the future. Even if you don't need features like 'search' and 'sort' currently, someday the specs will change and you'll need to sort your items. If you implement it this way, now you need to implement a sort.

The included linked lists are there because they've been tried, trusted, and debugged. Writing your own function for these is just duplicating a lot of work that's not necessary.

In addition, your worry about having the overhead of an extra object node shouldn't really be too much of a worry - how much extra overhead could it be? In days like today even if they were a kilobyte (which would be crazy) it shouldn't add up to a worry.

Antiicer

Answer 5

I believe the XML DOM classes in java do (something like) what you describe, so there's at least precedent for it. Generally what you describe is probably the exception not the rule because otherwise you just end up re-implementing a linked list.

Minta

Answer 6

In Java, it's less of a problem than other languages, since the Item must be a class pointer. If, on the other hand, Item is a struct, as is possible with C# and other languages, you run into obvious problems. Besides the fact that you've got a mutable struct, you'd also probably get a compile-time error trying to define a struct with an infinitely large memory requirement.

Depending on requirements, it may be much simpler to allow objects to refer to their siblings through next and previous, the way an object in a hierarchy can often refer to it's parent by having a reference to it.

Imco

Answer 7

This pattern is called an invasive container.

It's not the right thing to do in every situation, but it has some well-known advantages (lower memory usage, better locality, fewer objects for the memory manager to allocate and collect).

Lordling

Answer 8

As always, depends on the scope of your project and/or on the context in which this is used. If the project is rather small, following every single good-practice guideline won't be very helpful: you'll just end up spending more time doing it 'properly' and the benefits might be almost nil.

If your project is somewhat big, but this linked list is only used locally, like inside a single source file, or as a private member of a class (in other words, if it's an implementation detail, and not part of the overarching mechanism), then you can also skip doing it 'properly' and take the simpler approach.

Only when the project is large and the linked list is an important piece of the puzzle should you spend time doing it as flawlessly as you can. As a rule of thumb, if more than one source file needs this linked list, then do it properly, don't cut corners.

In general, know when and how to spend your energy. There's a very fine line to walk between writing correct and robust code and over-engineering.

Facelift