JSR Notes:

List ADT E.: List usage with Collection classes ArrayList & LinkedList

Context of D.4.11 in terms of algorithms responsibility (A repeat of this)

D.4.6 - There, we weren't necessarily thinking about a list, we just wanted to see generally how linking is achieved through self-referential pointers. (Though what we looked at there ended up being a list, it also could have been a tree.)

D.4.10 - There, it was the employment of self-referential classes for implementations of general lists - and though not necessarily thinking stacks or queues, certainly these are useful ways of using lists.

D.4.11 - Here it's the use of self-referential classes in lists via the specific ADTs, ArrayList and LinkedList. And though able to treat lists as stacks and queues, also including searching, deleting, adding in order through whole lists.

And D.4.12, next, is for tracing through such algorithms.

And of all three, D.4.5, D.4.10, and D.4.11, we have to think that this is the key one, since it says in the Teaching Note "Students should have a broad understanding of the operation of these lists and their interface (methods) but not of the internal structure", which is what D.4.5 an D.4.10 were really about. Past papers, too, hint strongly at an emphasis on this D.4.11 for algorithmic Paper 2 list questions.

Intro - Java Library: Collections

Libraries Review

Remember that "libraries" are groupings of classes of code, which have been made by others, and are now available for you to use, or in the case of the library analogy, to "borrow". So there is no need to code your own selection sort, or binary search tree etc. It's nice to make your own for learning purposes, and so that you intimately know how they work, but once you get out in the "real world", rather than in an educational setting, you will want to be the most efficient you can be, and use pre-made classes and algorithms like the ones mentioned here.

Java Collections Framework (not required, but for context)

The Java "Collections" classes come from the Java Collections Framework (JCF) which includes ArrayList and LinkedList. You don't need to understand the hierarchy of the JCF, but for what it's worth, here it is:

Wikepedia CC BY-SA 4.0

The context of classes within a framework (also not required, but for context)

The only things we actually use, as programmers, in a given framework are the classes at the bottom of the hierarchy; and of the six of them in Java the Collections framework, there are two library collections that we are to be familiar with for IB CS; they are LinkedList and ArrayList. (By the way, interfaces give an list of methods that must be included by classes which implement them, and abstract classes have actual methods and attributes, from which you can extend classes, but they themselves cannot be instantiated - so both "simply" inform how classes below them in a given hierarchy will be implemented.)

The Collections Classes

The six Java Collections classes we can use (including ArrayList and LinkedList) are similar to arrays in that they hold references to objects and they can be managed as a group. However, unlike arrays, collections are, or can be dynamic; they can also grow and shrink in size automatically when objects are added or removed. And so, unlike arrays, collections do not need to be assigned a certain size when instantiated. Collections cannot hold primitive types per se, such as int, long, or double, but they can hold objects from the equivalent Wrapper Classes such as Integer, Long, or Double. (Modified from Wikipedia.)

When declaring Collections instances, we declare the type of the collection within the "chevron" symbols following the collections class name. For example:

ArrayList<Student> students = new ArrayList<Student>( );

LinkedList<Integer> idNumbers = new LinkedList<Integer>( );

 

----------------- " -----------------

Constructing ArrayList and LinkedList Algorithms

Now onto the assessment statement itself, "Construct algorithms using the standard library collections included in JETS."

For this, primarily refer to the "JETS" IB document, page 8, and the pseudocode examples in the Pseudocode in Examinations document, and past papers. (And see below.)

But, first, let's take a look at the full suite of methods available to us in both the ADTs referred to in the Teaching Note: ArrayList (not in the JETS document), and LinkedList.

Java's LinkedList and ArrayList Classes

LinkedList - list specialist

LinkedList has a more actual methods than ArrayList partly because it is made to work either as stacks or queues, and ArrayList is not. So ArrayList doesn't have all of the functions for working with the ends: addFirst, addLast, peeking, popping and polling. Another thing making the LinkedList list of methods seem more impressive is that there are "doubles"; several processes are represented by two methods - for example, pop( ) is just a more stack-specific name for removeLast( ).

ArrayList - full data set specialist

