Computer Science
Linear Lists

A linear list is an abstract data type. It is a dynamic structure - the number of items in the list can increase and decrease at run-time. Items in a list are stored in order in adjacent locations in memory.

The following example illustrates how a linear list can be programmed using an array. This is written in Javascript which can be viewed along with the source code of this page. The algorithms from below have been used with a few tweaks. Validation is minimal although fussy in some places.

Linear List Simulation







Algorithms For A Linear List

Each item in the example list has 3 properties, the first one being used for sorting. You need to use a user-defined type to represent each item in the list. In C#, we would do this as follows,

public struct TStudent {
   public string surname;
   public string forename;
   public int mark;

A one-dimensional array is used to store the records.

TStudent[] students = new TStudent[20];

The remaining algorithms are in pseudocode.


Get Item
item[0] = new Item
ptr = size
if size = maxsize then
   prompt user that list is full
   While item[ptr].surname>item[0].surname
      item[ptr+1] = item[ptr]
      ptr = ptr - 1
   End While
   size = size + 1
   item[ptr+1] = item[0]
End If

Finding The Location Of An Item

item[0].surname = surname to be found
ptr = size
while item[ptr].surname> surname to be found
   ptr = ptr -1
End While
If ptr = 0 Then
   Return False
   Return ptr


Call find item function to see if item is found
If item not found Then
   Write Error Message
   ptr = location of item
   While ptr < size
      item[ptr] = item[ptr +1]
      ptr = ptr + 1
   End While
   size = size -1
End If