is a database essentially like a big linked list?

[Terrance]

I was reading the book, The Art of Computer Programming, the section on information structures. After reading the section on linked lists, it seems to me that a database is essentially a big linked list. Since a linked list is almost like a linear array that can expand and contract as data is put into and taken out of it, this seems to me like it is just a smaller version of a database.

Any of you who have programmed a database before may have insight into this question. But I was wondering if a database is just like a big linked list?

[Mario F.]

Not really, no. One aspect of databases is random access to any part of a table (row and field), whereas linked lists require you to traverse each node (row) when searching.
At the most elementary level, a database is perhaps best thought as a group of simple bidimensional arrays, one for each table. But concerning their design they are usually implemented as a combination of data structures like B-trees and hash tables.

[whiteflags]

Mario answered sufficiently, but I guess it doesn't hurt to echo him.

I was reading the book, The Art of Computer Programming, the section on information structures. After reading the section on linked lists, it seems to me that a database is essentially a big linked list. Since a linked list is almost like a linear array that can expand and contract as data is put into and taken out of it, this seems to me like it is just a smaller version of a database.

I would say databases aren't like linked lists. It really depends on how you look at it, and the more you know about the subject, the less appropriate the comparison seems to be.

Most data structures will be flexible to accommodate more information, (or less) so it's definitely not something unique to linked lists. Moreover, databases do not have to simply grow linearly, as in inserting or deleting table records. If we are talking about a relational database, it could also grow like a web, as new tables and new relationships are created.

The truth is that a DBMS needs to be programmed with a number of features in order for us humans to safely work with the database much like a computer would operate on its simpler structures. These are often complex features built out of multiple data structures. One that I would at least try to use if I built my own relational database is the hash table.

Additionally, we are often interested in things a computer does not necessarily need for its structure. One key difference between, say, a linked list and a database is that a database can be stored in digital files. Once you store many data structures in a file format, they really lose the properties that made them work in RAM.

HTH.

[Terrance]

Cool, thanks for the responses.