Programming Concepts: Lists

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 3 - ⇑ Programming Concepts ⇑

← Queues Lists Graphs →


A list is a number of items in an ordered or unordered structure. A list can be used for a numerous 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[edit]

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 3
  1. Cabbage
  2. Carrots
  3. Beetroot
  4. Salt
  5. Rustic Bread
  6. Mead
  7. The Fall by Camus
  8. A dozen eggs
  9. -
  10. -
  11. -
  12. -
  1. Cabbage
  2. Carrots
  3. Beetroot
  4. Salt
  5. Rustic Bread
  6. Mead
  7. The Fall by Camus
  8. A dozen eggs
  9. Whole Chicken
  10. 1 can of chickpeas
  11. Deodorant
  12. Socks
  1. Cabbage
  2. Carrots
  3. -
  4. -
  5. -
  6. -
  7. -
  8. -
  9. -
  10. -
  11. -
  12. -
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 sounds 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[edit]

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:

  1. The memory used can vary at run time, meaning memory isn't wasted.
  2. 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[edit]

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:

Singly-linked-list.svg

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?

Answer :

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

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 =
Address node
NextPointer Data
697 Red
698 Yellow
699 Green
700 Blue
701 Purple

Answer :

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

Answer :

Green[*]->Red[*]->Purple[*]->Yellow[*]->null

Inserting Items into Linked Lists[edit]

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
  1. Find last node: 003
  2. Find next free node: 004
  3. Change data on next free node (004) to Chappel
  4. Change pointer on next free node (004) to null
  5. 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>
  1. Find suitable element position
  2. shift all elements below that down one
  3. 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>
  1. Find node before Jadd: 003
  2. Find address that will be after Jadd: 003.NextPointer = 004
  3. Find next free space: 007
  4. Insert Jadd into next free space (007)
  5. Change Jadd.NextPointer to point to node following it: 004
  6. 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:

CPT-LinkedLists-addingnode.svg
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

Answer :

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

Answer :

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?

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 :

  1. Find node before that to be inserted: pre
  2. Find address that will be after Jadd: pre.nextPointer
  3. Find next free space: nextFree
  4. Insert into next free space: inserted
  5. Change inserted.nextPointer = pre.nextPointer
  6. Change pre node to point to inserted data: pre.nextPointer = inserted.Address

Deleting Items from Linked Lists[edit]

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 Oliver
  1. Find element to delete
  2. shift all elements below up one place
  3. 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.

CPT-LinkedLists-deletingnode.svg

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 Oliver
  1. Find node to be deleted: del = 003
  2. Find node that links to it: pre = 002
  3. Find node that del links to: post = del.nextPointer = 004
  4. Set pre.nextPointer = del.nextPointer = 004
  5. 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

Answer :

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

Answer :

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

Answer :

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?

Answer :

Into the heap to be reused
Describe the steps to delete an item from a list

Answer :

  1. Find node to be deleted: del
  2. Find node that links to it: pre
  3. Find node that del links to: post = del.nextPointer
  4. Set pre.nextPointer = del.nextPointer
  5. Add the deleted data to the heap

Uses of Linked lists[edit]

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[edit]

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)