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++; } }