5.1. Linked Lists

A powerful feature of using a graph database, is that you can create your own in-graph data structures — for example a linked list.

This data structure uses a single node as the list reference. The reference has an outgoing relationship to the head of the list, and an incoming relationship from the last element of the list. If the list is empty, the reference will point to itself.

To make it clear what happens, we will show how the graph looks after each query.

To initialize an empty linked list, we simply create a node, and make it link to itself. Unlike the actual list elements, it doesn’t have a value property.

CREATE (root { name: 'ROOT' })-[:LINK]->(root)
RETURN root
cypherdoc--cf38d218.svg

Adding values is done by finding the relationship where the new value should be placed in, and replacing it with a new node, and two relationships to it. We also have to handle the fact that the before and after nodes could be the same as the root node. The case where before, after and the root node are all the same, makes it necessary to use CREATE UNIQUE to not create two new value nodes by mistake.

MATCH (root)-[:LINK*0..]->(before),(after)-[:LINK*0..]->(root),(before)-[old:LINK]->(after)
WHERE root.name = 'ROOT' AND (before.value < 25 OR before = root) AND (25 < after.value OR after =
  root)
CREATE UNIQUE (before)-[:LINK]->({ value:25 })-[:LINK]->(after)
DELETE old
cypherdoc--89a53f24.svg

Let’s add one more value:

MATCH (root)-[:LINK*0..]->(before),(after)-[:LINK*0..]->(root),(before)-[old:LINK]->(after)
WHERE root.name = 'ROOT' AND (before.value < 10 OR before = root) AND (10 < after.value OR after =
  root)
CREATE UNIQUE (before)-[:LINK]->({ value:10 })-[:LINK]->(after)
DELETE old
cypherdoc--d546bacf.svg

Deleting a value, conversely, is done by finding the node with the value, and the two relationships going in and out from it, and replacing the relationships with a new one.

MATCH (root)-[:LINK*0..]->(before),(before)-[delBefore:LINK]->(del)-[delAfter:LINK]->(after),
  (after)-[:LINK*0..]->(root)
WHERE root.name = 'ROOT' AND del.value = 10
CREATE UNIQUE (before)-[:LINK]->(after)
DELETE del, delBefore, delAfter
cypherdoc--89a53f24.svg

Deleting the last value node is what requires us to use CREATE UNIQUE when replacing the relationships. Otherwise, we would end up with two relationships from the root node to itself, as both before and after nodes are equal to the root node, meaning the pattern would match twice.

MATCH (root)-[:LINK*0..]->(before),(before)-[delBefore:LINK]->(del)-[delAfter:LINK]->(after),
  (after)-[:LINK*0..]->(root)
WHERE root.name = 'ROOT' AND del.value = 25
CREATE UNIQUE (before)-[:LINK]->(after)
DELETE del, delBefore, delAfter
cypherdoc--cf38d218.svg