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

Queues Graphs 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 List A static abstract data type. The amount of data does not change at run time. 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 3Cabbage 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 SocksCabbage 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 dim killedList as string(11) 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 Linked List Dynamic Abstract Data Type. Uses pointers to vary memory used at run time. 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. center|250px|frame|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 center|250px|frame|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. center|250px|frame|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? A data structure that has a fixed memory size that cannot change at run time What is a dynamic data structure? A data structure that changes in size at run time Describe a linear list: A static abstract data type. The amount of data does not change at run time Give two criticisms of linear lists 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: Dynamic Abstract Data Type. Uses pointers to vary memory used at run time. What is stored in each element of a linked list? Data, and a pointer to the next item if necessary What is the head of a linked list: The data contained in the element that the first pointer points to Give two benefits of a linked list over a linear 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 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: center Or using an address table (both lists are the same): Head Pointer = 101 Address node NextPointer Data 101 102 12 102 103 99 103 null 37 Example: Linked List Computer Representation Head Pointer = 0 Address node NextPointer Data 0 1 Wiston 1 2 Wormingford 2 3 Nayland 3 null Bures 4 null Halstead 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 Address node NextPointer Data 800 804 Wiston 801 802 Wormingford 802 803 Nayland 803 800 Bures 804 null Halstead 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? null What does the following linked list store: Head Pointer = 700 Address node NextPointer Data 697 804 Red 698 null Yellow 699 698 Green 700 701 Blue 701 699 Purple 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 = Address node NextPointer Data 697 Red 698 Yellow 699 Green 700 Blue 701 Purple Head Pointer = 697 Address node NextPointer Data 697 698 Red 698 701 Yellow 699 700 Green 700 null Blue 701 699 Purple Give a node pointer diagram for the following: Head Pointer = 699 Address node NextPointer Data 697 701 Red 698 null Yellow 699 697 Green 700 699 Blue 701 698 Purple 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 Address node NextPointer Data 000 001 Bures 001 002 Wormingford 002 003 Nayland 003 null Wiston 004 003 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 Address node NextPointer Data 000 001 Bures 001 002 Wormingford 002 003 Nayland 003 004 Wiston 004 null Chappel 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 Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Liam 005 Michael 006 Oliver 007 <blank>Find suitable element position shift all elements below that down one insert element into spare space Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Liam 005 Michael 006 Oliver 007 Oliver Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Liam 005 Michael 006 Michael 007 Oliver Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Liam 005 Liam 006 Michael 007 Oliver Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Jadd 005 Liam 006 Michael 007 Oliver 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 Address node NextPointer Data 001 002 Aubrey 002 003 Barry 003 004 Ethelbert 004 005 Liam 005 006 Michael 006 null Oliver 007 002 <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 Address node NextPointer Data 001 002 Aubrey 002 003 Barry 003 007 Ethelbert 004 005 Liam 005 006 Michael 006 null Oliver 007 004 Jadd 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: center Exercise: Linked lists - Inserting Show the resulting linked list for inserting J into the following alphabetised linked list: Head Pointer = 001 Address node NextPointer Data 001 002 F 002 003 G 003 004 K 004 005 L 005 006 N 006 null P 007 null J Head Pointer = 001 Address node NextPointer Data 001 002 F 002 007 G 003 004 K 004 005 L 005 006 N 006 null P 007 003 J Show the resulting linked list for inserting 78 into the following ordered linked list: Head Pointer = 001 Address node NextPointer Data 001 002 12 002 006 13 003 null 78 004 005 77 005 null 79 006 004 14 Head Pointer = 001 Address node NextPointer Data 001 002 12 002 006 13 003 005 78 004 003 77 005 null 79 006 004 14 Why is inserting data into a linked list easier than inserting data into a linear list? 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 the computer heap Outline the steps involved in inserting data into a linked list 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 Address Data 001 Aubrey 002 Barry 003 Ethelbert 004 Jadd 005 Liam 006 Michael 007 OliverFind element to delete shift all elements below up one place set last place to blank Address Data 001 Aubrey 002 Barry 003 Jadd 004 Jadd 005 Liam 006 Michael 007 Oliver Address Data 001 Aubrey 002 Barry 003 Jadd 004 Liam 005 Liam 006 Michael 007 Oliver Address Data 001 Aubrey 002 Barry 003 Jadd 004 Liam 005 Michael 006 Michael 007 Oliver Address Data 001 Aubrey 002 Barry 003 Jadd 004 Liam 005 Michael 006 Oliver 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. center Take a look at the same example of adding 'Jadd' to a linked list of names. Original State Process Insert Head Pointer = 001 Address node NextPointer Data 001 002 Aubrey 002 003 Barry 003 004 Ethelbert 004 005 Jadd 005 006 Liam 006 null Michael 007 002 OliverFind 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 Address node NextPointer Data 001 002 Aubrey 002 004 Barry 003 004 Ethelbert 004 005 Jadd 005 006 Liam 006 null Michael 007 002 Oliver 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 Address node NextPointer Data 001 002 F 002 003 G 003 004 H 004 005 L 005 006 N 006 null P 007 null X Head Pointer = 001 Address node NextPointer Data 001 002 F 002 003 G 003 004 H 004 005 L 005 null N 006 null P 007 null X Show the following table after removing L and G, in that order: Head Pointer = 001 Address node NextPointer Data 001 002 F 002 007 G 003 004 K 004 005 L 005 006 N 006 null P 007 003 J Head Pointer = 001 Address node NextPointer Data 001 007 F 002 007 G 003 005 K 004 005 L 005 006 N 006 null P 007 003 J Show the following list after inserting 23 then removing 14 Head Pointer = 001 Address node NextPointer Data 001 002 12 002 006 13 003 null 79 004 005 77 005 null 79 006 004 14 Head Pointer = 001 Address node NextPointer Data 001 002 12 002 003 13 003 004 23 004 005 77 005 null 79 006 003 14 When you delete an item from a linked list where does it go? Into the heap to be reused Describe the steps to delete an item from a list 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 Address node NextPointer Folder 001 002 C: 002 003 Program Files 003 004 Games 004 005 Documents 005 006 Family Photos 006 008 Home Movies 007 008 Stolen Documents 008 null Stories 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: Heap a large pool of unused memory used to allocate space for new data items. 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)