Logout

Home OOP HL Last Next

D.4.11

Construct algorithms using the standard library collections included in JETS.

 

Teaching Note:

The classes are ArrayList and LinkedList. Students should have a broad understanding of the operation of these lists and their interface (methods) but not of the internal structure.

 

Sample Question:

sdfsdfsf

JSR Notes:

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

 

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

The Java "Collections" classes come from the Java Collections Framework (JCF) which includes ArrayList and LinkedList. You don't need to understand the heirarchy 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

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 familiary with for IB CS; they are LinkedList and ArrayList. (By the way interfaces just give an list of methods to implement, and abstract classes have actual methods and attributes, from which you can extend classes, but they themselves cannot be instantiated - so both inform how classes below them in a given hierarchy will be implemented.)

The Collections Classes

The six Java Collections classes (including ArrayList and LinkedList) are similar to arrays in that they both hold references to objects and they can be managed as a group. However, collections 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 perse, 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.

But, first, let's take a look at the full array 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 because it is made to work either as stacks or queues, and ArrayList is not. So ArrayList doesn't have all of the funtions for working with the ends, addFirst, addLast, peeking, popping and polling.

ArrayList - full data set specialist

But, of the few exta 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... 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.

  		

LinkedList<E> where E defines the type of elements held in the list

Constructor LinkedList<E>()

.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 are fine:

myList.removeFirst( );

and

Student s = myList.removeFirst( );

Both of the above remove the first element of the list; it's just that with the second one we receive it.

(By the way, 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 quesitons. The thing is that the LinkedList parts of the quesitons come at the end, so it's better to do them all as part of last stage exam preparation.

As I did to coallate the following, in class, if using digital versions of past papers, just do a Command-F for LinkedList to find the questions related to it. Folder: "Past Papers LOOK INSIDE".

May 2014: Q 17, - page 19

Nov. 2014: Q 17 - page 18

May 2015: Q 18 (c) and (d) - page 16

Nov. 2015: Q 18 - page 18 - mainly tracing

May 2016: Q 17 (a) and (b) - page 17

Nov. 2016: Q 20 - page 15

May 2017: Q 15 - page 16

Nov. 2017: Q 18 - page 18

 

********** TO DO: 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 interitance, check out this straightforward and nice application of interitance.

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

 4 import java.util.LinkedList;
 5 
10 public class MyStack extends LinkedList{
11     
12     public MyStack(){       
14     }
15     
16     public void push(Object o){
17         super.addLast(o);
18     }
19     
20     public Object pop(){
21         return super.removeLast();
22     }
23 }
 

 4 import java.util.LinkedList;

10 public class MyQueue extends LinkedList{
11     
12     public MyQueue(){     
14     }
15     
16     public void enqueue(Object o){
17         super.addLast(o);
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. This is an example of how to use LinkedList in your IB CS internal assessment. And note that 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 in many ways it's easier.

The GUI class using LinkedList

array list project array list project 2

 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) {
 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) {
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