A linked list is a data structure composed of connected Nodes. Each node contains two items:
A data, also known as the item interested in adding; can be an int, a string, or even an object.
A next, which is also a Node. This is the “link” that connects one node with another node
Arrays are limited based on the capacity provided. E.g., once you define the array's capacity we are “stuck” with that capacity until the program finishes. Therefore, we need another data structure that permits us to “grow” and “shrink” our data as we need.
The node is a small data structure that is used only in the linked list context
The node is composed of the value and the next. The value is the actual data that we are interested in storing. The next is the connection between nodes. The value data type can be anything you would like to store. Since the next is the connection between nodes, its data type is Node. I know what you are thinking, “How can we have a data type of something that we are defining”. This sounds a little bit crazy (or recursively), but if you think about it, the connection between nodes requires similar data types. Therefore, the “bridging” between nodes should be Node.
The node looks as follows:
public class Node{
String value;
Node next;
public Node(String value){
this(value, null);
}
public Node(String value, Node next){
this.value = value;
this.next = next;
}
}
Let us test our code by establishing the connectivity between nodes
public static void main(String [] args){
Node n1 = new Node("A");
Node n2 = new Node("B");
Node n3 = new Node("C");
Node n4 = new Node("D");
Node n5 = new Node("E");
Let us create a connection between nodes to generate
n2.next = n1;
n1.next = n3;
n3.next = n5;
n5.next = n4;
n4.next = null;
By attempting to print:
System.out.println(n2);
What are we expected to get?
Node@7d2d3583
Since we are dealing with objects, we need to extract the actual value that holds the Node object. In this case, will be:
System.out.println(n2.value);
Will print the value of “B”. How about the next value, i.e., the “A”?
System.out.println(n2.next.value);
If we plan to print the entire list we should do something like:
System.out.println(n2.value); //prints B
System.out.println(n2.next.value); //prints A
System.out.println(n2.next.next.value); //prints C
System.out.println(n2.next.next.next.value); //prints E
System.out.println(n2.next.next.next.next.value); //prints D
Obviously, we need to avoid the redundancy of the .next.next…. The question is how? There are different ways to do it
Approach 1: Use the initial node to navigate through the connectivity
while(n2 != null){
System.out.println(n2.value);
n2 = n2.next;
}
The previous routine indeed prints the elements of the connectivity. However, if we attempt to do this again, we will not succeed, since n2 will already be null.
Approach 2: Use a “dummy” to copy the reference of the initial point
Node dummy = n2;
while(dummy != null){
System.out.println(dummy.value);
dummy = dummy.next;
}
Approach 3: Define a toString() in the class Node
The class Node has a field (next), which its type is Node. This is the recursive concept that even defining a class it owns a connection to itself through the next field.
public String toString(){
return value+"->"+next;
}
The first and last
We have two fields in this class, they are called the first and the last.
Constructors and Definition of the class
As we discussed, we only have two fields in this class that make the class unique: the first and the last. In code it looks as follows:
public class MyLinkedList{
Node first, last;
public MyLinkedList(){
first = last = null;
}
}
/**
* isEmpty()
* The method will check if the list is empty
* @returns true if the list is empty, false otherwise
**/
public boolean isEmpty(){
return first == null;
}
/**
* add
* The method will take a String s as a parameter
* and it will add it to the end of the list
* @param s, a String desired to be added to the list
**/
public void add(String s){
Node n = new Node(s);
if(isEmpty()){
first = last = n;
}
else{
last.next = n;
last = n;
}
}
/**
* Size
* The method will count how many nodes are
* in the list.
* @returns the total number of nodes in the list
**/
public int size(){
int total = 0;
Node dummy = first;
while(dummy != null){
total++;
dummy = dummy.next;
}
return total;
}
/**
* find
* The method will check for every item on the Linked List
* if a given target is located
* @param t a String which value need to check in the list
* @returns true if the target was found in the list,
* false otherwise
**/
/**
* countOccurrences:
* The method will take a target, a String, as a parameter,
* and it will count and return the total number of times
* the target appears in the list.
* @param s, a String interested to know how many times
* appears in the list
* @returns the total times the String s appear in the list
*/