Interesting question! The first two things that come to my mind are conjugacy classes (two permutations are equivalent if they have the same cycle structure), and so-called "toric permutations", introduced by Eriksson et al and which can be defined as follows.
Let $\pi$ be a permutation of {$1,2,\ldots,n$}. First, build a circular permutation $\pi^\circ=0\ \pi_1\ \pi_2\ \cdots\ \pi_n$, with indices taken modulo $n+1$ so that $0=\pi^\circ_0=\pi^\circ_{n+1}.$
This circular permutation can be read starting from any position, and the original ``linear'' permutation is reconstructed by taking the element following $0$ as $\pi_1$ and removing $0$.
Then, for $x$ in $\{0, 1, 2, \ldots, n\}$, let $\overline{x}^m = (x+m)\pmod{n+1}$, and define the following operation on circular permutations:
$$m+\pi^\circ=\overline{0}^m\ \overline{\pi_1}^m\ \overline{\pi_2}^m\ \cdots\ \overline{\pi_n}^m.$$
The toric permutation $\pi^\circ_\circ$ obtained from $\pi$ in $S_n$ is then defined as the set of permutations in $S_n$ reconstructed from all circular permutations $m+\pi^\circ$ with $0\leq m\leq n$, and we say that two permutations $\pi$, $\sigma$ in $S_n$ are torically equivalent if $\sigma\in\pi^\circ_\circ$ (or $\pi\in\sigma^\circ_\circ$), which we also write as $\pi\equiv^\circ_\circ\sigma$.
Example: let $\pi=\langle 3\ 1\ 5\ 2\ 4\ 6\rangle$; then $\pi^{\circ}=0\ 3\ 1\ 5\ 2\ 4\ 6$, and
$$
0+\pi^{\circ}= 0\ 3\ 1\ 5\ 2\ 4\ 6$$
$$
1+\pi^{\circ} = 1\ 4\ 2\ 6\ 3\ 5\ 0$$
$$
2+\pi^{\circ} = 2\ 5\ 3\ 0\ 4\ 6\ 1$$
$$
3+\pi^{\circ} = 3\ 6\ 4\ 1\ 5\ 0\ 2 $$
$$
4+\pi^{\circ} = 4\ 0\ 5\ 2\ 6\ 1\ 3 $$
$$
5+\pi^{\circ} = 5\ 1\ 6\ 3\ 0\ 2\ 4 $$
$$
6+\pi^{\circ} = 6\ 2\ 0\ 4\ 1\ 3\ 5 $$
which yields $\pi_{\circ}^{\circ}$={$\langle 3\ 1\ 5\ 2\ 4\ 6\rangle, \langle 1\ 4\ 2\ 6\ 3\ 5\rangle, \langle 4\ 6\ 1\ 2\ 5\ 3\rangle, \langle 2\ 3\ 6\ 4\ 1\ 5\rangle, \langle 5\ 2\ 6\ 1\ 3\ 4\rangle$, $\langle 2\ 4\ 5\ 1\ 6\ 3\rangle, \langle 4\ 1\ 3\ 5\ 6\ 2\rangle$}, and all permutations in that set are torically equivalent.
No guarantee as to how interesting the relations between $X_n(\rho)$ and $Y_n(\rho)$ will be in these cases, but that's something to start with.
It doesn't require linked lists, just arrays that can grow.
There's a Java applet online that implements it.
I'm sure there are other implementations online, but since I couldn't find any, as a start, here's a simple Python implementation. [Though it feels odd giving a programming answer here, and I'm sure several people here can write it much better!]
from bisect import bisect
def RSK(p):
'''Given a permutation p, spit out a pair of Young tableaux'''
P = []; Q = []
def insert(m, n=0):
'''Insert m into P, then place n in Q at the same place'''
for r in range(len(P)):
if m > P[r][-1]:
P[r].append(m); Q[r].append(n)
return
c = bisect(P[r], m)
P[r][c],m = m,P[r][c]
P.append([m])
Q.append([n])
for i in range(len(p)):
insert(int(p[i]), i+1)
return (P,Q)
print RSK('1364752')
Edit: Used binary search to improve from O(n3) to O(n2log n), which should matter only for very large permutations.
Best Answer
There are two closely related definitions which satisfy the properties you want.
First, consider the group $\Sigma_k$ of all bijections $\pi: \Bbb Z \to \Bbb Z$ such that $\pi(x+k) = \pi(x)+k$ for all $x$. Note that $S_k$ is a subgroup in $\Sigma_k$ - simply take any permutation of $\{1,\ldots,k\}$ and extend it periodically to all $x$. This group (introduced by Lusztig) is finitely generated and is closely related to affine Lie algebra $\widehat A_k$. The RSK algorithm does not exactly work here, but Lusztig does study the shape of Young diagrams (of what would be resulting two tableaux). The shape is a partition of $k$, and can be described using decreasing subsequences, extending Curtis Greene's theorem (I forgot if this is in Lusztig's paper or my own easy observation).
Second, a somewhat related definition is the group $\Phi_k$ of bijections $\pi: \Bbb N \to \Bbb N$ such that $\pi(x+k) = \pi(x)+k$ for all $x$ large enough. I studied this definition in this paper. This group $\Phi_k$ is also finitely generated. It is very suitable for RSK, which is not always, but sometimes invertible. The asymptotic shape I defined is essentially the same as Lusztig's. Neither I nor anyone else studied the infinite matrix extension. The infinite permutation version is already difficult enough.