This page looks best with JavaScript enabled

Implementing Linked List in Java: Part 1

 ·   ·  ☕ 8 min read

Introduction

In the last post, we have already seen that we can classify entire data structure into linear and non-linear data structure. Today we will see how we can implement one of the linear data structures in Java.

Initial plan was to implement Linked List in Python. But Python is so higher level that we’d be actually writing higher order data structure on top of high order data structure. What I try to say with that is Python already has those data structure implemented. Java is more close to C/C++, and gives a balance of features and flexibility. I’d have chosen C++ for this post, but I don’t want to deal with memory management and pointers for sake of this post.

Problem with Arrays

Here is one con of array that linked list fixes. See the image below:

Array using contagious chunk of memory
Array using contagious chunk of memory

Arrays always uses contagious chunk of memory. In the image above you can see that we have 3 rows of 11 units of memory. In first row, a program has allocated 7 units of memory. Then next 7 units of memory of is empty. Then again 7 unit of memory is occupied with another program.

Now at this point, you want to allocate 7 or less than 7 unit of memory, you can use the blank space there. But if you have to allocate more than 7 units of memory, you have to look for space somewhere else. In the image above, 11 units of memory is taken from the 3rd row.

This represents fragmentation. Meaning that memory is not used efficiently. That 7 units of memory might never be used.

This is worse when combined with the fact that you can’t change the size of the array after declaration. If you want more space, you have to allocate a different array. If you realized you need less memory than the allocated one, you can’t to much about it.

With linked list you are not force to use contagious chunk of memory. Overall use of linked list results in better utilization of memory.

Linked List

A LinkedList is a sequential access linear data structure in which every element is a separate object called a Node, which has two parts:

  • The data
  • The reference (or pointer)

Each element of a linked-list has an object (actual data) which can have multiple attributes, and a reference to a similar next node.

This post is not about what linked list is, but how to implement it. So let’s look at the implementation now.

Whether singly or doubly, Linked List is a collection of ListNodes.

ListNode

At the very first, we need a ListNode:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

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

    @Override
    public String toString() {
        return "ListNode(" +
                "data=" + data +
                '}';
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}

In a minimalistic singly ListNode, we’d have 2 fields. First is the data itself, and the pointer to the next node.

I have defined other methods for convinience, like the constructor, getters & setters for data and next pointer. I also have a toString method to represent node as a string.

LinkedList

Linked List is composed (as a chain) of these Nodes. By the naming convension, the first node is called head and the last node is called tail.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public class LinkedList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
    }
}

We right now have no methods implemented in our Linked List. We don’t even have a method to add a node to linked list. We’ll do this as we go.

Methods of a Linked List

Traverse a Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    public static void traverse(ListNode head) {
        // base condition
        if (head == null) {
            return;
        }

        // logic
        System.out.print(head.getData() + " -> ");

        // recursive call
        traverse(head.getNext());
    }

Explanation:

The above code has 3 section denoted by comments. These are the minimal things which needs to be in a recursive function.

Let’s do the dry run. Suppose we put node1 to this function. The function would check if it is null or not, if not, it will go ahead and print the data and the -> bit. Next it calls the same function will the next node in the list.

When the recursion reaches at the last node, the head == null would become true, and recursion would end there. Function calls would pop out of stack.

Runner code:

You can put the runner code inside the main method:

1
2
3
4

    public static void main(String[] args) {
        // ...
        traverse(node1);
    }

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 ->

Excuse the -> at the end, and let’s focus on the logic. Fixing that extra bit is not in the scope of this post.

Length of a Linked List

1
2
3
4
5
6
7
8

    public static int length(ListNode head) {
        int counter = 0;
        while (head != null) {
            counter++;
            head = head.getNext();
        }
        return counter;
    }

Explanation:

Function is passed a node, typically the first/head node. When the function executes, first we initialize a counter. Rest of the code is almost of the traverse code, just that we are incrementing counter variable on each iteration. At last we are returning the coutter.

Runner code:

You can put the runner code inside the main method:

1
2
3
4

    public static void main(String[] args) {
        // ...
        System.out.println(length(node1));
    }

Output:

5

Bonus:

The recursive version of length would look like this:

1
2
3

    public static int length(ListNode head) {
        return head == null ? 0 : 1 + length(head.getNext());
    }

Very briefly explaining, the function goes deep into recursion until the head == null becomes true. While returning back from recursion, it starts adding +1 to the result. The last result is returned after recursino is finished.

Both of the approach takes O(n) time. For O(1) time, you should consider maintaining a length variable and increment/decrement it at the time of adding/removing a node.

Check if a node is prerent

1
2
3
4
5
6
7

    public static boolean isPresentRecursive(ListNode head, int data) {
        if (head == null) {
            return false;
        }

        return head.getData() == data || isPresentRecursive(head.getNext(), data);
    }

Explanation

This is a recursive approach to check if a Linked List has a data node. The code is identical to that of traversing. The only exception is we return true if we find the data node.

The return statement can be split into multiple lines for understanding.

1
2
3
4
5

        if (head.getData() == data) {
            return true;
        }

        return isPresentRecursive(head.getNext(), data);

Runner code

You can put the runner code inside the main method:

1
2
3
4

    public static void main(String[] args) {
        // ...
        System.out.println(isPresentRecursive(node1, 3));
    }

Output

true

Insert at Kth position

This is the sole insertion method we are going to implement. This same method can be used to insert at head, as well as tail. For head, you’d pass K to be 0. For tail, you’d pass K to be length(head).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

    public static ListNode insertAtK(ListNode head, int data, int k) {
        if (head == null && k != 0) {
            return head;
        }

        if (k < 0 || k > length(head)) {
            return head;
        }

        ListNode newNode = new ListNode(data);

        if (k == 0) {
            newNode.setNext(head);
            head = newNode;
        } else {
            int count = 0;
            ListNode temp = head;

            while (count < k-1) {
                temp = temp.getNext();
                count++;
            }

            newNode.setNext(temp.getNext());
            temp.setNext(newNode);
        }
        return head;
    }

Explanation

At first we have some guard conditions. If head is null, it’s natural that new node should be at head. If that’s not the case, it returns the passed head node.

In next guard condition, we return head if K is beyond the length of the Linked List.

If that is not the case, we go ahead and create a ListNode with the given data. If k is set to be 0 meaning that node goes at the head. We set the new node’s next to the head, and then set the head value to new node because we also have to return the new head.

Runner code

You can put the runner code inside the main method:

1
2
3
4

    public static void main(String[] args) {
        // ...
        System.out.println(isPresentRecursive(node1, 3));
    }

Output

true

Conclusion

In this post I have implemented some most common operations on a Linked List. In upcoming posts, we’d see some more operations on the same data structures. We’ll also come up with data structures problems to solve and will discuss the approach.

Share on
Santosh Kumar
WRITTEN BY
Santosh Kumar
Santosh is a Software Developer currently working with NuNet as a Full Stack Developer.