Linked List Implementation in Java with Operations

A Linked List is a linear data structure where each element (node) contains two parts:

1. Data: Stores the actual data.
2. Pointer: Points to the next node in the list.

In contrast to arrays, linked lists allow dynamic memory allocation, meaning they can grow or shrink during runtime. They are a great alternative when frequent insertions and deletions are needed.

Here's a step-by-step implementation of a Singly Linked List with basic operations.

Node Class

Each node of the linked list will have two properties: data and next.

class Node {

int data;

Node next;

// Constructor

public Node(int data) {

this.data = data;

this.next = null;

}

}

LinkedList Class

The LinkedList class manages the list and provides methods for various operations such as insertion, deletion, and traversal.

Linked List Operations

• Insert at the Beginning
• Insert at the End
• Insert at a Specific Position
• Delete a Node by Key
• Delete by Position
• Search for an Element
• Display the Linked List

class LinkedList {

Node head; // head of the list

// 1. Insert at the Beginning

public void insertAtBeginning(int data) {

Node newNode = new Node(data);

newNode.next = head;

head = newNode;

}

// 2. Insert at the End

public void insertAtEnd(int data) {

Node newNode = new Node(data);

if (head == null) {

head = newNode;

return;

}

Node last = head;

while (last.next != null) {

last = last.next;

}

last.next = newNode;

}

// 3. Insert at a Specific Position

public void insertAtPosition(int data, int position) {

Node newNode = new Node(data);

if (position == 0) {

insertAtBeginning(data);

return;

}

Node temp = head;

for (int i = 1; i < position; i++) {

if (temp == null) {

throw new IndexOutOfBoundsException("Position out of range");

}

temp = temp.next;

}

newNode.next = temp.next;

temp.next = newNode;

}

// 4. Delete a Node by Key

public void deleteByKey(int key) {

Node temp = head, prev = null;

// If the head node itself holds the key

if (temp != null && temp.data == key) {

head = temp.next; // Changed head

return;

}

// Search for the key to be deleted

while (temp != null && temp.data != key) {

prev = temp;

temp = temp.next;

}

// If key was not present in the list

if (temp == null) return;

// Unlink the node from the linked list

prev.next = temp.next;

}

// 5. Delete a Node by Position

public void deleteByPosition(int position) {

if (head == null) return;

Node temp = head;

// If the head needs to be removed

if (position == 0) {

head = temp.next;

return;

}

// Find previous node of the node to be deleted

for (int i = 0; temp != null && i < position - 1; i++) {

temp = temp.next;

}

// If position is more than the number of nodes

if (temp == null || temp.next == null) return;

// Node temp.next is the node to be deleted

temp.next = temp.next.next;

}

// 6. Search for an Element

public boolean search(int key) {

Node temp = head;

while (temp != null) {

if (temp.data == key) {

return true;

}

temp = temp.next;

}

return false;

}

// 7. Display the Linked List

public void display() {

Node temp = head;

if (head == null) {

System.out.println("The list is empty");

return;

}

while (temp != null) {

System.out.print(temp.data + " -> ");

temp = temp.next;

}

System.out.println("null");

}

}

Explanation of Operations:

1. Insert at the Beginning:

   • This operation takes constant time O(1). The new node is made the head of the list and points to the previous head.

2. Insert at the End:

   • This operation takes O(n) time since you have to traverse the entire list to find the last node.

3. Insert at a Specific Position:

   • Traverses the list to the desired position and inserts the node. Time complexity depends on the position and can be O(1) for the head or O(n) for the end.

4. Delete a Node by Key:

   • Searches for the node containing the key and unlinks it from the list. This operation takes O(n) time because you might have to traverse the entire list.

5. Delete by Position:

   • This is similar to deleting by key, but instead of searching for the value, you remove the node at a specific position. The complexity is also O(n).

6. Search for an Element:

   • Traverses the list and returns true if the element is found. Time complexity is O(n).

7. Display the Linked List:

• Prints the elements in the list. Time complexity is O(n).

Example Usage:

    public class Main {

public static void main(String[] args) {

LinkedList list = new LinkedList();

// Insert elements

list.insertAtBeginning(10);

list.insertAtEnd(20);

list.insertAtEnd(30);

list.insertAtPosition(15, 1);

// Display the list

list.display(); // Output: 10 -> 15 -> 20 -> 30 -> null

// Delete a node by key

list.deleteByKey(20);

list.display(); // Output: 10 -> 15 -> 30 -> null

// Search for an element

System.out.println(list.search(15)); // Output: true

// Delete a node by position

list.deleteByPosition(1);

list.display(); // Output: 10 -> 30 -> null

}

}

Time Complexity Overview:

• Insert at Beginning: O(1)
• Insert at End: O(n)
• Insert at Specific Position: O(n)
• Delete by Key: O(n)
• Delete by Position: O(n)
• Search: O(n)
• Display: O(n)

This implementation handles the basic operations of a singly linked list. You can also extend this to doubly linked lists by adding a prev pointer to each node for bidirectional traversal.

#LinkedList #JavaProgramming #DataStructures #CodingInterview #JavaDeveloper #SinglyLinkedList #Algorithm #LearnDSA #TechTutorial #JavaCoding