Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Following are important terms to understand the concepts of Linked List.
Link − Each Link of a linked list can store a data called an element.
Next − Each Link of a linked list contain a link to next link called Next.
LinkedList − A LinkedList contains the connection link to the first Link called First.
As per above shown illustration, following are the important points to be considered.
LinkedList contains an link element called first.
Each Link carries a data field(s) and a Link Field called next.
Each Link is linked with its next link using its next link.
Last Link carries a Link as null to mark the end of the list.
Data Structures and Algorithms (DSA) in Java using a linked list.
example of implementing a linked list in Java with some common operations:
public class LinkedListExample<T> {
private Node<T> head;
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
public void insertAtFront(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head = newNode;
}
}
public void insertAtEnd(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node<T> current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void delete(T data) {
if (head == null) {
return;
}
if (head.data.equals(data)) {
head = head.next;
return;
}
Node<T> current = head;
Node<T> previous = null;
while (current != null && !current.data.equals(data)) {
previous = current;
current = current.next;
}
if (current == null) {
return;
}
previous.next = current.next;
}
public boolean contains(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
return true;
}
current = current.next;
}
return false;
}
public void display() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedListExample<Integer> linkedList = new LinkedListExample<>();
linkedList.insertAtEnd(10);
linkedList.insertAtEnd(20);
linkedList.insertAtFront(5);
linkedList.insertAtFront(2);
linkedList.insertAtEnd(30);
linkedList.display(); // Output: 2 5 10 20 30
linkedList.delete(5);
linkedList.display(); // Output: 2 10 20 30
System.out.println("Contains 20: " + linkedList.contains(20)); // Output: true
System.out.println("Contains 15: " + linkedList.contains(15)); // Output: false
}
}
In this example, we have a class LinkedListExample that represents a generic linked list. It has an inner class Node that represents a single node in the linked list. Each node contains a data field of type T to store the value and a next field to point to the next node.
The insertAtFront method inserts a new node at the front of the linked list. If the list is empty, it sets the new node as the head. Otherwise, it updates the next pointer of the new node to point to the current head and then sets the new node as the head.
The insertAtEnd method inserts a new node at the end of the linked list. If the list is empty, it sets the new node as the head. Otherwise, it traverses to the end of the list and adds the new node there.
The delete method removes a node from the linked list. It first checks if the head node contains the desired data. If it does, the head is updated to the next node. Otherwise, it traverses through the list until it finds the node to delete. It updates the next pointer of the previous node to skip the node to be deleted.
The contains method checks whether a given data value exists in the linked list. It traverses through the list, comparing each node's data with the given value.
The display method iterates through the linked list and prints the data of each node.
In the main method, we create an instance of LinkedListExample, insert elements at the front and end of the list, display the list, delete a node, display the updated list, and check if the list contains specific values.
When you run this code, it will output:
2 5 10 20 30
2 10 20 30
Contains 20: true
Contains 15: false
Comments