Posted inDSA

🔗 Singly Linked List in Java – A Complete Beginner’s Guide (Part 1)

Introduction, Need, Node Structure, Creating a Linked List & Traversal

When learning Data Structures, arrays are usually the first data structure introduced because they are simple and easy to understand. However, arrays have several limitations, especially when we need to insert or delete elements frequently.

To overcome these limitations, computer scientists developed a dynamic data structure called the Linked List.

A Linked List is one of the most important topics in Data Structures and Algorithms (DSA). It is frequently asked in university examinations, coding interviews, and competitive programming.

In this comprehensive guide (Part 1), you’ll learn:

  • 📌 What is a Linked List?
  • 📌 Why do we need a Linked List?
  • 📌 Limitations of Arrays
  • 📌 Types of Linked Lists
  • 📌 Memory Representation
  • 📌 What is a Node?
  • 📌 Creating a Singly Linked List in Java
  • 📌 Traversing a Linked List
  • 📌 Java Programs with Complete Explanation

Let’s begin!

📚 Table of Contents

  1. What is a Data Structure?
  2. What is a Linked List?
  3. Why Do We Need a Linked List?
  4. Limitations of Arrays
  5. Advantages of Linked Lists
  6. Types of Linked Lists
  7. What is a Singly Linked List?
  8. Components of a Node
  9. Memory Representation
  10. Creating a Node in Java
  11. Creating a Singly Linked List
  12. Traversing a Linked List
  13. Java Programs
  14. Time Complexity
  15. Advantages & Disadvantages
  16. Frequently Asked Questions
  17. Conclusion

💻 What is a Data Structure?

A Data Structure is a way of organizing and storing data so that it can be accessed and modified efficiently.

Some common data structures are:

  • 📦 Arrays
  • 🔗 Linked Lists
  • 📚 Stacks
  • 🚪 Queues
  • 🌳 Trees
  • 🕸 Graphs
  • 🗂 Hash Tables

Each data structure is designed to solve different types of problems.

🔗 What is a Linked List?

A Linked List is a linear data structure in which elements are stored as individual nodes.

Unlike arrays, the nodes are not stored in contiguous memory locations.

Instead, every node stores:

  • The actual data.
  • The address (reference) of the next node.

Think of it as a chain where each link points to the next link.

[Data | Next] → [Data | Next] → [Data | Next] → NULL

The last node points to NULL, indicating the end of the list.

🤔 Why Do We Need a Linked List?

Suppose we have an array:

10 20 30 40 50

Now we want to insert 25 after 20.

The new array becomes:

10 20 25 30 40 50

To make space for 25, we need to shift:

  • 30
  • 40
  • 50

This shifting becomes expensive when the array is large.

Similarly, deleting an element also requires shifting.

Linked Lists solve this problem because insertion and deletion only involve changing references.

❌ Limitations of Arrays

Although arrays are fast, they have several disadvantages.

1️⃣ Fixed Size

Once an array is created, its size cannot be changed.

int arr[] = new int[5];

If you later need 10 elements, you must create another array.

2️⃣ Expensive Insertions

Suppose the array is:

10 20 30 40 50

Insert 25

10 20 25 30 40 50

Many elements need to be shifted.

Time Complexity:

[
O(n)
]

3️⃣ Expensive Deletions

Delete 20

10 30 40 50

Again, all remaining elements shift.

4️⃣ Memory Wastage

If the array size is larger than required,

unused memory is wasted.

✅ Advantages of Linked Lists

Linked Lists overcome many limitations of arrays.

✔ Dynamic size

✔ Easy insertion

✔ Easy deletion

✔ No shifting of elements

✔ Better memory utilization

📚 Types of Linked Lists

There are mainly four types of linked lists.

1️⃣ Singly Linked List

10 → 20 → 30 → NULL

Each node points only to the next node.

2️⃣ Doubly Linked List

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Each node stores both previous and next references.

3️⃣ Circular Singly Linked List

10 → 20 → 30
↑           ↓
└───────────┘

The last node points back to the first node.

4️⃣ Circular Doubly Linked List

Each node stores:

  • Previous reference
  • Next reference

The first and last nodes are connected in both directions.

📌 What is a Singly Linked List?

A Singly Linked List is the simplest type of linked list.

Each node contains:

  • 📦 Data
  • 👉 Reference to the next node

Example

10 → 20 → 30 → 40 → NULL

Here,

  • 10 points to 20
  • 20 points to 30
  • 30 points to 40
  • 40 points to NULL

🧩 Components of a Node

Every node contains two parts.

📦 Data

Stores the actual information.

Example

10

👉 Next

Stores the address of the next node.

10 | Next

Complete Node

+------+------+
| Data | Next |
+------+------+

🧠 Memory Representation

Suppose we have

10 → 20 → 30

Memory may look like this.

Address      Data      Next

100          10        250

250          20        400

400          30        NULL

Notice something interesting.

The addresses

100

250

400

are completely random.

Unlike arrays,

Linked List nodes do not occupy contiguous memory.

🎯 What is Head?

The Head is a special reference that stores the address of the first node.

Head

↓

10 → 20 → 30 → NULL

Without Head,

we cannot access the linked list.

🏗 Creating a Node in Java

In Java,

every node is represented using a class.

class Node {

    int data;

