About

This is an implementation of circular double linked lists built on top of the standard LSL functions. An example double-linked list is a list containing the elements in order: 10, 99 and 37. Every node contains the value (either 10, 99 or 37) as well as a forward pointer to the next node and a reverse pointer to the previous element. Due to the circularity a circular list does not have a first or last element.

$\begin{tikzpicture}[list/.style={rectangle split, rectangle split parts=3, node distance=20mm, draw, rectangle split horizontal}] \node[list,on chain] (A) {\nodepart{second} 10}; \node[list,on chain, right of=A, right=10mm] (B) {\nodepart{second} 99}; \node[list,on chain, right of=B, right=10mm] (C) {\nodepart{second} 37}; %\node[on chain, draw, inner sep=6pt, right of=C, right=10mm] (D) {}; \draw (D.north east) -- (D.south west); \draw (D.north west) -- (D.south east); % A <-> B \draw[*->] let \p1 = (A.three), \p2 = (A.center) in (\x1,\y2) to [out=25,in=150] (B.two north); \draw[*->] let \p1 = (B.one), \p2 = (B.center) in (\x1,\y2) to [out=-150,in=-25] (A.two south); % B <-> C \draw[*->] let \p1 = (B.three), \p2 = (B.center) in (\x1,\y2) to [out=25,in=150] (C.two north); \draw[*->] let \p1 = (C.one), \p2 = (C.center) in (\x1,\y2) to [out=-150,in=-25] (B.two south); % A <-> C \draw[*->] let \p1 = (A.one), \p2 = (A.center) in (\x1,\y2) to [out=50,in=100] (C.two north); \draw[*->] let \p1 = (C.three), \p2 = (C.center) in (\x1,\y2) to [out=-100,in=-50] (A.two south); \end{tikzpicture}$

We can represent double-linked lists in LSL via functions that perform operations typical to linked lists. In order to prevent unwanted type conversions, all functions return lists which can then be converted to the desired type.

Code

list
- forward
- insert_after
- insert_before
- remove
- reverse
node
- next
- previous