Don't do this in Salesforce please.

dont_do_this.cls

// Salesforce attracts programmers that have spent too much time using the same languages 
// their whole life, without appropriate 'adventures' into other languages.  It shows sometimes.
// IMO APEX doesn't really go out of its way to advertise its various collection types like Python
// or scripting languages & functional languages do.  As a result, you end up reinventing the wheel a lot.

// Wrong way, don't do this.

        List<Id> LstParentId = new List<Id>();    
    
        if (newList != null)
        {
            for (SObject newObj : newList) {
                boolean fAlreadyExist = false;
                For(id idCurrent : LstParentId)
                {
                    if (idCurrent == (Id)newObj.get('ParentId__c'))
                    {
                        fAlreadyExist = true;
                    }
                }
                if (!fAlreadyExist)
                {
                    LstParentId.Add((Id)newObj.get('ParentId__c'));
                }
            }    
        }
            
        if (oldList != null)
        {
            for (SObject newObj : oldList) {
                boolean fAlreadyExist = false;
                For(id idCurrent : LstParentId)
                {
                    if (idCurrent == (Id)newObj.get('ParentId__c'))
                    {
                        fAlreadyExist = true;
                    }
                }
                if (!fAlreadyExist)
                {
                    LstParentId.Add((Id)newObj.get('ParentId__c'));
                }
            }    
        }

// What is wrong?  For one, you are repeating code on many different levels.  Let's fix that.
// PS, this is still wrong.

        for (List<SObject> l : new List<List<SObject>> {newList, oldList}){
          if (l != null){
            for (SObject newObj : newList) {
                boolean fAlreadyExist = false;
                For(Id idCurrent : LstParentId)
                {
                    if (idCurrent == (Id)newObj.get('ParentId__c'))
                    {
                        fAlreadyExist = true;
                    }
                }
                if (!fAlreadyExist)
                {
                    LstParentId.Add((Id)newObj.get('ParentId__c'));
                }
            }
          }
        }

// You may complain that there is an "additional heap allocation";
// please wake up, we are on SFDC, not doing assembly on a micro controller.
// You are far more limited by code size (3mb total) than in-memory allocations.

// ------

// The other problem is poor collection choices.  What are you actually doing in this loop?  
// You are trying to get unique IDs from a list of objects.  

// Lists are good for when order matters, but order does not matter in this example.
// What matters is the unique IDs.

// APEX has the Set object, which typically keeps an  *unorganized, unique collection of objects. 
// Using Sets, Your code becomes this:

Set<Id> set_parent_id = new Set<Id>();    
for (List<SObject> l : new List<List<SObject>> {newList, oldList}){
    if (l != null){
        for (SObject obj : l) {
            set_parent_id.add((Id)obj.get('ParentId__c'));
        }
    }
}

// 8 Lines vs. 36 lines; much easier to keep tabs on.
// * SFDC set order is predictable (which is weird for those of us from other languages).  It doesn't matter though.
// http://releasenotes.docs.salesforce.com/en-us/summer15/release-notes/rn_apex_maps_and_sets_iteration_order.htm

In python it would have been;

ids = {x.id for x in new_list} | {y.id for y in old_list}

Don't tell the enterprise programmers, they are busy creating factory factories.

In US.SFDC, it would be:

Set<Id> set_parent_id = new Set<Id>();
set_parent_id.addAll((List<Id>) US.OL(newList).pluck(List<Id>.class, 'ParentId__c'));
set_parent_id.addAll((List<Id>) US.OL(oldList).pluck(List<Id>.class, 'ParentId__c'));