# A-level Computing 2009/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Programming Concepts/Lists

A list is a number of items in an ordered or unordered structure. A list can be used for numerous things like storing items or deleting and adding items. But for the programmer to perform the different tasks for the list, the program must have enough memory to keep up with changes made to the list. There are different sort of lists including linear lists and linked lists. Also, the list can be referred to as an abstract data type.

## Linear list

Linear lists can comprise of almost anything. Think of the lists that you use in every day life: Shopping lists, homework lists, lists of hottest celebrities. Below are three separate example lists from a pad of paper made to write shopping lists:
| Shopping List 1 | Shopping List 2 | Shopping List 3 |
| Cabbage Carrots Beetroot Salt Rustic Bread Mead The Fall by Camus A dozen eggs - - - - | Cabbage Carrots Beetroot Salt Rustic Bread Mead The Fall by Camus A dozen eggs Whole Chicken 1 can of chickpeas Deodorant Socks | Cabbage Carrots - - - - - - - - - - |
| Some wasted space | We can't add any more items! | Waste of space |
You can see above that different lists take up different amounts of space.
* List 1 uses up most of the space, but there is some wasted paper at the bottom
* List 2 uses up all the paper, but what would happen if you wanted to add something else?
* List 3 only uses up a little space but wastes most of the rest of the paper
To save paper what would be needed would be a sheet that would expand when more items were needed to be written down, and contract when less items needed to be written down. This might sound trivial but this is a real computer science issue, the following code declares a list of enemies killed in a shooting game
If the player wasn't very good and only killed one other player, then the list would be sitting there with 11 empty spaces, wasting all that space. On the other hand, if the player was incredibly good and they killed hundreds if not thousands of enemies, the list would only show the first 12. What is needed is a list that can grow and shrink, so that we only use the space that we need to. What is needed is a Dynamic Data Type, a data type that changes in size at run time.
Criticisms of a linear list:
* When a list is full you cannot add any more elements
* If the list is empty or partially full, you are wasting the space not used

## Linked list

A linked list is a solution to the problems inherent to linear lists. For the exam you should know:
* What linked lists are and be able to describe them:
* Their benefits and drawbacks:
Linked list over linear list/Benefits of a linked list:
* The memory used can vary at run time, meaning memory isn't wasted.
* The number of elements isn't limited at run time, it can expand.
* The different ways that computers store linked lists
* How to code the initialisation of linked list, and how to code:
** Adding items
** Deleting items
** Rearranging items
* Example: Post Office Box Analogy
* The concept of a linked list can be explained by a simple analogy to real-world post office boxes. Suppose Alice is a spy who wishes to give a codebook to Bob by putting it in a post office box and then giving him the key. However, the book is too thick to fit in a single post office box, so instead she divides the book into two halves and purchases two post office boxes. In the first box, she puts the first half of the book and a key to the second box, and in the second box she puts the second half of the book. She then gives Bob a key to the first box.
* Bob (bottom) has the key to box 201, which contains the first half of the book and a key to box 102, which contains the rest of the book.
* Now imagine if Alice's code book was even bigger. It won't make any difference to her system, she just adds another key
* Bob (bottom) has the key to box 201, which contains the first third of the book and a key to box 102, which contains the second third of the book and another key to box 103.
* Now imagine that Alice is the world's chief code breaker with an enormous code book, it doesn't matter how big the book is Alice can still apply her technique, ripping the book into four parts. But what about someone else already using box 104? Well because Alice includes a key to the next box, it doesn't have to use consecutive boxes, it could skip one, or twenty if need be.
* Bob (bottom) has the key to box 201, which contains the first quarter of the book and a key to box 102, which contains the second quarter of the book and another key to box 103, which contains the third quarter. Unfortunately 104 is used, so Alice puts a key to the next free space, which is box 105. In box 105 is the final quarter of the book.
* No matter how large the book is, this scheme can be extended to any number of boxes by always putting the key to next box in the previous box.
* In this analogy, the boxes correspond to elements, the keys correspond to pointers, and the book itself is the data. The key given to Bob is the head pointer, while those stored in the boxes are next pointers. This is how a linked list works.
* Exercise: Linked Lists vs Linear Lists
* What is a static data structure?
* Answer:
* A data structure that has a fixed memory size that cannot change at run time
* What is a dynamic data structure?
* Answer:
* A data structure that changes in size at run time
* Describe a linear list:
* Answer:
* A static abstract data type. The amount of data does not change at run time
* Give two criticisms of linear lists
* Answer:
* When a list is full you cannot add any more elements
* If the list is empty or partially full, you are wasting the space not used
* Give a description of a linked list:
* Answer:
* Dynamic Abstract Data Type. Uses pointers to vary memory used at run time.
* What is stored in each element of a linked list?
* Answer:
* Data, and a pointer to the next item if necessary
* What is the head of a linked list:
* Answer:
* The data contained in the element that the first pointer points to
* Give two benefits of a linked list over a linear list:
* Answer:
* the memory used can vary at run time, meaning memory isn't wasted.
* the number of elements isn't limited at run time, it can expand

