A LinkedList is a linear data structure. You already know some linear data structures, such as arrays, where each element has a value and position within the whole. A LinkedList consists of a number of nodes, which contain a value and a pointer which points to the next node in the list.
Image courtesy GeeksForGeeks
The above image shows a 4-node linked list. Each node, including the first and last, have pointers. The first node, the head, contains a value and points to the next node. The last node, the tail, points to null, since it is the last node.Null is a value in java which means empty or nothing.
Note: it is possible for the tail node to point to the head node, in which case you would have a circular LinkedList(covered next).
LinkedList implements two interfaces, List and Deque. List is an interface that is implemented by structures such as ArrayList and Vector(this is a little advanced). Deque extends the Queue interface, which is where LinkedList gets its order from. You can think of LinkedList as a list with a queue, or an order.
There are singly linked lists and doubly linked lists. In singly linked lists, each node has only one pointer which creates a chain in one direction. In other words, you cannot go backwards in a singly linked list. Doubly Linked Lists go in both directions (covered in a later section), and the Java LinkedList class is an example of a doubly linked list.
To implement a LinkedList:
import java.util.LinkedList;
class Main {
public static void main(String[] args) {
LinkedList<String> a = new LinkedList<String>();
// *adding items*
a.add("One");
a.add("Three");
a.add(1, "Two");
System.out.println(a);
// *setting items*
a.set(1, "2")
// *removing items*
a.remove("2");
a.removeFirst();
a.remove(0);
System.out.println(a);
}
}
<aside> 💡 Note that you need to import LinkedList from java’s utility package, or use import java.util.*
</aside>