We back away from DB theory to learn some of the important data structure that is used in DBMS.

The simplest data structure is Flat file, which is a file with no repeating field(all fields are disjoint) –> 2 Dimesion table ( field = columns, record = row)

1.Linked Lists.

Linked lists are the list that of which every element is linked together linearly(dynamically). The last element’s next neighbor is usually denoted null, or none.

NOTE : There are two kinds of linked list

– Singly Linked list or one-way iteration list(picture above)

– Doubly Linked list or two-way iteration list.

For example, Suppose we have the following table of records.

What if we want to sort the table by First Name. We can do sort operation onto the list to get the sorted list like this :