Section 10.3
10 Data Structures
10.3 Linked Lists
Linked lists are dynamic data structures that hold a sequence of items which are
not necessarily in contigous data locations.
Each item in the list is called a node and is made up of information field
(which often has sub fields) and a next address field called a pointer.
The pointer of the last item is given a value of zero to indicate that there are
no more items.
This data structure also includes a variable that points to the first item in
the list.
10.3.1 Managing Freespace
In order to keep track of the free space two linked lists are kept.
When a new item is added the data list a node is removed from the free space
list.
When an item is deleted from the data list it is linked into the free space
list.
Initialising The Table
At this stage the table just consists of a linked list free space.
10.3.2 Inserting An item Into A Linked List
- Store the new name in the node pointed to by the next free.
- Change the next free to point to the new next free.
- Follow the links to find out where the new item should be linked
in.
- Change the new items pointer to point to the next item.
- Change the previous items pointer to point to the new item.
Pseudocode
node(nextfree).nam = newname
tempfree = nextfree
nextfree = node(nextfree).pt
follow = start
DO UNTIL node(node(follow).pt).nam > newname
follow = node(follow)).pt
LOOP
node(tempfree).pt = node(follow).pt
node(follow).pt = node(tempfree).pt
Before we can work out the full pseudocode we need to identify the special
cases.
They are:
- There is no free space.
- The data list is empty.
- The new item is to be the first item in the data list.
- The new item is to be the last item in the data list.
10.3.3 Deleting An Item From A Linked List
In order to delete an item from a linked list we:
- Follow the pointers to the item.
- Change the next free pointer to the deleted item.
- Change the previous items pointer to the following item.
- Change the deleted items pointer to point to the old next free
item.