But, of the few extra functions that ArrayList has that LinkedList does not, there are some really important ones if dealing regularly with a full data set, not just the ends. For starters, there's sort( ). And ArrayLists' ability to iterate through the whole structure is a lot more developed, with methods like forEach( ), iterator( ), and replaceAll( )

So when you want stack and/or queue functionality, you would choose LinkedList, but for sure ArrayList is very useful too when you want to work with not just the ends of a data set.

JETS - Java Examination Tool Subset

JETS stands for Java Examination Tool Subset, and is a document that shows you the kind of coding standards to expect on IB CS exams - though it's generally the way we do things, and doing lots of past papers is the best way to be most comfortable with this anyway.

Note that there is an inconsistency between the Teaching Note above and the actual JETs document; only the LinkedList is shown in the JETS document.

Here are all of the functions listed in the original JETS document: Though note that they are just listed - the explanations of what they do are not there. But, on the other hand, the next assessment statement's Teaching Note says the following: "In examination questions, definitions of ArrayList and LinkedList methods will be given where necessary." One way or the other, you should enter the exam knowing how the following methods do work.

.add(E e) 
.add(int index, E element)      Inserts the specified element at the specified position in this list.
.addFirst(E e)                  Inserts the specified element at the beginning of this list. 
.addLast(E e)                   Appends the specified element to the end of this list.

.clear()                        Removes all of the elements from this list.
.element()                      Retrieves, but does not remove, the head (first element) of this list.

.get(int index)                 Returns the element at the specified position in this list.
.getFirst()                     Returns the first element in this list.
.getLast()                      Returns the last element in this list.

.remove()                       Retrieves and removes the head (first element) of this list.
.remove(int index)              Removes the element at the specified position in this list.
.removeFirst()                  Removes and returns the first element from this list.
.removeLast()                   Removes and returns the last element from this list.

.size()                         Returns the number of elements in this list.
.isEmpty()                      Returns if the list is empty.
		

The difference between get( ) and remove( ): In fact, both return the object, but in the case of remove( ), it is removed also. So if you are looking to work with the data, either one will work, but get( ) will leave it in the list and remove( ) will remove it from the list. So the choice you make should be based on intention; if it is your intent to simply get the data, use get( ), and if your intent is to remove, use remove( ).

And even though remove( ) returns the object, you can still use it if you just want to remove it, even though not receiving the object where the call to remove is made. So, either of the following will remove the element; the first one has it go "poof into thin air", and the second uses it:

myList.removeFirst( );

and

Student s = myList.removeFirst( );