### Storing Linked Lists in a Computer

We hopefully understand the principles behind the Linked List abstract data type, we now need to know how this abstract data type is stored in a computer. When storing a linked list on a computer you must use:
* head pointer
* node
** nextpointer
** data
There are two ways to represent a Linked List using node and pointer notation:
Or using an address table (both lists are the same):
Head Pointer = 101 :
| Address | node | node |
| Address | NextPointer | Data |
| 101 | 102 | 12 |
| 102 | 103 | 99 |
| 103 | null | 37 |
Example: Linked List Computer Representation
Head Pointer = 0
Addressnode
NextPointerData
01Wiston
12Wormingford
23Nayland
3nullBures
4nullHalstead
The example above contains 5 nodes, but only 4 of them are in the linked list. Let's follow the points and see what data we have:
Wiston[*]-> Wormingford[*]-> Nayland[*]-> Bures[*]-> null
If you look closely you'll notice that address 4 is never linked, once we get to node 3, Bures, the pointer points to null. This means the end of the list.
Let's take a look at a more complex example
Head Pointer = 802
Addressnode
NextPointerData
800804Wiston
801802Wormingford
802803Nayland
803800Bures
804nullHalstead
Following the pointers for this we get:
Nayland[*]-> Bures[*]-> Wiston[*]-> Halstead[*]->null
As you can see it doesn't really matter what order the items are in terms of memory address, it's all about the pointers to tell us the order of the data and what data is in the linked list. Also the use of the head pointer means that the data might not start where you expect! :
Exercise: Linked Lists - Initialisation
What is the pointer value of the end of a linked list?
Answer:
null
What does the following linked list store:
Head Pointer = 700
Addressnode
NextPointerData
697804Red
698nullYellow
699698Green
700701Blue
701699Purple
Answer:
Blue, Purple, Green, Yellow
Insert the correct pointers into this linked list (remember the Head Pointer!), to create the following list:
Red, Yellow, Purple, Green, Blue
Head Pointer =
Addressnode
NextPointerData
697Red
698Yellow
699Green
700Blue
701Purple
Answer:
Head Pointer = 697
Addressnode
NextPointerData
697698Red
698701Yellow
699700Green
700nullBlue
701699Purple
Give a node pointer diagram for the following:
Head Pointer = 699
Addressnode
NextPointerData
697701Red
698nullYellow
699697Green
700699Blue
701698Purple
Answer:
Green[*]->Red[*]->Purple[*]->Yellow[*]->null :

### Inserting Items into Linked Lists

