Linked List in SQL

sql

linked-list

sql-queries

database-design

byAnton Shumikhin·Oct 17, 2024

An SQL linked list can be modeled with a table LinkedList having NodeID (primary key), NodeValue, and NextNodeID (self-referencing foreign key). Operations include INSERT for node addition, UPDATE for relinking, DELETE for node removal, and recursive CTEs for traversal:

CREATE TABLE LinkedList (
    NodeID INT PRIMARY KEY,
    NodeValue INT,
    NextNodeID INT NULL REFERENCES LinkedList(NodeID)
);

Insert Nodes

Now let's populate the linked list with some nodes using the INSERT command:

INSERT INTO LinkedList (NodeID, NodeValue, NextNodeID) VALUES 
(1, 10, 2),   -- 🌌 The start of our LinkedList odyssey
(2, 20, 3),   -- 🚀 Setting a course for the next node
(3, 30, NULL);-- 🏁 Null: the final frontier

SQL's set-oriented nature makes linked list manipulations slightly tricky.

Efficient list positioning

Consider using relative positions for efficient node insertion, sorting, and retrieval. A practical method involves the use of an incremental position column.

The 'position' advantage

Use a position column progression, like increments of 100, to conveniently place new nodes between existing nodes without shaking things up too much (because "Winter is NOT Coming" here!).

Indexing for speed

A table is only as good as its indexes, so add an index to the position column to speed up your sort and retrieval operations.

Meet ALTER TABLE, your new best friend

To upgrade your ordinary table into a linked-list powerhouse, call on ALTER TABLE. This trusty command will attach the position and NextNodeID columns to your table, because it's the hero your table deserves.

ALTER TABLE LinkedList ADD position INT; -- 🦸 ALTER TABLE to the rescue!
UPDATE LinkedList SET position = NodeID * 100; -- 💪 Supercharge positions with some gainz
CREATE INDEX idx_position ON LinkedList (position); -- 🦄 Create an index. Instant magic!

Navigating the linked list

Insertion and updates in SQL style

Inserting and updating nodes is as simple as speaking some SQL. Use INSERT and UPDATE commands to plug your data right into the list, just like plugging in a flash drive.

Smooth node deletions

Deleting a node requires just as much effort as saying "Expelliarmus". A single DELETE command does the trick.

Advanced retrievals

Recursive CTEs for linked list traversal

If you want to take a grand tour of your linked list, turn to recursive CTEs. They let you walk through the list like a park, one node at a time.

Strategies for large linked lists

Large linked lists pose no problems if you're armed with the right strategies. Recursive depth limits and performance enhancements are your trusty allies.