It is the linker's job to link the function declaration to its implementation
This is not true. This is the compiler's job. Essentially the declaration (I'm assuming you mean the prototype, as in
return_type function_name (arguments...)) is part of the language to allow you to tell the compiler what the function looks like before the compiler finds its implementation (the code body between
A lot of functions in fact are declared at the same place they are implemented. However it is also common to declare function prototypes without an implementation in headers or in virtual classes. This basically tells the compiler "hey, this is what the function looks like, but you will find the implementation later or somewhere else".
By the time you run the linker it is no longer processing things like declarations. Instead, linkers deal only with compiled code and some of that code consists of functions.
The final binary code does not actually contain any function definitions. Instead, code is simply a long list of machine instructions. A function is simply an address to somewhere in the code. For example a function like
add() may be located at the 12566th byte of the binary code (or 0x00003116 in hex which is a more common way to look at addresses). The code that calls that function will simply be the instruction
call 0x00003116. At this stage there is no information that that location contains a function.
However linkers work with object (or library) files that contain metadata, not just pure binary code. The actual format of these files depend on a lot of things - the language you use, the operating system you are on, the type of file etc. (for example, obj files in C/C++, lib files on Linux, dll files on Windows, etc.). However, what these files must contain is a list of what is sometimes called "symbols" and what addresses those symbols point to. These symbols are basically the function signature which tells the linker things like what the function's name is in the source code, how many arguments the function accepts, etc. This list of symbols is usually called the symbol table.
Actually, during compilation the compiler keeps a data structure called the symbol table in RAM in order to remember what it has compiled. Once the code is compiled, the compiler will format this symbol table appropriately and insert it in the object or library file.
When the linker sees that some code is calling
add() it scans the list of files it is working on (or it looks up the database/array that it stored all the scanned files) and checks their symbol table to find
add(). Once found, it will replace the caller's symbol with the address of the
add() function (eg, 0x00003116). There is another step called the fixup which recalculates the address in RAM depending on how the executable or library file is loaded into RAM but I'll leave the details of that process as further research. It's enough to know that the linker's job is to load all the files you pass to it, remember all their symbol tables, and then replace symbols in code with actual addresses in memory.