How to keep ordering of records in a database table

I feel this is related to the general problem of using an array vs a linked list. How about storing a foreign key referencing the next record in the same table? This is the linked list like approach.

For your example there are not too many tabs so an array based approach should work fine. But for someone having hundreds of records it may be useful to use a self-referential foreign key.

ID Name      NExT  
 1 Home      2  
 2 About     3  
 3 Products  4 
 4 Shopping  NULL

Adding and deleting rows will be akin to linked list insertion and deletion.

Update: Modified table

ID Name       NExT  
 1 Home       5  
 2 About      3  
 3 Products   4 
 4 Shopping   NULL
 5 Contact us 2

The order will be 1 > 5 > 2 > 3 > 4 as determined by the next column. You can also use a prev column which will make it similar to a doubly linked list.

Without an ORDER BY, you can't guarantee the order of the data - typically, without an ORDER BY it will be based on insertion order.

Sadly, there's no convention that works well for a user customizable sort order.
One could get away with using analytic/windowing/ranking functions like ROW_NUMBER, but it depends on data and database support (MySQL doesn't support analytic functions, Oracle 9i+/PostgreSQL 8.4+/SQL Server 2005+ do). But analytic functions don't help if you want an entry starting with "B" to appear before "A"/etc.

Your options are to either use two statements to insert a single record:

UPDATE YOUR_TABLE
   SET sort_order = sort_order + 1
 WHERE sort_order >= 2

INSERT INTO YOUR_TABLE
  (value, sort_order)
VALUES('new value', 2)

...or delete the existing records, and re-insert the list in the new order.