Understanding data structures is an important skill in any programmer's toolkit. Not to mention that the majority of coding interviews frequently include linked list questions.
Your capacity to tackle confusing situations, think holistically, and spot patterns in code is demonstrated by these abilities. Data structures apply algorithms to your code and organise your data. The Java platform offers high-performance implementations of numerous data structures and is one of the programming languages used for conversational applications that is tested the most.
Today we're going to look at one of JavaScript's most important data structures, the Linked List class. We'll see how it works and learn how to use it to store and manipulate data.
What is a linked list?
A linked list in Java is a linear data structure that stores elements in contiguous locations. A linked list's elements are connected together by addresses and pointers, and each element has two components: a data part and an address part. The data part is the element's value, and the address part consists of pointers and addresses used to link the elements.
Working with a linked list in Java is as follows:
• A linked list in Java is a dynamic data structure that grows in size when elements are added and shrinks when elements are removed from the list.
• Elements in a linked list are stored in containers.
• The list contains a link to the first container.
• All containers have a reference to the next container in the list.
• Whenever you add an element to a list using the add() operation, a new container is created, and that container is linked to the other containers in the list.
Different types of linked lists are required in order to access and alter our elements appropriately because a linked list is a linear data structure and does not store elements in contiguous locations.
Three alternative sorts of linked lists, each with a particular function for our code organisation, exist.
1. Singularly linked list (one-way)
A single linked list is unidirectional, meaning it can only be traversed in one direction from the start to the last node (end).
2. Doubly linked list (bidirectional)
Doubly linked lists (DLLs) are extensions of basic linked lists but contain a pointer to the next node and the previous node. The list may now be traversed in both ways thanks to this. Three fundamental members make up a DLL node:
• Data
• A pointer to the next node
• A pointer to the previous node
3. Circular linked list
The first entry in a circularly linked list points to the last member, while the last element points to the first element. A circular linked list can be created from a single linked list or a doubly linked list. A circular linked list's most crucial actions are:
insert: insert elements at the beginning of the list
display: list display
delete: delete elements from the beginning of the list
List of linked classes
As mentioned above, the Singly Linked list contains nodes linked together as a string. We would want a pointer that tracks the list's initial entry in order to retrieve this string.
We don't need to keep track of the storage locations as long as we know information about the first element in the list.
A head node, or pointer to the list's first entry, can be found in a singly linked list. We can use this master node to traverse the list at any time.
Below is the basic structure of the Singly Linked List class:
public class SinglyLinkedList {
//Internal node class for SLL
public class Node{
public T data; //Data to store (can be int, string, object, etc.)
public Node nextNode; //Pointer to the next node in the list
}
public Node headNode; //head node of the linked list
public int size; //list size
Various operations can be performed on elements in a linked list in Java. Those operations are:
Insert elements into a list
Elements can be inserted into a given list at the beginning, at the end, or at a specified location in the list.
Insert to the beginning of the List
• A new node is created to store the data.
• The next pointer to the new node will point to the top of the list.
• The new node then becomes the head of the list.
Insert at the end of the list
• A new node is created to store the data.
• To get to the list's final node, the full list must be visited.
• The new list node becomes the last node by creating a new last node pointer that points to it.
• paste in the list's designated spot.
• To store the data, a new node is made.
• To get to the node immediately before the node at the designated place in the list, the list is traversed.
• The new list node is one of the nodes in the list because other pointers point to it.
Remove elements from the list.
Elements can be removed from a given list from the beginning, end, or specified position in the list.
Delete from the beginning of the list
The list head is set to point to the second list node.
Delete from the end of the list
• The entire list is traversed to reach the penultimate node of the list
• The second-to-last node's next pointer is set to point to null
Delete from the specified position in the list
• The list is traversed to reach the node that is just before deleting the node at the specified position in the list.
• Other pointers are changed to remove the node at the specified list position.
Things to consider before using a linked list
Linked lists function similarly to dynamic arrays. This implies that when creating, we don't need to mention the size. Adding and removing items automatically causes its size to change. A double linked list data structure is also used to implement the Linked List class.
The list's elements all make reference to the ones that come before and after them. The element's next reference returns null if it is the last in the list.
When: You only use the list by traversing it instead of accessing random elements, this architecture makes Linked List helpful.
From the start or midway of the list, you frequently need to add and remove items.
The following factors additionally make LinkedList less advantageous than ArrayList, the typical default list implementation in Java, as a result of this design:
• Due to the storage requirements of its item references—one for the previous item and one for the next item—it consumes more memory than an ArrayList.
• Because linked lists need sequential access by nature, elements in a linked list must be read from the beginning (or end) in order.
Conclusion
There is much more that you can learn and practice to master linked lists in Java. In this blog, we have discussed linked lists in Java. We have its types, some examples, and how to use it.
Advanced Certification in Applied Data Science, Machine Learning & IoT By E&ICT Academy, IIT Guwahati
9 months
Certification in Data Science and Machine Learning With Python By The
IoT Academy Noida
180 Hrs
