2.6 Linked lists

Define two pointer arrays defined as follows:

- (for ``head of chain''); its -element contains the largest particle number of all inhabitants of cell .
- ( ``linked list''); number of the next (i.e. lower) particle in the presently treated cell; when that cell is finished.

In a language-free (but Fortran-like) form, proceed as follows:

do 100 k=1,ncell // where usually ncell=M^3 100 hoc(k)=0 do 200 i=1,n icell=1+int(x(i)/cl) //where cl=l=L/M +int(y(i)/cl)*M +int(z(i)/cl)*M*M ll(i)=hoc(icell) hoc(icell)=i 200 continue

These few quick steps may be performed at each MD or MC step to update the linked-cell pointer arrays. When it comes to calculating interactions, these arrays provide the information about possible partner molecules.

For clarity, consider this example:

After nulling all arrays, the codelet does this:

i=1 icell=5 ll(1)=0 hoc(5)=1 i=2 icell=9 ll(2)=0 hoc(9)=2 i=3 icell=9 ll(3)=2 hoc(9)=3 i=4 icell=6 ll(4)=0 hoc(6)=4 i=5 icell=3 ll(5)=0 hoc(3)=5 i=6 icell=6 ll(6)=4 hoc(6)=6

Later, when it comes to scan the lists (force or energy calculation), we proceed thus:

For a particle (no. ) in cell , we have to scan cells where the brackets denote those cells which in our example are empty of partners.

icell=3: hoc(3)=5 ---> compute (1-5) ll(5)=0 icell=6: hoc(6)=6 ---> compute (1-6) ll(6)=4 ---> compute (1-4) ll(4)=0 icell=9: hoc(9)=3 ---> compute (1-3) ll(3)=2 ---> compute (1-2) ll(2)=0

F. J. Vesely / University of Vienna