To add another item to the end of a linked list is really quite simple, all you do is place the new item in some spare memory (taken from the heap) and adjust the last pointer in the current list from pointing to null, to pointing to the new item. Let us take a look at an example of inserting 'Chappel' into a list of settlements in East Anglia:
| Start | Add Chappel | End |
| Head Pointer = 000 Addressnode NextPointerData 000001Bures 001002Wormingford 002003Nayland 003nullWiston 004003 | Find last node: 003 Find next free node: 004 Change data on next free node (004) to Chappel Change pointer on next free node (004) to null Change pointer of last node (003) to point to the new node (004) | Head Pointer = 000 Addressnode NextPointerData 000001Bures 001002Wormingford 002003Nayland 003004Wiston 004nullChappel |
This seems simple enough, but what if we want to insert something in the middle of a list. Let's look what would happen for a linear list so we can see how amazing linked lists truly are. Let's insert 'Jadd' into a list of names:
| Original State | Process | Move Down | Move Down | Move Down | Insert |
| AddressData 001Aubrey 002Barry 003Ethelbert 004Liam 005Michael 006Oliver 007<blank> | Find suitable element position shift all elements below that down one insert element into spare space | AddressData 001Aubrey 002Barry 003Ethelbert 004Liam 005Michael 006Oliver 007Oliver | AddressData 001Aubrey 002Barry 003Ethelbert 004Liam 005Michael 006Michael 007Oliver | AddressData 001Aubrey 002Barry 003Ethelbert 004Liam 005Liam 006Michael 007Oliver | AddressData 001Aubrey 002Barry 003Ethelbert 004Jadd 005Liam 006Michael 007Oliver |
It took 3 moves before we could insert our new value. Imagine what would happen if we were insert a value in the middle of a linear list of 1000 elements, it would take 500 move downs before we could insert a new item. What a terrible use of processing time!
With linked lists things are much easier. Because we use pointers all we need to do is to change the pointers around to quickly insert a new element, take a look at the same example of adding 'Jadd' to a linked list of names.
| Original State | Process | Insert |
| Head Pointer = 001 Addressnode NextPointerData 001002Aubrey 002003Barry 003004Ethelbert 004005Liam 005006Michael 006nullOliver 007002<blank> | Find node before Jadd: 003 Find address that will be after Jadd: 003.NextPointer = 004 Find next free space: 007 Insert Jadd into next free space (007) Change Jadd.NextPointer to point to node following it: 004 Change node before Jadd to point to Jadd: 003.NextPointer = 007 | Head Pointer = 001 Addressnode NextPointerData 001002Aubrey 002003Barry 003007Ethelbert 004005Liam 005006Michael 006nullOliver 007004Jadd |
Notice that we didn't 'move' anything, we just changed the pointers. This might not seem to be much faster than the linear list, but imagine you were dealing with a list of 1000 items, you'd only have to change 3 pointers instead of moving 500 nodes. It's a much faster method.
You can also see this visually in this example of inserting 37 into a list of 12 and 99:
Exercise: Linked lists - Inserting
Show the resulting linked list for inserting J into the following alphabetised linked list:
Head Pointer = 001
Addressnode
NextPointerData
001002F
002003G
003004K
004005L
005006N
006nullP
007nullJ
Answer:
Head Pointer = 001
Addressnode
NextPointerData
001002F
002007G
003004K
004005L
005006N
006nullP
007003J
Show the resulting linked list for inserting 78 into the following ordered linked list:
Head Pointer = 001
Addressnode
NextPointerData
00100212
00200613
003null78
00400577
005null79
00600414
Answer:
Head Pointer = 001
Addressnode
NextPointerData
00100212
00200613
00300578
00400377
005null79
00600414
Why is inserting data into a linked list easier than inserting data into a linear list?
Answer:
Whatever the size of a list, a linked list only requires a few pointer changes to insert a new item, whilst a linear list requires all the following objects to be shifted along.
Where does a linked list get free space from
Answer:
the computer heap
Outline the steps involved in inserting data into a linked list
Answer:
Find node before that to be inserted: pre
Find address that will be after Jadd: pre.nextPointer
Find next free space: nextFree
Insert into next free space: inserted
Change inserted.nextPointer = pre.nextPointer
Change pre node to point to inserted data: pre.nextPointer = inserted.Address :

### Deleting Items from Linked Lists