(And in terms of the full LinkedList and JETS, remember that many of the methods which are not part of JETS, really are there. For example, peek( ) and poll( ) work the same as getLast( ) and getFirst( ), it's just that they are better stack and queue specific terms. And the same goes for pop( ) and dequeue( ), as they are preferred for stacks and queues, rather than using removeLast( ), and removeFirst( ).)

Past Paper LinkedList Construction Questions

This is primarily what this assessment statement is geared toward. Though most of the notes above is setting up Collections, and below is possible applications of them.

And the best thing to do at this point is make sure there is lots of time in March and April to do lots, if not all of the following questions. The thing is that the LinkedList parts of the questions come at the end, so it's better to do them all as part of last stage exam preparation.

From past paper printouts that can't leave the class, look up the following questions.
(JSR Note: The digital version of these is in a folder "Past Papers LOOK INSIDE".)

As with all past papers, it is best to prioritize the latest exams. So working backward:

Nov. 2017: Q 18 - page 18
May 2017: Q 15 - page 16
Nov. 2016: Q 20 - page 15
May 2016: Q 17 (a) and (b) - page 17 - but not really; more arrays only
Nov. 2015: Q 18 - page 18
May 2015: Q 18 (c) and (d) - page 16 Most of these others are construction questions primarily.
Nov. 2014: Q 17 - page 18
May 2014: Q 17, - page 19

Practice questions .rtfd compressed file.

*** JSR Note: Consider adding simpler set-pieces for the middle of Year 2.***

Stack & Queue Class Made from Inheriting LinkedList

Next, as a possible question, which combines a couple of OOP Option topics, but also as a very good review of LinkedList, stack & queues, and inheritance, check out this straightforward and nice application of inheritance.

(And here's a reminder of how inheritance works.)

 4 import MyLinkedList;
 5 
10 public class MyStack extends MyLinkedList{
11     
12     public MyStack(){       
14     }
15     
16     public void push(Object o){
17         super.addFirst(o); //or the way it was called in D.4.10, insertAtHead
18     }
19     
20     public Object pop(){
21         return super.removeFirst();
22     }
23 }
 

 4 import MyLinkedList;

10 public class MyQueue extends MyLinkedList{
11     
12     public MyQueue(){     
14     }
15     
16     public void enqueue(Object o){ 
17         super.addLast(o); //or the way it was called in D.4.10, insertAtTail
18     }
19     
20     public Object dequeue(){
21         return super.removeFirst();
22     } 
24 }

----------------------- " -----------------------

----------------------- " -----------------------

LinkedList Applied to a GUI IB CS IA Situation

***This is not necessary for this particular assessment statement*** but it fits in nicely here, and is good reinforcement. This is an example of how to use LinkedList in your IB CS internal assessment. And note that you have a situation that works as either a stack or a queue, you should; the IB expects that you will use "Libraries" which help you not reinvent the wheel. So if you have a situation in which a data structure will grow or shrink in size, you should definitely use a stack or queue rather than an array. And it's not that hard; in fact it's easier than doing it from scratch.

The GUI class using LinkedList

 26 public class GUICars extends javax.swing.JFrame {
 27  
 34     LinkedList <Car> carLinkedList = new LinkedList();
 35     
 36     public GUICars() {
 37         initComponents();
 38         myInit();
 39     }
 40                                                            
328     private void entryButtonMouseReleased(java.awt.event.MouseEvent evt) {                                          
330         int numDoors = 5;
331         if(threeDoorRB.isSelected()){
332             numDoors = 3;
333         }else if(fourDoorRB.isSelected()){
334             numDoors = 4;
335         }
336         
337         carLinkedList.add(new  Car (carColorTF.getText(),  carNameTF.getText(),  isManual.isSelected(),  numDoors));
338         carColorTF.setText("");
339         carNameTF.setText("");
341     }                                         
342 
344     private void displayPanelMouseReleased(java.awt.event.MouseEvent evt){
345          for(int i = 0; i < carLinkedList.size(); i++){
346             displayTable.setValueAt(carLinkedList.get(i).getColor(), i, 0);
347             displayTable.setValueAt(carLinkedList.get(i).getName(), i, 1);
349         }
350     }

The Sort&Search Class using LinkedList

 6 public class CarSortAndSearch {
 7 
 8     public void sortByCarName(LinkedList <Car> carLinkedList) { 
                                         //SO HERE'S A SORT OF A LINKED LIST FOR YOU TO USE IF YOU WANT
 9         int n = carLinkedList.size();
10         boolean sorted = false;
11         while (!sorted) {
12             n--;
13             sorted = true;
14             for (int i = 0; i < n; i++) {
15                 if (carLinkedList.get(i).getName().compareTo(carLinkedList.get(i).getName()) > 0) {
16                     //Swap:
17                     Car temp = carLinkedList.get(i); //making a temporary carList object
18                     carLinkedList.set(i, carLinkedList.get(i+1)); //set the first to be the second
19                     carLinkedList.set(i+1, temp);  //set the second to be the temp       
20                     sorted = false;
21                 }
22             }
23         }
24     }
25 
26     public int binarySearchCarName(String carToSearchFor, LinkedList <Car> carLinkedList) {
                                         //AND HERE'S A BINARY SEARCH OF A LINKED LIST TO USE IF YOU WANT
27         int low = 0;
28         int high = carLinkedList.size() - 1;
29         while (low <= high) {
30             int mid = (high + low) / 2;
31             if (carLinkedList.get(mid).getName().equalsIgnoreCase(carToSearchFor)) {
32                 return mid;
33             } else if (carLinkedList.get(mid).getName().compareTo(carToSearchFor) < mid) {
34                 low = mid + 1;
35             } else {
36                 if (carLinkedList.get(mid).getName().compareTo(carToSearchFor) > mid) {
37                     high = mid - 1;
38                 }
39             }
40         }
41         return -1;
42     }
43