A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
3 of 7 added 50 characters in body

You might use set operations: complement and union.

Assuming that recent notifications limited to 100.

Set<Notification> updateNotifications(Set<Notification> persisted, Set<Notification> recent) {
    Set<Notification> newNotifications = complement(recent, persisted);
    save(newNotifications);

    if (recent.size() < 100) {
        return union(persisted, newNotifications);
    }

    Set<Notification> obsoleteNotifications = complement(persisted, recent);
    delete(obsoleteNotifications);

    return newNotifications;
}