A brief introduction
Linked List is a linear collection of objects, which is composed of nodes pointing to the next node. Each node contains a value and a reference to the next node in the sequence. Most of the operations applied in a linked list (add, remove, search, etc.) will require sequencial scanning most of the time.
As you can notice, each node will always have a pointer to the next node and a value, this is called a single linked list. If a node has a link to the previous and to the next one, it is called a double linked list or a circular linked list.
Implementation
The first step will be creating a node class:
public class Node<T>{
private Node next;
private T value;
public Node(){
}
public Node(T value){
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
This is a POJO (Plain Old Java Object) of a Node class, which contains a value and another Node that will be the “Next” node. If you ask yourself about the “T” I have in there, I am declaring the Node class as Generic, enabling the option to choose what datatype to use. Now, we will be creating varios operations used, starting with the add.
public class MyLinkedList<T>{ private Node head; private static int counter; public void add(T value){ if (head == null) { head = new Node(value); } else { Node temp = new Node(value); Node current = head; while (current.getNext() != null) { current = current.getNext(); } current.setNext(temp); } counter++; } }