Storing Address Data Model
When working with addresses, one thing you may consider -- at least give it a serious look -- is using the USPS to convert the user-supplied address into the USPS standard address. So the same address, just with different abbreviations or punctuations, will converge to the same address. There are several remote apis the Post Office makes available to your app.

As for the database, yes, the literature shows that the place to put a 1-to-many FK is in the "many" tuple. You have also stated you want to maintain a history of address changes so this format makes even more sense.

However, there are many advantages to having a 1-to-many intersection table. This is similar to a many-to-many intersection table except that one side is made part of the PK to enforce the "1" side of the 1-to-many cardinality.

create table OneToMany(
  OneID    int   not null
    references UserTable( ID ),
  ManyID   int   not null
    references AddressTable( ID ),
  TypeID   char( 1 ),    -- 'H' for Home, 'W' for work, etc.
  constraint PK_OneToMany primary key( OneID, TypeID )
);


Each user has only one entry for each kind of address and even if multiple users share the same address, if one user moves to a different address, the other users are not affected.

There is a small alteration needed to maintain the history of changes. All that is needed is the addition of a datetime field.

create table OneToMany(
  OneID    int   not null
    references UserTable( ID ),
  ManyID   int   not null
    references AddressTable( ID ),
  TypeID   char( 1 ),    -- 'H' for Home, 'W' for work, etc.
  Effective datetime not null default NOW,
  constraint PK_OneToMany primary key( OneID, TypeID, Effective )
);


Now all changes are maintained and it is very easy to look back at any time in the past to see what the address was at that time. Here is an answer I posted that will refer you to more information. Mine is not the accepted answer, and I would highly recommend you take the time to become familiar with both mine and the accepted answer. Choose the one (or design your own with what you learn) that is best for your situation.