Linked Lists - 1
Learning linked lists in Java with Udemy course - Practical Data Structures & Algorithms in Java
Linked list
Unlike an array([]), elements of a linked list are not managed with continuous indexes. A linked list consists of nodes, and each node has data and a reference(link) to the next node.
Array vs. Linked list
It is easier in a linked list to insert/delete data compared to an array. By the way, the linked list without an index usually slows down the speed of searching because access to certain elements requires sequential searching. In other words, the insertion/deletion of the first data is performed within the time of O(1) in a linked list. When we insert or delete data in an array at a specific index, we have to move all the rest of the data to the back from the point, but in the case of a linked list, we do not have to do it. However, the addition/deletion of data at one point rather than the first one takes time to retrieve the data, so it has O(n) performance.
Singly Linked List
It is the simplest form of a linked list only with reference to the following nodes.
public class SinglyLinkedList {
private Node first;
public boolean isEmpty() {
return (first == null);
}
// used to insert at the beginning of the list
public void insertFirst (int data) {
Node newNode = new Node();
newNode.data = data;
newNode.next = first;
first = newNode;
}
public Node deleteFirst() {
Node temp = first;
first = first.next;
return temp;
}
public void displayList() {
System.out.println("List (first ===> last)");
Node current = first;
while(current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
public void insertLast(int data) {
Node current = first;
while(current.next != null) {
current = current.next; // we will loop until current.next is null
}
Node newNode = new Node();
newNode.data = data;
current.next = newNode;
}
}