Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and efficient insertion and deletion operations. In Java, linked lists are commonly used for various applications due to their flexibility and versatility. In this blog post, we will explore linked lists in Java in detail, covering their definition, types, operations, and implementation.

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: the data, which holds the value of the element, and a reference (or link) to the next node in the sequence. Unlike arrays, which have fixed sizes, linked lists can dynamically grow and shrink as elements are added or removed.

Key Concepts

• Node: The fundamental building block of a linked list. Each node consists of:
  • Data: The actual information you store (e.g., integer, string).
  • Next pointer: References the next node in the list.
  • Previous pointer (for doubly-linked lists): References the preceding node, enabling bidirectional traversal.
• Head: The starting point of the list, pointing to the first node.
• Tail: In singly-linked lists, points to the last node. In doubly-linked lists, points to the last node for forward traversal and the first node for backward traversal.

Types of Linked Lists

1. Singly Linked List

In a singly linked list, each node has only one link, which points to the next node in the sequence. Traversal in a singly linked list can only be done in one direction, typically from the head (start) to the tail (end) of the list. Singly-linked lists are relatively simple and efficient in terms of memory usage.

2. Doubly Linked List

In a doubly linked list, each node has two links: one points to the next node, and the other points to the previous node. This bidirectional linking allows traversal in both forward and backward directions. Doubly linked lists typically require more memory per node due to the additional reference for the previous node.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circular structure. Circular linked lists can be either singly or doubly linked and are useful in scenarios where continuous looping is required.

How to represent a LinkedList in Java ?

Now we know that, A linked list is a data structure used for storing a collection of elements, objects, or nodes, possessing the following properties:

1. It consists of a sequence of nodes.
2. Each node contains data and a reference to the next node.
3. The first node is called the head node.
4. The last node contains data and points to null.

| data | next | ===> | data | next | ===> | data | next | ===> null

Implementation Of a Node in a linked list

Generic Type Implementation

public class ListNode<T> {
    private T data;
    private ListNode<T> next;
}

In the generic type implementation, the class ListNode<T> represents a node in a linked list that can hold data of any type. The line public class ListNode<T> declares a generic class ListNode with a placeholder type T, allowing flexibility for storing different data types. The private member variable data of type T holds the actual data stored in the node, while the next member variable is a reference to the next node in the linked list, indicated by ListNode<T> next. This design enables the creation of linked lists capable of storing elements of various types, offering versatility and reusability.

Integer Type Implementation

public class ListNode {
    private int data;
    private ListNode next;
}

In contrast to the generic type, the integer type implementation, represented by the class ListNode, is tailored specifically for storing integer data. The class ListNode does not use generics and defines a private member variable data of type int to hold integer values within each node. Similarly, the next member variable is a reference to the next node in the linked list, indicated by ListNode next. This implementation is more specialized and optimized for scenarios where the linked list exclusively stores integer values, potentially offering improved efficiency due to reduced overhead from generics.

Node Diagram

| data | next |===>

This node diagram depicts the structure of each node in the linked list. Each node consists of two components: data, representing the value stored in the node, and next, a pointer/reference to the next node in the sequence. The notation | data | next |===> illustrates this structure, where data holds the value of the node, and next points to the subsequent node in the linked list. The arrow (===>) signifies the connection between nodes, indicating the direction of traversal from one node to another within the linked list.

Representation of Linked List

head ===> |10| ===> |8| ===> |9| ===> |11| ===> null

The representation of the linked list illustrates a sequence of nodes starting from the head node. Each node contains its respective data value, with arrows (===>) indicating the connections between nodes. The notation head ===> |10| ===> |8| ===> |9| ===> |11| ===> null shows the linked list structure, where head denotes the starting point of the list. The data values (10, 8, 9, 11) are enclosed within nodes, and null signifies the end of the linked list. This representation visually demonstrates the organization and connectivity of nodes within the linked list data structure.

Code Implementation

public class LinkedList
{

  private ListNode head; // head node to hold the list
  
  // It contains a static inner class ListNode
  private static class ListNode
  {
     private int data;
     private ListNode next;

     public ListNode(int data) {
          this.data = data;
          this.next = null;
     }
  }

  public static void main(String[] args)
  {
   
  }
}

The above code snippet outlines the structure of a linked list in Java. The LinkedList class serves as the main container for the linked list, featuring a private member variable head that points to the first node. Within this class, there exists a static inner class named ListNode, which defines the blueprint for individual nodes. Each ListNode comprises an integer data field and a reference to the next node. The constructor of ListNode initializes a node with the given data and sets the next reference to null by default. The main method, though currently empty, signifies the program’s entry point where execution begins. It provides a foundational structure for implementing linked lists, enabling the creation and manipulation of dynamic data structures in Java programs.

Common Operations on Linked Lists

We will see each operation in much detail in the next article, where we will discuss Singly Linked Lists in more detail. Right now, let’s see a brief overview of each operation:

1. Insertion

Insertion in a linked list involves adding a new node at a specified position or at the end of the list. Depending on the type of linked list, insertion can be performed efficiently by updating the references of adjacent nodes.

2. Deletion

Deletion involves removing a node from the linked list. Similar to insertion, deletion operations need to update the references of adjacent nodes to maintain the integrity of the list structure.

3. Traversal

Traversal refers to visiting each node in the linked list sequentially. Traversal is essential for accessing and processing the elements stored in the list.

4. Searching

Searching involves finding a specific element within the linked list. Linear search is commonly used for searching in linked lists, where each node is checked sequentially until the desired element is found.

5. Reversing

Reversing a linked list means changing the direction of pointers to create a new list with elements in the opposite order. Reversing can be done iteratively or recursively and is useful in various algorithms and problem-solving scenarios.

Conclusion

Linked lists are powerful data structures in Java that offer dynamic memory allocation and efficient operations for managing collections of elements. Understanding the types of linked lists, their operations, and their implementation in Java is essential for building robust applications and solving complex problems efficiently. Whether you’re a beginner or an experienced Java developer, mastering linked lists will enhance your programming skills and enable you to tackle a wide range of programming challenges effectively. Happy coding!