What is the difference between shouldn't have done something and needn't have done something?
Everything was okay. You needn't have worried.
Can we say you shouldn't have worried instead of needn't ... ?
In general, "should not" and "need not" have significantly different meanings.
"Should not" indicates that it is bad to do a particular thing. For example, you should not drive a car too fast, because driving too fast is dangerous.
"Need not" indicates that it is not bad not to do a particular thing (in other words, the thing is unnecessary). For example, before you get in a car and drive it, you need not look inside the fuel tank to see if there is fuel there, because the car has a fuel gauge which tells you whether or not there is fuel. However, it is still okay to look inside the fuel tank if you want.
A synonym of "need not" is "don't need to". Examples: "you don't need to turn on the headlights", "you didn't need to worry".
If you say "you shouldn't have worried", then what you are saying is "worrying was a bad thing to do", and that may be a little bit rude to say. It would probably be better to say "you needn't have worried" (or "you didn't need to worry").
As Phil14 mentions in his comment, "you shouldn't have ..." has a note of reprimand, but this can vary with context:
You shouldn't have brought donuts, I'm on a diet.
(mild reprimand, equivalent to "I wish you hadn't done that")
Hey, you brought donuts! You shouldn't have!
(zero reprimand, equivalent to "Thanks!")
"You needn't have" can also indicate disapproval, but to a lesser degree. As P. E. Dant mentions in his comment, it can sound archaic or overly polite to some, but that shouldn't stop you from using it.
This is fairly confusing in that "should not do" and "need not do" are not equivalent negations of "should" and "need".
"Need not do" is as you would expect, the opposite of "need to do" - "not need to do". These things are the opposite of a requirement and are therefore optional.
However "should not do" is much closer to a positive requirement ("should") to "not do" something. In either case, "should" or "should not", there is an obligation relating to a verb.
"You need not walk in the road" - but you can if you like
"You should not walk in the road" - so don't
All of the above applies equally to the future perfect "should not have" and "need not have".
I think there is a little difference between them.
1) You shouldn't have worried.
It means that there were some reasons to worry but those weren't enough.
2) You needn't have worried.
It means that it was just unnecessary to worry.
shouldn't have done can have meanings along a spectrum or gradient from
it was wrong or a bad idea to do it
you were under no obligation to do it
and the same is true for needn't have done whose meanings extend from
there was no compelling reason to do it
you were under no obligation to do it
So you can see that there is overlap between the two words.
We brought you some flowers to welcome you back.
-- That was very nice of you, but you needn't|shouldn't have done that.
Nobody wanted the kittens so I drowned them in a sack.
-- You needn't|shouldn't have done that. I'm sure if we had waited a little longer, we would have found homes for them.
Technically they are the same in meaning, the differences are only in the context.
With that said, I should add that in my experience "you should not have done" often also means that what you've done was a mistake, you've done something wrong or the speaker is mad at you.
On the other hand "you need not have done" is more "gentle", it doesn't really convey that negative meaning unless of course the context has it. And I should point out that some people consider the usage of the verb need as a modal verb archaic or even incorrect, and often non-native speakers (usually who learned BrE) may not even understand it.