📝

Java Linked List Implementation Guide

May 12, 2025

Implementing a Linked List in Java using Class

Introduction

  • Linked List: A linear data structure similar to arrays.
  • Differences from Arrays:
    • Elements in a linked list are not stored at contiguous memory locations.
    • Elements are linked using pointers.

Basic Structure

  • Node Class:

    • Contains two fields: int data and Node next.
    • Constructor: Initializes data and sets next to null.

  • LinkedList Class:

    • Contains Node head to represent the start of the list.

Insertion

  • Insertion at End:
    • Traverse to the end of the list and add the new node.
    • If the list is empty, the new node becomes the head.

Code Example

class LinkedList { Node head; static class Node { int data; Node next; Node(int d) { data = d; } } static LinkedList insert(LinkedList list, int data) { Node new_node = new Node(data); if (list.head == null) { list.head = new_node; } else { Node last = list.head; while (last.next != null) { last = last.next; } last.next = new_node; } return list; } }

Traversal

  • Method: Iterate from head to the last node and print each node's data.

Code Example

static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); while (currNode != null) { System.out.print(currNode.data + " "); currNode = currNode.next; } System.out.println(); }

Deletion by Key

  • Objective: Remove the first occurrence of a node with given data.

Cases

  1. Key at Head:

    • Update head to head.next and free memory of the old head.

  2. Key in Middle/End:

    • Find the previous node and remove the current node by updating prev.next.

  3. Key Not Found: No deletion performed.

Code Example

static LinkedList deleteByKey(LinkedList list, int key) { Node currNode = list.head, prev = null; if (currNode != null && currNode.data == key) { list.head = currNode.next; return list; } while (currNode != null && currNode.data != key) { prev = currNode; currNode = currNode.next; } if (currNode != null) { prev.next = currNode.next; } return list; }

Deletion by Position

  • Objective: Remove node at a specified index.

Cases

  1. Index 0:

    • Update head to head.next and free memory of the old head.

  2. Index within Bounds:

    • Keep track of the previous node and unlink the node at the given index.

  3. Index Out of Bounds: No deletion performed.

Code Example

static LinkedList deleteAtPosition(LinkedList list, int index) { Node currNode = list.head, prev = null; if (index == 0 && currNode != null) { list.head = currNode.next; return list; } int counter = 0; while (currNode != null) { if (counter == index) { prev.next = currNode.next; break; } else { prev = currNode; currNode = currNode.next; counter++; } } return list; }

Conclusion

The implementation of a linked list in Java involves creating a Node class for individual elements and a LinkedList class to manage the nodes. Key operations include insertion, traversal, and deletion by key or position, each requiring careful manipulation of pointers to ensure the integrity of the list.

View note sourcehttps://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/