# Computer ScienceLinear 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.

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```