You should now be familiar with how linked lists work and how to insert elements into linked lists, but what
To again prove the point that linked lists are amazing, take a look at this example where we are deleting Ethelbert from our ordered list of people. We can't just take them out as that would leave a gaping hole in our list, we need to shift everything up
| Original State | Process | Move Up | Move Up | Move Up | Move Up and set to blank |
| AddressData 001Aubrey 002Barry 003Ethelbert 004Jadd 005Liam 006Michael 007Oliver | Find element to delete shift all elements below up one place set last place to blank | AddressData 001Aubrey 002Barry 003Jadd 004Jadd 005Liam 006Michael 007Oliver | AddressData 001Aubrey 002Barry 003Jadd 004Liam 005Liam 006Michael 007Oliver | AddressData 001Aubrey 002Barry 003Jadd 004Liam 005Michael 006Michael 007Oliver | AddressData 001Aubrey 002Barry 003Jadd 004Liam 005Michael 006Oliver 007<blank> |
It took 4 moves before we could consider the item deleted and list re-ordered. Imagine what would happen if we were delete a value in the middle of a linear list of 1000 elements, it would take 500 moves up before we could consider the item deleted and list re-ordered.(Again) What a terrible use of processing time!
With linked lists things are much easier. Because we use pointers all we need to do is to change the pointers around to 'skip over' the deleted node.
Take a look at the same example of adding 'Jadd' to a linked list of names.
| Original State | Process | Insert |
| Head Pointer = 001 Addressnode NextPointerData 001002Aubrey 002003Barry 003004Ethelbert 004005Jadd 005006Liam 006nullMichael 007002Oliver | Find node to be deleted: del = 003 Find node that links to it: pre = 002 Find node that del links to: post = del.nextPointer = 004 Set pre.nextPointer = del.nextPointer = 004 Add the deleted data to the heap | Head Pointer = 001 Addressnode NextPointerData 001002Aubrey 002004Barry 003004Ethelbert 004005Jadd 005006Liam 006nullMichael 007002Oliver |
Notice that we didn't need to 'move' anything, we just changed a single pointer. but imagine you were dealing with a list of 1000 items, you'd only have to change 1 pointer instead of moving 500 nodes. It's a much, much faster method.
Exercise: Linked Lists - Deleting
Show the pointers on the following data after removing P
Head Pointer = 001
Addressnode
NextPointerData
001002F
002003G
003004H
004005L
005006N
006nullP
007nullX
Answer:
Head Pointer = 001
Addressnode
NextPointerData
001002F
002003G
003004H
004005L
005nullN
006nullP
007nullX
Show the following table after removing L and G, in that order:
Head Pointer = 001
Addressnode
NextPointerData
001002F
002007G
003004K
004005L
005006N
006nullP
007003J
Answer:
Head Pointer = 001
Addressnode
NextPointerData
001007F
002007G
003005K
004005L
005006N
006nullP
007003J
Show the following list after inserting 23 then removing 14
Head Pointer = 001
Addressnode
NextPointerData
00100212
00200613
003null79
00400577
005null79
00600414
Answer:
Head Pointer = 001
Addressnode
NextPointerData
00100212
00200313
00300423
00400577
005null79
00600314
When you delete an item from a linked list where does it go?
Answer:
Into the heap to be reused
Describe the steps to delete an item from a list
Answer:
Find node to be deleted: del
Find node that links to it: pre
Find node that del links to: post = del.nextPointer
Set pre.nextPointer = del.nextPointer
Add the deleted data to the heap :

### Uses of Linked lists

We know that linked lists allow for dynamic data structures, structures that change size at run time. This means that if we want to make a data structure that can shrink and grow in size at run time, it is a good idea to use a linked list. Examples include:
* Queues
* Stacks
* File systems
Example: Catching Criminals with linked lists
You might read in the news about the police confiscating criminals computers to search for data. You might also think that the criminals must be pretty stupid to not delete all their incriminating data before they are caught. Well it's not as simple as that. The way that a computer file system works is very similar to the linked lists you have read about above. When you add a folder or a file, it doesn't have to sit next to all the other data in memory, using pointers the data can be scattered throughout memory. And most importantly, when you 'delete' something, you only delete the pointer to it. It is still there in memory, just with nothing pointing to it. Take a look at the following, a hard disk of a criminal:
C:/
Program Files
Games
Documents
Family Photos
Home Movies
Stolen Documents
Stories about Cats
On hearing the police downstairs knocking on the door, the criminal runs to his computer and deletes the 'Stolen Documents' folder.
C:/
Program Files
Games
Documents
Family Photos
Home Movies
Stories about Cats
But all that is happening in the operating system is the equivalent of the following (the data structure is a lot more complicated in reality):
Head Pointer = 001
Addressnode
NextPointerFolder
001002C:
002003Program Files
003004Games
004005Documents
005006Family Photos
006008Home Movies
007008Stolen Documents
008nullStories about Cats
The data is still there, all that has been done by deleting the data is to change the pointers. With special software you can restore it, catching the crook.
The best way to 'delete' data is to shred your hard disk, and many firms and governmental organisations will have metal shredders for this very purpose. :

### Maintaining the free space

We have mentioned that linked lists are dynamic data types, allowing memory used to change at run time. To achieve this we use the Heap:
But what happens when we delete something, you have seen the pointers changing, but you haven't seen the space being reused
How do you maintain the free space?
Remember how pointers work and how you know that you have reached the end of the list.
Easy to sort (just swap pointers)
Easy to insert/delete items (just change the pointers)