Programming Concepts: Lists
A list is a number of items in an ordered or unordered structure. A list can be used for a number of 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 done to the list. There are different sort of lists which are linear list and linked list. Also, the list can be referred to as an abstract data type.
Linear list
editLinear 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 |
---|---|---|
|
|
|
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
editA 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
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:
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:
|
Storing Linked Lists in a Computer
editWe 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 | |
---|---|---|
NextPointer | Data | |
101 | 102 | 12 |
102 | 103 | 99 |
103 | null | 37 |
Example: Linked List Computer Representation
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
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:
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
Answer:
Give a node pointer diagram for the following:
Answer: Green[*]->Red[*]->Purple[*]->Yellow[*]->null |
Inserting Items into Linked Lists
editTo 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 | ||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
This seems simple enough, but what if we want to insert something in the middle of a list. Let's look at 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
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:
Answer:
Show the resulting linked list for inserting 78 into the following ordered linked list:
Answer:
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:
|
Deleting Items from Linked Lists
editYou 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
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
Answer:
Show the following table after removing L and G, in that order:
Answer:
Show the following list after inserting 23 then removing 14
Answer:
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:
|
Uses of Linked lists
editWe 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:
On hearing the police downstairs knocking on the door, the criminal runs to his computer and deletes the 'Stolen Documents' folder.
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):
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
editWe 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)