ansaurus

Question

Answer 1

+5 A:

If your linked list doesn't have loops, then the fact that this is a "linked list" is a memory detail, not a serialization detail. Just write the node values out into the file and build the next pointers when you deserialize.

However, if your linked list does have loops, then you'll need something smarter. You'll need to store next pointers as a file offsets to the node (or something similar) to encode the "link".

For each node in your linked list, store two words. The first is the data, the second is the offset of the next node. Here is an illustration of the circularly linked list:

 +-> 1234 -> 5678 -> 2398 -+
 |                         |
 +-------------------------+


0  : 4bytes: 1234 : int data  <------------+
4  : 4bytes:    8 : offset of next node -+ |
                                         | |
8  : 4bytes: 5678 : int data  <----------+ |
12 : 4bytes:   16 : offset of next node -+ |
                                         | |
16 : 4bytes: 2398 : int data  <----------+ |
20 : 4bytes:    0 : offset of next node ---+

Stephen 2010-06-22 03:31:33

@Stephen Thank you very much. But how can I store them in sorted order ?

mousey 2010-06-22 03:34:08

@mousey : You could sort them before serializing. Typically, you don't want your serialization routines to modify your data. In other words, you want `A == Deserialize(Serialize(A))`. If you start changing the order of elements, you're in trouble.

Stephen 2010-06-22 03:36:21

@Stephen If I add a new element that need to be in sorted order. do I need to deserialize the entire list for adding a new element ?

mousey 2010-06-22 03:42:12

@mousey : Probably. But, typically you don't serialize (and deserialize) every time you add an element to a list. You usually serialize it to send it over the network, store it on disk, etc. You may choose a different format altogether if the sorted property (and constant re-encoding) is important - when writing, always append to the back of the file and keep it sorted when you read it back in.

Stephen 2010-06-22 03:53:36

Also I have an another question. How to store the pointers ?

mousey 2010-06-22 04:32:51

since if I store the pointers there is no meaning

mousey 2010-06-22 05:02:15

@mousey : A pointer is just an address. You can't really store the pointers meaningfully. You can store 'pointers' to within the file by using file offsets. For example, `node->next` is at byte234 in the file, so seek there to read it. However, you'll need to deduplicate these references. You sound like a beginner, so consider if you really need this behavior.

Stephen 2010-06-22 12:29:43

No need to use anything as drastic as file offsets. Just a plain sequence number will do. That is, store each node as (conetent, next) where next is simple the number of nodes into the serialized list of the node references. If it hasn't been done yet, give it the next number and do it next. Simple. Trees are a little harder: use the 2n and 2n+1 ordering.

dmckee 2010-06-23 03:04:27

@dmckee : good call, straight sequence numbers will be easier than offsets.

Stephen 2010-06-23 03:12:01

@dash-tom-bang : yes... I was changing my example as I wrote it... forgot to update that. thanks.

Stephen 2010-06-23 17:00:54

ansaurus

tags:

views:

answers:

Need some help with serialization

related questions