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

 
 
 


Surname:

Forename:

Mark:

Surname:

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.

Insertion

Get Item
item[0] = new Item
ptr = size
if size = maxsize then
   prompt user that list is full
else
   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
Else
   Return ptr

Deletion

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