Section 10.2
10 Data Structures
10.2 Linear Lists
A linear list is a dynamic data structure in which the data items are held one
after another in sequence.
In order to implement a linear list we need an array large enough to hold the
maximum sequence that can occur.
We also need:
- a variable to hold the size.
- a variable to hold to maximum size.
10.2.1 Inserting An Item
New items are inserted at the correct place. The variable holding the size must
be incremented.
10.2.2 Retrieving An Item From A List
To retrieve an item we place the sought item in position 0 and search linearly
through the list.
Example
train(0).dest = sought_value
pointer = 1
DO UNTIL train(0).dest = train(pointer).dest OR pointer = max
pointer = pointer + 1
LOOP
IF pointer > max THEN
found = 0
ELSE
found = 1
END IF
10.2.3 Deleting An Item From A List
To delete an item from a list we first find the item using the code from the
last section.
Example
Input item to delete
CALL the retrieve sub program to see if it is in the list and then get its
location
IF found = 0 THEN
display an error message
ELSE
FOR current = pointer to size
train(current) = train(current + 1)
NEXT current
size = size - 1
END IF
