# Searching linked lists that contain lists?

Following the advice I've read here and other sites, I've been trying to use the Mathematica equivalent of a linked lists...

testList = {{a, b}, {{c, d}, {{e, f}, {}}}}


Now, I want to see if {c,d} is a member of testList. How do I do that? MemeberQ doesn't transverse the list recursively and Flatten also nukes the sub lists. The following seems to work but I would expect there to be a cleaner simpler way...

memberInLinkedList[{}, _] = False;
memberInLinkedList[l_List, v_] := True /; First[l] == v;


Is there a more eloquent or built-in way to do this? Perhaps a general idiom or package that handles this transparently?

• What exactly is l in the original definition of testList? Sep 11, 2013 at 17:30
• @Shredderroy I think l and testList are the same. Sep 11, 2013 at 17:42
• Indeed, sorry about that. Sep 11, 2013 at 18:19
• You could use a head different than List for the linked list to avoid the flattening issue
– Rojo
Sep 11, 2013 at 18:43

MemberQ[testList, {c, d}, Infinity]


True

b1[x_] := Module[{f, res},
f[{x, R_}] = True;
f[{L_, R_}] := f[R];
f[#] /. f[{}] -> False
] &

Block[{$RecursionLimit = 1*^6,$IterationLimit = 1*^6},
{
MemberQ[ll, {86, 99}, Infinity] // timeAvg,
t7[{86, 99}][ll] // timeAvg,
b1[{86, 99}][ll] // timeAvg
}
]


{0.0196000, 0.00751200, 0.00321600}

• Well that's really weird; I thought I tried this form and it was slower, which surprised me. I guess failed to properly clear a definition during testing. +1! Back to testing. :-) Sep 12, 2013 at 15:36
• I can't think of any approach to try to improve this. You win. Sep 12, 2013 at 15:44
• b1 works fine with L1 but not with L2: L=Partition[Range@8,2]; L1=Fold[{#2,#}&,{},L]; L2=Fold[{##}&,{},L]; b1[#][L1]&/@L (*{True,True,True,True}*); b1[#][L2]&/@L (*{f$200,f$201,f$202,f$203}*) Sep 12, 2013 at 20:24
• @RayKoopman As Mr.Wizard I didn't convert this output to False. Now I fix it. Sep 12, 2013 at 20:33
• I still get the same kind of f$xxx sequence. Sep 12, 2013 at 21:23 ## Methods revisited ybeltukov posted a cleaner version of t7 that made me feel rather silly. (Thanks ybeltukov; it will teach me to be more careful about clearing definitions while experimenting!) I can't beat it, so instead I'll try to refine it. First, several of my functions and his b1 do not return False on a failure to match, so this should be corrected. Second, one should incorporate extension of $IterationLimit into the function. It would then look something like this:

t8[linked_, x_] :=
Module[{f},
Block[{$IterationLimit = ∞}, f[{x, R_}] = True; f[{}] = False; f[{L_, R_}] := f[R]; f @ linked ]] t8[ll, {86, 99}]  True  ### A crash with most methods I discovered that on longer linked lists all the methods suggested so far cause a kernel crash. ybeltukov confirmed that this problem also affects version 9.0.1. Examples: SeedRandom RandomInteger[99, {500000, 2}]; ll = Fold[{#2, #} &, {}, %]; MemberQ[ll, {86, 99}] (* kernel crash *) Cases[ll, {86, 99}, -1, 1] (* kernel crash *) ll /. {86, 99} :> Return[True] (* kernel crash *)  One way around this problem is to manage a stack manually as Daniel did here. t9[linked_, pat_] := Module[{R = linked, L}, While[R =!= {}, {L, R} = R; If[MatchQ[L, pat], Return @ True]; ]; False ]  Now: SeedRandom RandomInteger[99, {500000, 2}]; ll = Fold[{#2, #} &, {}, %]; t9[ll, {86, 99}]  True  This is not as fast as b1/t8 however. ### Original answer If you did not have MemberQ you could still walk the tree recursively. Here are several ways to do that: t1[x_] := MatchQ[#, {x, _} | {_, _?#0}] & t2[x_][{L_, R_}] := MatchQ[L, x] || t2[x][R] t3[x_] := Module[{f}, f[{L_, R_}] := MatchQ[L, x] || f[R]; f] t4[x_] := MatchQ[#[], x] || #0 @ #[] &  All functions have the syntax: tfunc[pattern][linkedlist]. Sometimes these are even faster than MemberQ: SetAttributes[timeAvg, HoldFirst] timeAvg[func_] := Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}] SeedRandom RandomInteger[99, {50000, 2}]; ll = Fold[{#2, #} &, {}, %]; MemberQ[ll, {86, 99}, Infinity] // timeAvg  0.01148  Block[{$RecursionLimit = 1*^6},
timeAvg @ #[{86, 99}][ll] & /@ {t1, t2, t3, t4}
]

{0.01812, 0.007112, 0.00612, 0.008736}


### More experiments

Using the syntax tfunc[pat, list] is somewhat faster, i.e. this is faster than t2:

t5[x_, {L_, R_}] := MatchQ[L, x] || t5[x, R]


A bit faster still is shifting this to a form that is iterative:

t6[x_, {L_, R_}] /; MatchQ[L, x] = True;
t6[x_, {L_, R_}] := t6[x, R]


The fastest I found so far is combining this iterative form with the dedicated function a la t3:

t7[x_] :=
Module[{f},
f[{L_, R_}] /; MatchQ[L, x] = True;
f[{L_, R_}] := f[R];
f
]


Timings for these three variations:

Block[{$RecursionLimit = 1*^6,$IterationLimit = 1*^6},
{
t5[{86, 99}, ll] // timeAvg,
t6[{86, 99}, ll] // timeAvg,
t7[{86, 99}][ll] // timeAvg
}
]

{0.00624, 0.005864, 0.005368}


I find it fairly impressive that t7 is twice is fast as MemberQ in this application.

• I haven't tried them all but, at least t7 breaks in here when you serach for something that isn't there
– Rojo
Sep 12, 2013 at 21:07
• @Rojo Yes; I believe t6 does as well. That's what I meant when I said "First, several of my functions and his b1 do not return False on a failure to match ..." I posted t5/t6/t7 in a hurry and I didn't do a good job. I also tried the cleaner form and somehow convinced myself it was slower. I hope that t8 fixes these problems. Sep 12, 2013 at 23:33
• @Mr.Wizard Can you add that crash depends on system stack size? For example on Linux you can run Mathematica as ulimit -s 65536 && mathematica and the problem disappears. Sep 13, 2013 at 12:30
• @ybeltukov It will have to wait a couple of days if I do it. I don't have ulimit in Windows AFAIK so I'd need to use another tool, and I'd like to test it before making claims myself. I don't mind if you edit this answer to note your findings. Sep 13, 2013 at 13:49

[Edit: I forgot to include the modified m2 needed for the LL-headed linked lists. I'm including an improved (faster) version.]

Here are a couple of ways:

m1[l_, pat_] := Catch[l /. pat /; Throw[True] :> Null; False];
m2[l_, pat_] := NestWhile[Last, l, # =!= {} && ! MatchQ[First@#, pat] &] =!= {};


Leonid Shifrin suggests in this answer using a special head for linked lists if the elements of the linked list are to be lists themselves. For example,

testLL = LL[{a, b}, LL[{c, d}, LL[{e, f}, LL[]]]]


One can then use Flatten to get a flat expression:

Flatten[testLL, Infinity, LL]
(* LL[{a, b}, {c, d}, {e, f}] *)


Then MemberQ (and other such functions) can be used more or less normally:

MemberQ[Flatten[testLL, Infinity, LL], {c, d}]
(* True *)


If LL has the attribute HoldAllComplete, as in Leonid Shifrin's answer, we can mark the end of the linked list with Throw like this:

testLL2 = LL[{a, b}, LL[{c, d}, LL[{e, f}, LL[Throw["endLL"]]]]]


Then we can modify m2 as follows:

m2LL[l_, pat_] :=
Catch[NestWhile[Last, l, ! MatchQ[First@#, pat] &]; True] /. "EndLL" -> False


If NestWhile gets to the end of the linked list, First@# will execute the Throw.

Timing tests

Using Mr.Wizard's data (updated to include Throw["EndLL"] to mark the end of the list ll2):

SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] := Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}]

SeedRandom;
data = RandomInteger[99, {50000, 2}];
ll = Fold[{#2, #} &, {}, data];
ClearAll[LL];
SetAttributes[LL, HoldAllComplete];
ll2 = Fold[LL[#2, #] &, LL[Throw["EndLL"]], data];


Timing:

m1[ll, {86, 99}] // timeAvg
m2[ll, {86, 99}] // timeAvg
MemberQ[ll, {86, 99}, Infinity] // timeAvg


0.00949383
0.0142940
0.0301806

Below are (updated) timings on the LL linked lists. It is interesting that MemberQ with Flatten is faster than MemberQ with a level spec. of Infinity.

m1[ll2, {86, 99}] // timeAvg
m2LL[ll2, {86, 99}] // timeAvg
MemberQ[Flatten[ll2, Infinity, LL], {86, 99}] // timeAvg


0.00865924
0.01107858
0.0227578

Mr.Wizard's t7 is about as fast as m1. A comparison with MemberQ is included.

Block[{$RecursionLimit = 1*^6,$IterationLimit = 1*^6},
t7[{86, 99}][ll] // timeAvg]


0.00860823

But t7 is faster than m1 on patterns that don't match (or match near the end):

Block[{$RecursionLimit = 1*^6,$IterationLimit = 1*^6},
t7[{86, 999}][ll] // timeAvg]
m1[ll2, {86, 999}] // timeAvg


0.064016
0.074637

(Update: Of course @ybeltukov's b1 beats both t7 and m1.)

• +1 for m1 -- very nice :-) Sep 12, 2013 at 15:30
• @Mr.Wizard Thanks! Nesting Last was conceptually appealing, too, and it avoids having to deal with recursion limit (not particularly important in this case). Your recursive approach is clearly superior. Sep 12, 2013 at 18:00