Linked List in SQL

Linked List in SQL

Store an integer column in your table called 'position'. Record a 0 for the first item in your list, a 1 for the second item, etc. Index that column in your database, and when you want to pull your values out, sort by that column.

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

To insert a value at index 3, modify the positions of rows 3 and above, and then insert:

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 

SQL - Linked List Table - Is there a better way to write this query?

You can use a recursive CTE:

with cte as (
      select nodeid, nodeid as oldestnodeid
      from nodes
      where previousnodeid is null
      union all
      select n.nodeid, cte.oldestnodeid
      from cte join
           nodes n
           on cte.nodeid = n.previousnodeid
     )
select *
from cte
order by nodeid;

Here is a db<>fiddle.

Although this is also "iterative", it is much better than the cursor-based approach. Basically, all three "oldest" nodes are handled in parallel. So the query recurses 5 times -- for the As -- rather iteratively looping through 9 rows.

How do I sort a linked list in sql?

In Oracle:

SELECT Id, ParentId, SomeData
FROM (
  SELECT ll.*, level AS lvl
  FROM LinkedList ll
  START WITH
    ParentID IS NULL
  CONNECT BY
    ParentId = PRIOR Id
)
ORDER BY
  lvl

P. S. It's a bad practice to use NULL as ParentID, as it is not searchable by indices. Insert a surrogate root with id of 0 or -1 instead, and use START WITH ParentID = 0.

SQL : Linked lists in SQL database?

You could think of the following central database schema:

stores
    id
    code
    name
    address
    ...

items
    id
    code
    name
    description
    barcode
    retail_price
    ...

stocks
    store_id
    item_id
    stock_count

inventories
    id
    inventory_date
    store_id

inventory_items
    inventory_id
    item_id 
    original_stock_count
    corrected_stock_count

So the stocks table would have references to the store where the stock is held and the item reference. Note that the details of the item are in the items table, which is independent from a store.

But in the stocks table you would have an item occurring multiple times, each time for a different store.

The inventories table has a record per inventory session, which is unique per store. This does not prevent from inventories to be taken for all stores at the same time, which would result in as many records, but leaves the flexibility to do one for one store only as well.

Then the inventory_items table adds the results of the inventory: per item the counts are logged.

Linked lists: query first and last element of chained lists stored in SQL table

WITH RECURSIVE cte AS (
   SELECT id AS first, id AS last, 1 as len
   FROM   lines
   WHERE  previous_id IS NULL

   UNION ALL
   SELECT c.first, l.id, len + 1
   FROM   cte   c
   JOIN   lines l ON l.previous_id = c.last
   )
SELECT DISTINCT ON (first)
       last, len  -- , first -- also?
FROM   cte
ORDER  BY first, len DESC;

db<>fiddle here

Produces your result exactly.

If yo also want the first element like your title states, that's readily available.

Iterate through linked list in one SQL query?

Does postgresql support recursive queries that use WITH clauses? If so, something like this might work. (If you want a tested answer, provide some CREATE TABLE and INSERT statements in your question, along with the results you need for the sample data in the INSERTs.)

with Links(id,link,data) as (
  select
    id, redirectid, data
  from T
  where redirectid is null
  union all
  select
    id, redirectid, null
  from T
  where redirectid is not null
  union all
  select
    Links.id,
    T.redirectid,
    case when T.redirectid is null then T.data else null end
  from T
  join Links
  on Links.link = T.id
)
  select id, data
  from Links
  where data is not null;

Additional remarks:

:( You can implement the recursion yourself based on the WITH expression. I don't know postgresql syntax for sequential programming, so this is a bit pseudo:

Insert the result of this query into a new table called Links:

select
    id, redirectid as link, data, 0 as depth
  from T
  where redirectid is null
  union all
  select
    id, redirectid, null, 0
  from T
  where redirectid is not null

Also declare an integer ::depth and initialize it to zero. Then repeat the following until it no longer adds rows to Links. Links will then contain your result.

  increment ::depth;
  insert into Links
  select
    Links.id,
    T.redirectid,
    case when T.redirectid is null then T.data else null end,
    depth + 1
  from T join Links
  on Links.link = T.id
  where depth = ::depth-1;
end;

I think this will be better than any cursor solution. In fact, I can't really think of how cursors would be useful for this problem at all.

Note that this will not terminate if there are any cycles (redirects that are ultimately circular).

---

Related Topics