Java Tutorial
.
A LinkedList in Java is a linear and fundamental data structure that stores the Java components. It offers Java users an efficient, flexible way to store and work with various Java elements.
Java LinkedList allows dynamic size adjustment as and when elements are subtracted or added. Here in this tutorial, you will learn what is LinkedList, its needs, its operation, demonstration, LinkedList in a data structure, and much more.
LinkedList is an element sequence where all the elements are kept safe in nodes. Along with the elements, each node has a reference point directed toward the next node. Read on to learn more about various linked list methods in Java, the insertion and deletion process in a LinkedList in Java, the creation of a LinkedList in Java, and so on.
Linked lists are used because they have a range of advantages. They make better use of the memory from the viewpoint of allocation. The size for this list is also not pre-determined and thus allows easy addition and subtraction of elements from the list. Even for sorting algorithms LinkedLists are more efficient.
To create a linked list in Java, we must first define a class to represent the nodes of the list and implement methods to perform various operations on the list.
Let us understand linked lists with an example of creating a linked list.
We will have two classes: Node and LinkedList. The Node class will represent a single node in the linked list, storing an integer value and a reference to the next node. The LinkedList class will represent the linked list, maintaining a reference to the head node.
The LinkedList class will provide methods to insert nodes at the end of the list (insert method) and display the list's contents (display method).
We will then add the main method to create an instance of the LinkedList class and insert some elements into the list using the insert method. Finally, we display the contents of the list using the display method.
Here is the code:
class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head; public LinkedList() { this.head = null; } public void insert(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } public void display() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } } public class Main { public static void main(String[] args) { LinkedList list = new LinkedList(); list.insert(10); list.insert(20); list.insert(30); list.insert(40); list.display(); } }
A doubly linked list is a type of linked list where all the nodes contain references to both the next and previous nodes, allowing for efficient traversal in both directions. In Java, you can implement a doubly linked list using a custom class representing the nodes and maintaining the necessary references.
Here is an example:
Code:
class Node { int data; Node prev; Node next; public Node(int data) { this.data = data; this.prev = null; this.next = null; } } class DoublyLinkedList { Node head; Node tail; public DoublyLinkedList() { this.head = null; this.tail = null; } // Methods for various operations on the doubly linked list go here public void addFirst(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { newNode.next = head; head.prev = newNode; head = newNode; } } public void addLast(int data) { Node newNode = new Node(data); if (tail == null) { head = newNode; tail = newNode; } else { newNode.prev = tail; tail.next = newNode; tail = newNode; } } public void insertAfter(Node node, int data) { if (node == null) { return; } Node newNode = new Node(data); newNode.next = node.next; newNode.prev = node; if (node.next != null) { node.next.prev = newNode; } node.next = newNode; if (tail == node) { tail = newNode; } } public void remove(Node node) { if (node == null) { return; } if (node.prev != null) { node.prev.next = node.next; } else { head = node.next; } if (node.next != null) { node.next.prev = node.prev; } else { tail = node.prev; } } public void displayForward() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public void displayBackward() { Node current = tail; while (current != null) { System.out.print(current.data + " "); current = current.prev; } System.out.println(); } } public class Main { public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList(); // Adding elements list.addFirst(10); list.addLast(20); Node node = list.head; list.insertAfter(node, 30); // Displaying elements System.out.print("Forward order: "); list.displayForward(); System.out.print("Backward order: "); list.displayBackward(); // Updating elements node = list.head; node.data = 40; // Removing elements node = list.head.next; list.remove(node); // Displaying elements after update and removal System.out.print("Forward order after update and removal: "); list.displayForward(); } }
In the above example, we have a Node class representing a single node in the doubly linked list. Each node has an integer data value and references to the previous and next nodes in the list.
The DoublyLinkedList class represents the doubly linked list itself. It maintains references to the head and tail nodes of the list.
The LinkedList class provides several constructors in Java to create LinkedList objects. Here are the commonly used constructors:
LinkedList(): Creates an empty LinkedList.
LinkedList(Collection<? extends E> c): Creates a LinkedList containing the elements of the specified collection in the order the collection's iterator returns them.
Example:
There are several methods to perform various operations on the linked list in Java. Here are some commonly used methods:
add(element): Adds the specified element to the end of the linked list.
add(index, element): Inserts the specified element at the specified position in the linked list.
get(index): Returns the element at the specified position in the linked list.
remove(index): Removes the element at the specified position in the linked list.
size(): Returns the number of elements in the linked list.
isEmpty(): Checks if the linked list is empty.
contains(element): Checks if the linked list contains the specified element.
clear(): Removes all elements from the linked list.
toArray(): Converts the linked list to an array.
Here is an example demonstrating various operations on a LinkedList:
Code:
import java.util.LinkedList; public class LinkedListOperations { public static void main(String[] args) { LinkedList<String> linkedList = new LinkedList<>(); // Adding elements linkedList.add("Apple"); linkedList.add("Banana"); linkedList.add("Orange"); System.out.println("Initial LinkedList: " + linkedList); // Updating elements linkedList.set(1, "Mango"); System.out.println("After updating: " + linkedList); // Removing elements linkedList.remove("Orange"); linkedList.removeFirst(); System.out.println("After removal: " + linkedList); // Iterating over elements System.out.print("Elements in the LinkedList: "); for (String element : linkedList) { System.out.print(element + " "); } System.out.println(); // Converting to an array Object[] array = linkedList.toArray(); System.out.print("Array representation: "); for (Object element : array) { System.out.print(element + " "); } System.out.println(); // Size of the LinkedList System.out.println("Size of the LinkedList: " + linkedList.size()); // Removing first and last elements linkedList.removeFirst(); linkedList.removeLast(); System.out.println("After removing first and last: " + linkedList); } }
The LinkedList class can also be used as a queue in Java by using the methods provided by the Queue interface. Here's an example of using a LinkedList as a queue:
import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); // Adding elements to the queue queue.add("Apple"); queue.add("Banana"); queue.add("Orange"); // Displaying the queue System.out.println("Queue: " + queue); // Removing elements from the queue String removedElement = queue.remove(); System.out.println("Removed element: " + removedElement); // Accessing the head of the queue String head = queue.peek(); System.out.println("Head of the queue: " + head); // Checking if the queue is empty boolean isEmpty = queue.isEmpty(); System.out.println("Is the queue empty? " + isEmpty); } }
In this example, we create a LinkedList and assign it to a Queue reference. We then use the queue-specific methods such as add, remove, peek, and isEmpty to perform queue operations.
When using LinkedList as a queue, elements are added to the end of the list (add method) and removed from the front of the list (remove method), following the FIFO (First-In-First-Out) order.
The LinkedList class can also be used as a double-ended queue (deque) in Java by utilizing the methods provided by the Deque interface. Here's an example of using a LinkedList as a deque:
import java.util.LinkedList; import java.util.Deque; public class DequeExample { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); // Adding elements to the front of the deque deque.addFirst("Apple"); deque.addFirst("Banana"); // Adding elements to the end of the deque deque.addLast("Orange"); deque.addLast("Mango"); // Displaying the deque System.out.println("Deque: " + deque); // Removing elements from the front and end of the deque String removedFirst = deque.removeFirst(); String removedLast = deque.removeLast(); System.out.println("Removed elements: " + removedFirst + ", " + removedLast); // Accessing the first and last elements of the deque String first = deque.peekFirst(); String last = deque.peekLast(); System.out.println("First element: " + first); System.out.println("Last element: " + last); } }
In this example, we create a LinkedList and assign it to a Deque reference. We then use the deque-specific methods such as addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast to perform deque operations.
ArrayList and LinkedList are manifestations of the Collection framework’s List interface. But, there are certain minute differences between the two terms.
Here’s a section on LinkedList vs. ArrayList Java to help you understand the key differences:
Here are the various advantages of LinkedList in Java:
Much like vectors in Java, LinkedList is featured with the ability to grow in size or shrink. It simply means that to accommodate the addition of new elements, the LinkedList can grow. Or, it can shrink itself in case any elements are removed.
Compared to arrays, LinkedList has more efficient memory use. Array keeps all the elements in the memory locations, even though some elements might not be useful. LinkedList, however, allocates memory selectively. Memory is allocated only to the elements in use and thus is a memory savior where the data set size is variable or unknown.
When compared to arrays, LinkedLists have more efficient sorting algorithms. Unlike arrays, swapping elements are unnecessary for LinkedLists, saving valuable time.
LinkedList offers efficient element manipulation in Java, which lets you comfortably add or subtract elements. It is a part of the Collection Framework and implements interfaces like Queue, List, and Deque. It has numerous advantages over an array, for being dynamic in size and having memory efficiency, but it also lacks an array’s capability of accessing random elements.
Considering the range of advantages, LinkedLists can be applicable in your day-to-day work. For instance, well-known software like Canva, MS-Word have an ‘undo’ feature executed by LinkedLists. Thus, it is an essential feature of the Java platform that you must master if you want to become a Java expert.
1. Is LinkedList in C the same as LinkedList in Java?
The implementation and syntax of LinkedList in C and Java are different. LinkedLists are not a complementary, built-in structure in C as in Java. In C, pointers and structures are used to implement LinkedLists, while in Java, it is implementable in a doubly linked list.
2. What are the various types of LinkedLists?
The various types of LinkedLists are:
Doubly linked list
Singly linked list
Circular linked list
Multiply linked list
3. What are some LinkedList applications?
LinkedLists can be used for implementing Queues, Stacks. It also helps the user fill in elements at the head or the list's tail.
Leave a Reply
Your email address will not be published. Required fields are marked *