Linked Datastructures
Insertion
When we want to insert a node into an existing linked list we must change the existing references. If we want to insert a node Y between two connected nodes X and Z then we must change the next reference of the X node to the node Y and set the next reference of the node Y to the node Z.
There are multiple edge cases we must account for. If the list is empty then insertion of a node means creating a list in the first place, if we want to insert a node in the front, then we must also set the head node reference to the new head of the list, if the node is inserted as the last element then we must make sure that its next reference is null.
Linked Datastructures
add Method
The add method inserts an element at the end of the list. To achieve this we must navigate to the last element and then add the node. We must navigate to the last node and not move past it as if we move to the null reference we cannot add the node to linked list anymore. Hence we must always check when the next reference is null and not when the current node is null. We can then add the node to the end of the list.
Another problem we might encounter is that when the list head reference is null then we are adding to an empty list and must thus directly add the null as the new head reference.
Linked Datastructures
addFirst / removeFirst
The methods to add and remove the first element seem straight forward at first but we must also be careful when the list is empty. As when the list is non-empty we have to replace the head with the node the head has a reference to in its next attribute. This reference may be null and thus there exists no null. That can be done using a this.head = this.head.getNext() assignment. However when the list is empty we cannot remove an element and calling this.head.getNext() where head is null would result in a NullPointerException. Hence we do nothing when the head is null when removing the first element.
When adding to an empty list we once again create a new list and else change the head to a new node that contains a reference to the old head node in its next attribute.
Linked Datastructures
get Method
When implementing the get method we use to usual approach with creating a copy of the head reference and then iterating over the linked list until we reach the i-th node. We must make sure that we do not dereference the null reference. For this reason we must at each step of the iteration verify that the current reference is not null. If the current reference ever gets null then the index is out of bounds.
We return null if the index it is out of bounds and else we return the node at the i-th index. We indicate this in the top-of-method comment such that it is clear what the method does.
Linked Datastructures
removeLast method
The removeLast method is the most complicated to implement. We must navigate to the node before the last element to be able to delete the last node in the linked list. If we navigate to the last node we cannot unlink it from the linked list as we cannot access the next attribute of the previous node in the linked list and we cannot delete the object itself. Deleting objects is something we cannot do in Java, and it happens in the background via the Java garbage collector.
Setting a reference to null does not delete the underlying object. If any reference to it exists then the object still exists and is visible to the user. If all references are lost then the Java garbage collector will eventually get rid of it.
Hence we must navigate to the node before the last node to be able to delete its reference to the last node. Then we cannot reach the last node anymore and for us the node does not exist anymore.
Linked Datastructures
The size Attribute
Whenever we want to output the length of a datastructure we use the length() method. The single exception to this is given by the array which has a length attribute instead. This is due to the special implementation of arrays and also the fact that arrays are of fixed length.
We add a size attribute to the class to allow to retrieve the size of the list. We initialise the size attribute with the value 0 and add +1 to it whenever we add an element to the list. When we call the removeFirst or removeLast method we must make sure that the list is non-empty before adding -1 to the size attribute.
The size attribute is a good example for why attributes should be declared private (or public if they are final) as we only want a user to read its value but not write to it directly. Changing its value follows from insertions and deletions and a user cannot directly manipulate the size attrbute. To the left only modifications are shown for the removeFirst method, note however that all insertion / deletion methods have been changed accordingly.
Linked Datastructures
Output
To output datastructures we implement the toString() method which returns a String representation of the given datastructure. The toString() method is a method all classes can implement which is why we add the JavaDoc @Override declaration (more on this later).
Whenever an object is passes to the println or print method of the PrintStream System.out the toString() method of the corresponding class the object is an instance of is called. If no such method is specified the string x@y is printed where
-
x = package.class
-
y = hashcode
This behaviour is very different for arrays but for all other objects this is the case.
To the left one can see two simple implementations of the toString method, where one uses Strings and the other uses StringBuilder. Strings create a new object every time an operation is made on them, hence we must expect a large number of objects being created inside a for loop that concatenates strings in its body. Thus we use StringBuilder which avoids this by using a buffer to add more characters even after being initialised. You do not have to do this but it is considered good practice to do so.
Programming
Good Style
Having a good programming style is important to allow for efficient implementation, debugging and making changes in existing code. Many times it is stated that good programming style is for other readers, but most importantly it is for you hence I would strongly advice you to take good programming style serious. For this purpose read the quickguide discussing good programming style.
Rational Numbers
Introduction
We have seen that double type values are not 100% accurate and especially when many operations are involved the limitations of double get noticeable. Even rational numbers suffer from this inaccuracies when represented using the double type. We will now use this and implement a rational number type which is much more accurate (up to the limitations of the int type) than double type representation of rational numbers. This will also serve as an example for how to approach the implementation of a class.
Rational Numbers
Definition
A rational number is a number that can be represented as a fraction of two whole numbers (... , -1, 0, 1, ...). Hence whole and natural numbers are also rational numbers, as we can divide them by 1 and get a fraction that represents them. Irrational numbers like pi and e are not rational however as they cannot be represented using a fraction.
Fractions come with a whole set of operations which ca be done given the nominators and denominators of the involved fractions.
Rational Numbers
Implementation
One might now immediately start implementing the class and add attributes nominator and denominator and all operator methods. But this is a bad way to approach this as we should first make sure that we understand how we will implement our class. We must first answer the following questions before starting the implementation.
-
Attributes: What attributes should the class have?
-
Methods: What methods should the class have?
-
Objects: How can one work with the objects, can they be compared, can they be ordered, how do we access them and how do we construct new instances of the class?
Rational Numbers
Canonical representation
1/2 = 2/4 = 3/6 = 4/8
Often there may exist different representations of the same object. In the rational numbers both 1/3 and 30/90 are the same rational number. We usually would prefer to use 1/3 to represent all fractions of the form 1/3 * x/x. This representant should be unique for all objects of a class. We call this (unique) representant the canonical form of the object.
By asking ourselves the above questions we notice that the rational numbers require a canonical form for the class to be well-defined. Hence we will store any given combination of nominator and denominator in the canonical form and operations should also return results in the canonical form. We must hence first create a function "normalise" which transforms any nominator and denominator combination into the canonical form.
Rational Numbers
Constructor
We implement the constructor such that it always stores a rational number in its canonical form. For this purpose we use the euclidean algorithm to retrieve the greatest common divisor (gcd). We can the divide both nominator and denominator to get the canonical form. I do not want to go into great detail why this is the case but make sure you understand how this step works as it is a good test if you understood some topics discussed discrete mathematics. Our constructor must also make sure that the denominator given as input is non-zero and if that is the case we throw an exception.
We use a private static method that has the same implementation as the gcd method shown in the quickguide on good programming style.
Rational Numbers
Normalising Objects
We should also define the normalising utility without using the constructor as we do want to reuse objects instead of having to create a new object for every single operation. Thinking about efficiency is not the goal of this lecture but it is good to start thinking about it early so when it gets important you are already used to making your class more efficient than just the naive solution.
We also make the normalising utility private, i.e. non-visible from outside the class as a client has to never use it any object and any result they get from the class is in canonical form and hence already normalised. This gives us encapsulation and allows us to offer a service without having to reveal its implementation.
Rational Numbers
More Constructors
As always when this makes sense we should also define a default and constructor and any constructors suitable for the class we are writing. We use the general constructor inside the other constructors.
Constructors are to be declared as public and one should think about the choice of constructors well, as it helps improving the clients experience when working with the class.
Rational Numbers
Arithmetic Operators
We now start adding the utility methods we wanted to add at first. We now have the underlying framework in pace to allow for this to work. This is a good example for why putting in some thought on how to structure a class before implementing it is a good idea as now any inconveniences, like the result of a division not being defined because we would divide by zero, are being handled by the constructor.
We add a method add for addition, sub for subtraction, mul for multiplication and div for division.
Rational Numbers
Comparison Operators
In a next step we would also like to implement comparison operators like <, >, <=, >= and ==. We cannot use operators like < as they are only defined for primitive type variables. We use methods to implement their functionality for objects.
When doing comparisons we often subtract one number by the other and check if the result is positive, negative or equal to zero to determine which number is greater than the other.
For this purpose we add an internal method called greaterZero which returns true if and only if this rational (the instance the method is being called on) number is greater than zero. Being positive or negative means that the number is non-zero. This is often understood wrong and then leadss to mistakes.
Rational Numbers
Methods for Output
We now want to add methods useful for output. This includes the usual toString method which every class should include. In addition to that we also add a toDouble method which allows use to convert from the Rational type to the double primitive type.
The toString method will be called whenever an object appears inside the print / println methods of the System.out PrintStream.
The toDouble method has to be called by the client whenever they want to retrieve the Rational number as a double value.
Rational Numbers
Methods for Equality
One might have noticed that when we discussed the comparison operator methods we did not specifically mention the equality comparison. This is because equality comparison is special. Similarly to the toString method all classes by default have an equals method. This equals method simply compares the references stored within the reference variables by default.
When overwriting this method we pass as a parameter an arbitrary object. We will later see what this means and how this works. We also notice that Java recognises the two methods called equals as different methods, because the signatures of the methods are different (we will see later that different sometimes is not enough). The bottom equals method does the following
-
Check if the given object is of type Rational.
-
If the given object is of type Rational we can declare it to be an object of type Rational.
-
We can then call the internal equals method on it.
Memory
Addresses
Java programs, their variables, their dynamic structures like method calls (especially with recursion) and objects are stored in memory. Memory typically is not addressed byte-wise but instead we look at it using blocks of certain size. 4 Bytes or 32 bits for example. In modern computers these blocks are 64 bits. To the left one can see an example of how one can imagine the addresses in memory to be arranged. Addresses are multiples of 4 as each block is 4 bytes.
The addresses in the example to the left are denoted in hexadecimal notation. We have no access to these addresses in Java but it is good to have a basic understanding of how addresses in memory work.
Whenever a variable is declared inside memory space must be allocated (reserving space in memory) even before the value or object is initialised. For a reference variable both space for the variable itself and the object must be reserved.
Memory
Different Sections
There are different parts of memory that store different parts of a program. Each part serves its own purpose and they are the following
-
static data: In the static data section we store all data which cannot be changed, e.g. constants, information about the class, etc.
-
heap: In the heap section we store all objects which have been initialised using the new operator. The only exception to this is strings being initialised without the new operator which are stored in the static data as they are immutable and thus also considered as constants.
-
stack: On the stack we allocate for each method a so-called stack frame. Any variables declared inside a method are allocated (their value not the object (reference value / primitive value)) on the corresponding stack frame. Parameters to the method are also stored on the corresponding stack frame.
The stack grows upwards from higher addresses (larger value) to lower addresses and the heap grows downwards from lower addresses (smaller value) to higher addresses.
Memory
Objects
When we initialise an object and store a reference to it in a variable then the variable and its reference are stored in the stack, whereas the object itself is stored on the heap. For each attribute of the object we require some space on the heap to be allocated. A certain amount of space on the heap (marked in blue) is reserved for internal object data, like its type, its number of attributes, etc.
In the example to the left the following statement lead to the memory configuration
-
Rational r = new Rational(1, 2);
One can see that this lead to one variable being stored on the stack and the object being stored on the heap.
Java
Packages
package packageName;
When we have multiple classes which belong to the same overall general structure we put them into the same package. Each file can belong to at most one package. If no package is specified then the file is put into an unnamed package also referred to as the default package.
A class must declare that it is part of a package if one wants it to be part of said package. Subpackages have a similar name as the packages, e.g. java.util and java.util.Arrays but they are not part of the same package, rather java.util.Arrays belongs to java.util. Java packages creates a namespace which allows us to avoid naming conflicts. Packages to classes are like what folders are to classes. We can import all subpackages belonging to a package by using a star, e.g. import java.util.*.
Java
Importing Packages vs. Importing Classes
import java.util.*;
import java.util.Arrays;
When we import a class we must specify its full package name, e.g. import java.util.Scanner; whereas when we import an entire package we only specify the package name, e.g import java.io.*. The java.lang package is imported by default.
If two classes with the same name exist in the classpath of a java program and if one is imported as part of an entire package and the other is explicitly imported as a class, then the one imported as a class gets precedence over the one imported as part of a package. As an example if we have a class Example which is part of the package java.foo which was imported as a whole, and we also import java.bar.Example directly as a class, then the Example class within the java.foo package is ignored.
Java
Directly Importing Utility
java.util.Scanner =
new java.util.Scanner(System.in);
If for some reason we do not want to import a package or a class or we have a naming conflict (which should never happen) we can specifically address a class or one of its methods using the package name. In the above example we could reach the Example class in the java.foo package by using the name java.foo.Example.
Java
File Names
A class named D inside a package a.b.c must be stored in a folder named "c", stored inside a folder "b", stored inside a folder "a" and its name should be D.java.
At least this is true for a public class and classes which are part of a specified package, i.e. not the unnamed package. Classes in an unnamed package (default package) cannot be imported and cannot be reached from other classes which are part of a (named) package.
Java
default modifier
Packages allow us to introduce another modifier. If no modifier is specified, the modifier is called default and then the methods and attributes are visible inside the class itself and all other class declared in the same package.
Java
Nested Classes
Instead of having two classes "ListNode" and "IntList" in different files we could encapsulate the ListNode class by making it a private class within the IntNode class. This allows to fully encapsulate the implementation and only allow access through public methods. There are two options to do this. We can either use the static keyword or not but in both cases we require the private keyword.
When we do not use the static keyword then we talk of inner classes. When we use the static keyword then the nested classes belong to the outer class and require no object of the outer class to exist. We refer to such classes as static nested classes.
Java
Inner Classes
Instances of inner classes are not visible from the outside the class, hence we can encapsulate parts of a class and the objects used by a class. In the example of the LinkedIntList we could encapsulate the implementation of the ListNode object and make it impossible to directly access the instances of the ListNode outside the class.
This would allow us to fully encapsulate the entire structure of the LinkedIntList. All manipulations and accesses would then work over methods specified withing the LinkedIntList class.