Classes
Methods
One might have observed that some methods can only be used when an instance of a class exists. This instance is required because the method is a member method and thus works individually on each object. Methods which are not member methods can directly be called on the class they are defined inside. If a method call is made from within the class, e.g. from the main method of said class, then we do not need to write className.methodName() and can simply call the method directly using methodName().
The example to the left shows that, even though we do not have to address methods of a class which we are inside of using its name, we can address all non-member methods using the class name they are defined in.
Static
Definition
The behaviour described above is why we have the static keyword in Java. Member methods and member variables (attributes) have no static keyword. Non-static methods and non-static variables are individual to each object whereas static methods and static variables are globally defined for the class itself.
-
Static : A method or variable being static allows it to be called on the class it is defined within without requiring an instance of this class to exist.
-
Non-static : A method or variable which is non-static requires a class instance to be accessed. They are individual to each object and a non-static variable (an attribute / member variable) can have different values for each object. Similarly non-static methods (member methods) may behave differently on each object.
Visibility
Attributes I
When working with classes we can add attributes to the class which will contain the state of an instance of the class. For now static variables inside a class are ignored and will be discussed later on.
Attributes are most often declared with a so-called modifier. Until now we have seen the modifier "public" most often. The public modifier means that all attributes of an object can be accessed given a reference to it. This is most often not desired as it is better consensus to regulate the access to the state of an object via its member variables. Allowing the user only to access the state of an object via member methods also ensures that certain unwanted changes cannot be made and allows for a well-defined change.
Visibility
Attributes II
To assure that any change to the state to the variables is made through member variables we make all attributes private. This means that instead of adding the public modifier we add the private modifier. This results in the attributes not being accessible from outside the class, i.e. given a reference to the object outside of the class of the object one cannot access its attributes.
Having all attributes of a class be private allows for encapsulation where data is not directly accessed and we control which accesses can be made an which not. This is important as you would not like your bank salary to be a public attribute. Encapsulation also allows us to only show the utility of a class rather than its implementation. The implementation of a class should not be of concern to a client using the class.
Visibility
Abstraction
Encapsulation also allows for abstraction as a client does not have to worry about the implementation of a class and instead can use its utility without having to know how it works. A client may assume that the given methods work as intended.
This abstraction process is vital in the process of writing large programs as without it a programmer has to worry about large amounts of code and has to keep an overview over it. This is not feasible for most larger projects, hence abstraction is important and sometimes the only way to conquer large projects.
Visibility
This
Whenever we access attributes or member variables of a class using an object we are accessing the attributes and member variables specific to the object itself. In Java the keyword "this" is used to tell the user that variables and methods accessed within a class belong to whatever object they are accessed over. Inside a static method or for a static variable inside a class we cannot use the "this" keyword on.
In most cases the this keyword is not specifically written but it is good practice to do so as it makes your code easier to understand. Also when you use this. you can use the auto-complete feature of Eclipse.
There is one case where you have to use this and it is when the parameters of a constructor (encouraged) / method (discouraged) are called the same as the attributes. We then use this.x to differentiate between the parameter x of the method (which will be selected when using the variable name x) and the attribute x. This is what we call shadowing, i.e. when parameters of a method have the same name as attribute Java chooses the parameters and not the attributes.
Visibility
Getter / Setter
When the attributes of a class are private we might need getter (accessor) methods to read from the attributes or setter (mutator) methods to write to the attributes. We can choose which attributes we want to allow a client to read from / write to. Getter and setter method can be automatically created in Eclipse which is very helpful.
One might argue that most of the times for simple programs every attribute requires a getter and setter method and thus we can just use the public keyword instead. We use good practices to ensure that once these good practices get important one has already adopted them as otherwise mistakes happen very quickly.
In addition to getter and setter methods one should also make sure to add a default constructor and a general constructor to each class.
Visibility
Private Methods
Sometimes methods can also be private. A good example for this is when a method is only used within the class or when a method only works for a certain state of the object and one wants to avoid that the client unknowingly does an illegal operation that invalidates data.
One might want to add optimisations to their code which should not be visible to the user. A good example for this we will see later on when we will implement our own List type and use the same internal method to read from an element in the list and write to it. This method will navigate to the object and return it, the read / write methods then simply read and write while using the private internal method to do the navigation process. This is another good example for encapsulation.
Classes
One Constructor Policy
To remove redundancy it is considered good practice to call the main constructor within all other constructors using the this keyword as shown in the code to the left.
Often times a class will have multiple constructors which require more than two lines of code to initialise an object hence it makes much sense to first implement the general constructor and then use it in all other constructors one defines within a class.
Classes
Static Variables
Static variables do exist in Java and they are to be used only with the final keyword as well for constants which are consistent over all objects of a class. The final keyword makes the value (the reference and not the object for reference variables) of a variable unchangeable once it was set. There is a handful of examples where a static variable is non-final and I am certain that in Eprog you will never have to use them. If you do then you are doing something wrong. In recursion people often say they require a global static variable, this is however almost never the case.
Linked Datastructures
Introduction
We have seen arrays which are contiguously arranged values of the same type and have a fixed length. We might want to be able to store a unknown number of elements inside some datastructure. This can be done by having so called linked objects that consist of a value or object and a reference to the next linked object. We refer to the linked objects also as nodes.
Linked datastructures are very useful as they allow us to add as many nodes as we desire as long as there is space in memory. Arrays have a fixed length which limits their usage.
Linked Datastructures
The Last Node
Having a list of linked objects we must have some node which is the last one and refers to no further node. A reference that points to no object is exactly what null is in Java. Hence we use null as the value of the reference.
Alternatively in figures a dash through the reference part of the linked object signifies a null reference, i.e. pointing to no further node. It is important that the last node always contains a null reference. This then forms a chain of nodes with a first and last node.
Linked Datastructures
The First Node
The first node in the chain must be referenced to as well but not by a node. We simply use a reference to it and call this reference the reference to the head of the list. This reference is the only reference we need to find all other elements in the list as they are linked together and no node proceeds the head of the list.
Linked Datastructures
Nodes in Java
The goal is to now implement the nodes / linked objects using a Java class called "ListNode". To the left one can see the general structure of the node. We will use the data field to store a value / object and the next field to store the reference to the next node.
What type should the reference have? It points to a ListNode object hence the suitable type is ListNode. This might seem confusing at first as it yields a somewhat circular definition. However one must realize that a variable of type ListNode is simply a reference to a ListNode object and is well-defined on its own without having to know how the ListNode class is implemented.
We add the usual general constructor, a constructor when no reference is specified and a default constructor to the class. This already gives us the general structure of the class and allows us to primitively create linked lists.
Linked Datastructures
Java Convention
Some of you may have noticed that we redundantly defined three constructors separately instead of reusing the general constructor. This is correct and we must keep to the one constructor policy and reuse the general constructor in all other constructors to avoid redundancy.
To the left one can see an example of how this could be done. I prefer to write it this way as it uses less space and the reader understands quickly what happens even though the code is compressed to two lines. You may do what you prefer as long as you call the general constructor within all other constructors.
Linked Datastructures
Reference Assignment
ListNode c = new ListNode(3, null);
ListNode b = new ListNode(2, c);
ListNode a = new ListNode(1, b);
When we assign a reference to another reference we simply take the value inside the reference variable which we assign from and copy it into the reference variable which we assign to.
It is important to understand that a variable contains a value, either this value is a primitive type value or a reference. Hence assignments with the equality operator = only copy this value from one variable to the other. If one understands this then most of the operations we will do in the coming lectures will be intuitive and cause little problem. Hence make sure you understand the difference well.
Linked Datastructures
Iterating over List (Wrong)
while (list != null) {
System.out.println(list.data);
list = list.next;
}
When we want to iterate over a list we face one inherent problem. Given a reference to the first element if we were to move to the next node in the list we lose the reference to the previous (head) node. We could store all references to previous nodes along the way, but this is not feasible for large lists. Hence we must simply keep the reference to the head node somewhere for us to keep being able to access all nodes in the list.
To the left one can see how the list reference may be the reference to the head of the list at first but this reference is then lost while iterating over the list.
Linked Datastructures
Iterating over List (Correct)
ListNode current = list;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
We can fix the problem by keeping the reference to the head node unchanged and using a copy of the reference instead. This can be done using the assignment ListNode current = list, which will copy the value inside the variable list (the reference) to the variable current. We can then safely manipulate the value inside the current variable without affecting the value inside the list variable.
If it is unclear to you how this works then I recommend reading both this quickguide and this full story article as they cover the reasons why this is the case.