Data Structure in Prolog

Theoretically speaking, Prolog does not have any data structure.
One uses function symbols to represent the intended data
structures.

Example.

Suppose we want to represent lists 

()     by     nil
(a)    by     cons(a, nil)
(a b)  by     cons(a, cons(b, nil)),  etc.

Then, we write the program append as 

append(nil, X,X).
append(cons(A, L1), L2, cons(A, L3)) :- append(L1, L2, L3).


After the file is loaded, we execute

| ?- append(cons(a1, cons(a2, nil)), cons(b1, nil), Q).

Q = cons(a1,cons(a2,cons(b1,nil))) ? 

yes




It's perfectly legal to use any function names you 
like to represent lists

append(e, X, X).
append(c(A, L1), L2, c(A, L3)) :- append(L1, L2, L3).
p(W) :- append(c(a1, c(a2, e)), c(b1, e), W).

By this definition, you mean lists are represented as
()     by    e
(a)    by    c(a, e)
(a b)  by    c(a, c(b, e)),  etc.

| ?- append(c(a1, c(a2, e)), c(b1, e), Q).

Q = c(a1,c(a2,c(b1,e))) ? 

yes


BUILTIN LIST STRUCTURE:

For the reason of efficiency, there is a builtin list structure.

Lists are represented as
[]           :  empty list
[a, b, c]    :  a list  of three elements
[a, b | L]   :  a list of elements a, b and the rest is L

Under this builtin structure, we can write 

append([], X, X).
append([A| L1], L2, [A|L3]) :- append(L1, L2, L3).

p(W) :- append([a1, a2], [b1], W).
q(X,Y) :- append(X,Y,  [a1, a2]).

% execute the queries

| ?- p(A).

A = [a1,a2,b1] ? 

yes
| ?- q(A,B).

A = [],
B = [a1,a2] ? ;

A = [a1],
B = [a2] ? ;

A = [a1,a2],
B = [] ? ;

no