    Node next;

    Node(int data){

        this.data = data;
        this.next = null;

    }

}

Explanation

int data;

Stores the value.

Node next;

Stores the reference of the next node.

Node(int data)

Constructor.

Whenever a new node is created,

it automatically stores the data.

this.next = null;

Initially,

there is no next node.

💻 Program 1 – Creating a Single Node

class Node{

    int data;

    Node next;

    Node(int data){

        this.data = data;
        next = null;

    }

}

public class LinkedListDemo{

    public static void main(String args[]){

        Node head = new Node(10);

        System.out.println(head.data);

    }

}

Output

10

💻 Program 2 – Creating Three Nodes

class Node{

    int data;
    Node next;

    Node(int data){

        this.data = data;
        next = null;

    }

}

public class LinkedListDemo{

    public static void main(String args[]){

        Node first = new Node(10);

        Node second = new Node(20);

        Node third = new Node(30);

        first.next = second;

        second.next = third;

        System.out.println(first.data);

        System.out.println(first.next.data);

        System.out.println(first.next.next.data);

    }

}

Output

10

20

30

🌉 Visual Representation

first

↓

+------+------+
|  10  |   ●──┼────►
+------+------+
             |
             ▼
       +------+------+
       |  20  |   ●──┼────►
       +------+------+
                    |
                    ▼
             +------+------+
             |  30  | NULL |
             +------+------+

🚶 Traversing a Linked List

Traversal means visiting every node exactly once.

The idea is simple.

Start from Head.

Move to the next node.

Repeat until NULL.

Algorithm

Step 1

Start from Head

↓

Step 2

Print Data

↓

Step 3

Move to Next Node

↓

Step 4

If NULL

Stop

Else Repeat

💻 Java Program – Traversing a Linked List

class Node{

    int data;
    Node next;

    Node(int data){

        this.data = data;
        next = null;

    }

}

public class LinkedListTraversal{

    public static void main(String args[]){

        Node head = new Node(10);

        head.next = new Node(20);

        head.next.next = new Node(30);

        head.next.next.next = new Node(40);

        Node temp = head;

        while(temp != null){

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

            temp = temp.next;

        }

    }

}

Output

10 20 30 40

🔍 Dry Run

Initially

Head

↓

10 → 20 → 30 → 40 → NULL

Iteration 1

temp = 10

Print 10

Move to 20

Iteration 2

temp = 20

Print 20

Move to 30

Iteration 3

temp = 30

Print 30

Move to 40

Iteration 4

temp = 40

Print 40

Move to NULL

Loop terminates.

📈 Time Complexity

Creating a Node

O(1)

Traversing

Every node is visited exactly once.

If there are n nodes,

Time Complexity

O(n)

💾 Space Complexity

Traversal uses only one temporary reference.

O(1)

✅ Advantages of Singly Linked List

✔ Dynamic size

✔ Easy insertion

✔ Easy deletion

✔ Efficient memory utilization

✔ No need for contiguous memory

❌ Disadvantages

❌ Extra memory required for storing references

❌ Cannot move backward

❌ Searching is slower than arrays

❌ Random access is not possible

📊 Arrays vs Singly Linked List

FeatureArraySingly Linked List
MemoryContiguousNon-contiguous
SizeFixedDynamic
InsertionSlowFast
DeletionSlowFast
Random AccessYesNo
Memory UsageMay waste memoryBetter utilization
TraversalEasySequential

❓ Frequently Asked Questions

Q1. What is a Linked List?

A Linked List is a linear data structure where each element (node) stores data and a reference to the next node.

Q2. Why is a Linked List better than an Array?

Because it supports dynamic memory allocation and efficient insertion and deletion without shifting elements.

Q3. What is a Node?

A node is the basic building block of a linked list. It contains the data and the reference to the next node.

Q4. What is the Head in a Linked List?

The head is a reference to the first node of the linked list. Without it, the list cannot be accessed.

Q5. Can we access the third node directly?

No. In a singly linked list, nodes must be accessed sequentially starting from the head.

Q6. What does NULL indicate?

NULL indicates the end of the linked list. The last node’s next reference points to NULL.

🎯 Key Takeaways

  • 🔗 A Linked List is a dynamic linear data structure.
  • 📦 Each node contains data and a reference to the next node.
  • 🧠 Nodes are stored in non-contiguous memory.
  • 📌 The head points to the first node.
  • 🚶 Traversal starts from the head and continues until NULL.
  • ⚡ Insertion and deletion are more efficient than in arrays.
  • 📈 Traversing a linked list takes O(n) time.
  • 💾 Traversal uses O(1) extra space.

🎉 Conclusion

A Singly Linked List is one of the most fundamental data structures in computer science. It addresses many of the limitations of arrays by allowing dynamic memory allocation and efficient insertion and deletion operations. Understanding how nodes are connected through references is essential before moving on to more advanced operations.

In this first part, you learned the core concepts of linked lists, including their structure, memory representation, node creation, and traversal. These concepts form the foundation for all linked list operations.

👉 In Part 2, we’ll build on this knowledge by implementing the most important operations on a singly linked list:

  • ➕ Insertion at the Beginning
  • ➕ Insertion at the End
  • ➕ Insertion at a Specific Position
  • 🧪 Dry runs and complete Java programs for each operation.

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *