22

Let's say you are engineering a chat room software.

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);

This room (parent) now has a client (child).

client.on('message', (event) => {
   // With the above code, room must be found
   let room = rooms.FindClientsRoom(client);
   if(room){
       room.handleMessage(event);
   }
});

Or we have a child that knows about its parent

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);
client.setRoom(room);


client.on('message', (event) => {
   let room = client.getRoom();
   if(room){
       room.handleMessage(event);
   }
});

This is incredibly fast compared to looking for a client within 1000s of rooms. But is there something wrong with the design pattern? In any system, such as XML, do child nodes know about their parents? Should they?

5
  • 7
    For what it’s worth, the web’s DOM model lets you do this, with Element.parentNode.
    – JW01
    Jul 25 '20 at 23:25
  • 2
    The efficient version of rooms.FindClientsRoom would be to have a map of client to room. That shouldn't be much slower than storing the room on the client. I assume it's slow now because you're looping over all rooms. Jul 26 '20 at 14:14
  • 4
    You are essentially asking what data structure is the most appropriate for your data. There is always a trade-off with speed and size somewhere. Jul 27 '20 at 11:02
  • Should child nodes have a reference to their parents? If they need them, yes. If they don't, no. The better question is, When do child nodes require a reference to their parents? Something you might find an answer to here, or here
    – J...
    Jul 28 '20 at 10:38
  • .... this design implies that a client is only "in" one room at a time, which isn't how (modern) chat systems work. Usually, you can be connected to multiple rooms, and clients aren't "owned" by rooms, but are their own separate entity. Jul 28 '20 at 16:27
92

Your question is basically the same as "should linked list items have a reference to the previous item?", and the answer is the same: it depends. There are use cases when a singly-linked list is correct, and there are use cases when a doubly-linked list is correct.

The important point here is that it is the use case that matters, not the format: XML does not specify whether child nodes know about their parents, that is a matter of the design of the parser which reads the XML and creates in-memory data structures for it. Some parsers will do this, other ones won't.

If you need a quick lookup from your child nodes to the parent nodes, then put it in. If you don't, Keep It Simple S... and don't have them.

7
  • 5
    I wouldn't say a linked-list is quite the same, as with that all nodes are the same type (even if the data stored in the node can be of different types), whereas here you could have different types and you'd be coupling those types together more strongly by having one contain a reference to the other. It also depends how you use that reference, of course. Jul 26 '20 at 14:08
  • 11
    @BernhardBarker Considering that headers and footers and NULL can often not be the same type of node, I'd say your comment isn't fully accurate. Regardless, the point still stands - you need a reference to next but do you need a reference to prev? Well, it depends on whether what you're doing.
    – corsiKa
    Jul 26 '20 at 20:29
  • 1
    Excellent answer. You can think of it this way: Maintaining a doubly linked-list is never strictly necessary to traverse a data structure, but by storing a little bit of redundant data you can speed up the process considerably. That's the essence of a cache, and there is nothing implicitly wrong with a cache. Caches do make things more complicated though, so yes, only build one if you need it.
    – Douwe
    Jul 27 '20 at 15:15
  • @corsiKa Do you always need a reference to next if your use case only involves walking it backwards? Jul 27 '20 at 19:56
  • @BlokeDownThePub You cannot only walk backwards. The first direction you have is always forwards.
    – corsiKa
    Jul 27 '20 at 20:01
9

Personally, I think the first pattern you showed to be a mistake. As you pointed out, it takes a lot of time to find the room.

The general problem with the second pattern is that it makes reference counting garbage collection fail. (This issue varies by language.)

What you missed is that there is a third pattern. Specifically, that the events to the client can identify the room. This works well if the events are coming from the room. It doesn't work well if the events are from an unrelated external source.

You might also want to consider if a client can be associated with multiple rooms.

2
  • The last point can be addressed in the second design by making Client.room an array. So setRoom becomes addRoom.
    – Barmar
    Jul 27 '20 at 15:02
  • Many languages have the concept of a weak reference to address the garbage collection problem - only one of the bidirectional references is considered a normal "strong reference", and if only weak references remain, attempts to dereference them will return NULL. This is used to create doubly-linked lists in C++.
    – TheHans255
    Jul 28 '20 at 21:09
7

If you're doing this on a chat server application, then you should use a database. The most common database design for a tree is that parents do not have references to their children, only the child have foreign key reference to their parents. Instead, the parent to child relation should be handled by an index.

