Is it possible to perform CRC checks on Linked Lists?

[Susanne Strege]

Hello... I'm wondering if it is possible to perform a CRC or Checksum on the
data contained in a simple Linked List that uses pointers to nodes???

 

[Ben Pfaff]

Hello... I'm wondering if it is possible to perform a CRC or Checksum on the
data contained in a simple Linked List that uses pointers to nodes???

Yes.

 

[Eric Sosman]

Hello... I'm wondering if it is possible to perform a CRC or Checksum on the
data contained in a simple Linked List that uses pointers to nodes???

Yes. Are you having trouble doing this in C?

 

[Susanne Strege]

I'm having trouble finding out how to get a valid running checksum without
having to perform a checksum on the entire list each time a new node is
added to the list. This running checksum would then have to match with the
checksum performed on the entire list in the case of a system crash.
CRCWholeList == CRCRunning.

If I performed a checksum on the data contained in each node and then added
them up would the order matter? i.e... CRC(node 1) + CRC(node 2) + CRC(node
3) == CRC(node 3) + CRC(node 2) + CRC(node 1)

 

[Eric Sosman]

A: Because it's confusing.

Q: Why do people object to top-posting?

[Top-post corrected in the quoted material.]

I'm having trouble finding out how to get a valid running checksum without
having to perform a checksum on the entire list each time a new node is
added to the list. This running checksum would then have to match with the
checksum performed on the entire list in the case of a system crash.
CRCWholeList == CRCRunning.

If I performed a checksum on the data contained in each node and then added
them up would the order matter? i.e... CRC(node 1) + CRC(node 2) + CRC(node
3) == CRC(node 3) + CRC(node 2) + CRC(node 1)

For a checksum, it's easy because addition is commutative
and associative: When you add up the first three natural numbers
it doesn't matter whether you compute (1+2)+3 or 1+(2+3) or even
(3+1)+2; you get the same sum anyhow. So if you've added up all
the data items in an existing list and obtained the checksum X,
when you tack on a new item with the value 42 the new checksum
is X+42. Furthermore, the new checksum is X+42 no matter where
the new item is added: at the end, at the beginning, or somewhere
in the middle. (For extra credit, what would the new checksum be
if you *removed* an item whose value was 42? For extra extra
credit, what would the new checksum be if you neither inserted
nor deleted an item, but changed the value in an existing item
from 42 to 31?)

For CRC it's trickier, because the CRC operation is neither
commutative nor associative (this is intentional; you want 1/2/3
to produce a different CRC than 1/3/2). However, if the new item
is always added at the end of the list things are tractable. Take
a look at how you're computing the CRC: You initialize with some
value X0, and then incorporate the first item with X1 = f(X0,I1).
Then you do X2=f(X1,I2), X3=f(X2,I3), ..., Xn=f(X[n-1],In) and
hand back Xn as the CRC. If there'd been n+1 items you'd have
gone through exactly the same sequence of steps and gotten exactly
the same results, except you'd have also done X[n+1]=f(Xn,I[n+1]).
So if you remembered the CRC (Xn) from before, you need only one
more step to compute the new CRC (X[n+1]). Handling deletions at
the end shouldn't be too difficult. Handling insertions and
deletions at the front of the list might be possible; I haven't
really studied it. Handling insertions and deletions at arbitrary
positions in the list looks daunting.

So, with this much outline: Are you having trouble expressing
this in C?

 

[Robert B. Clark]

I'm having trouble finding out how to get a valid running checksum without
having to perform a checksum on the entire list each time a new node is
added to the list. This running checksum would then have to match with the
checksum performed on the entire list in the case of a system crash.
CRCWholeList == CRCRunning.

This is possible.

If I performed a checksum on the data contained in each node and then added
them up would the order matter? i.e... CRC(node 1) + CRC(node 2) + CRC(node
3) == CRC(node 3) + CRC(node 2) + CRC(node 1)

See now, you're talking about two different things.

A CRC (cyclic redundancy check) is not the same as a simple checksum.

A CRC would be sensitive to the order in which the data was processed; a
checksum would not be.

Google on "CRC algorithm" for more information.