If you're doing this in a chat client application, then don't worry too much about it. Even the heaviest chat software users aren't going to have more than hundred room or so simultaneously, don't worry about performance and pick the simplest implementation that makes your life and future maintenance easy rather than worrying about negligible performance differences.

4

In most tree models you want to know the parent of nodes, you will likely have a use case for it. You already mentioned your own use case and keeping track of parents is cheap so it is a no-brainer.

In other tree applications you typically want the node to be able to tell you its path, and its level (or depth). For this you also need the parent. It is a common thing to take onboard for tree nodes.

3
  • "keeping track of parents is cheap" - until somebody handcrafts the code to do this in a multi-threaded environment and the subtle bugs cause data corruption... Jul 26 '20 at 11:48
  • @PhilipKendall Whether the tree is a UI control or a document or something else, in a multi-threaded context you would have to marshall any action on the tree to the appropriate thread. Adding a parent property would not change that. So I am afraid I do not understand your point. Jul 26 '20 at 14:19
  • 3
    "marshall any action on the tree to the appropriate thread" - that's a brute force way of doing it. With careful locking of the appropriate parts of the data structure, you don't need to do all your actions on one thread. But my point is really that people try to do this and get it wrong, and when you're dealing with bidirectional links there's a lot more opportunity to get it wrong than if you're updating unidirectional links. Jul 26 '20 at 14:26
3

In general terms, you're adding an edge connecting Client and Room.

If this is a real world example, this is a poor model to make it a parent-child relationship. As others have pointed out, you may have to extend it to multiple client-room relationships which breaks a single back-pointer from Child -> Room.

This may seem wildly unrealistic but, say someone has more than one chat window open - they are now in more than one room at a time.

Even if you were modeling physical presence, a booking system would have to cope with the person who books more than one room on behalf of others (common) or books a long slot for one room whilst in the middle having an overlapping short use of another.

In-memory you can model such edges as a hash key in a dictionary that is a combination of client + room ID. This would continue to be a fast lookup.

That approach also extends easily to databases adding such records with a composite key.

It has a secondary benefit that you can save these edge records over time, showing a history of the relationships.

1

Trees are used for a variety of purposes, some of which are facilitated by having child nodes hold parent pointers, and some of which would require that child nodes not have parent pointers.

If child nodes have references to their parents, than a reference to a child can effectively identify both a tree and location within it. On the other hand, making a snapshot of a tree's state will require making a copy of all the nodes therein.

If tree nodes are immutable, and modifications to a tree are performed by producing a modified tree node and replacing referencces to the original with references to the modified version, then code may take a snapshot of a tree merely by copying a reference to its current root node.

Each approach is excellent for some purposes, but will work poorly for some others. Depending upon what you're doing with trees, either approach may work better. Alternatively, it may be useful to use a hybrid approach in which every tree node object is either referenced by exactly one tree, or will never be modified. I can't think offhand of situations where it would be useful for non-shared nodes to have parent references, but they could do so.

1

A mentioned in other answers already; what to do depends on the requirements.

Add a link from the child back to the parent if you regularly and/or quickly need to be able to find the parent from the child. Don't add a link if there's no reason to, or if the cost of adding this link outweighs the benefit (e.g. additional resources used, additional code to write & maintain, more complexity in determining when garbage collection can occur).

Regarding how you go about implementing such a relationship though, I'd say it's important to have the logic defined in one place. i.e. If you've decided that a child should always reference its parent then don't use the following to set that relationship:

room.addClient(client);
client.setRoom(room);

Instead, have your addClient method perform the setRoom operation for you; so you don't have to remember to call the two methods together each time you need this operation to take place.

function addClient(Client client) {
    this.clients.Add(client);
    client.joinRoom(this);
}

... And have the same logic in place in any operations to remove the relationship:

function removeClient(Client client) {
    this.clients.Remove(client);
    client.leaveRoom(this);
}

Note: I've also used joinRoom instead of setRoom, and passed this to leaveRoom. Those allow you to easily change your client from being able to have a single parent to multiple, should you choose to switch your approach.

-1

Adding new fields requires more memory. The difference between the first and second approach is more CPU vs more RAM usage. As they can be a tradeoff, need to decide which one to optimize depending on the application.

1
  • Feedback is welcome with the downvote. Note, other answers have not mentioned memory usage.
    – gregn3
    Jul 29 '20 at 11:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.