Linked Lists for beginners with examples in Java

Table of contents

• What is a Linked List
• What is a Node
• Creating a Linked List in Java
• Why to use Linked List over Arrays
• Pros of Arrays over Linked List
• Differences between Array and Linked List
• Comparison of time and space complexities of Array and Linked List
• Memory allocation in Linked List
• Memory Allocation in Arrays
• Creating a custom Linked List in Java
• Functions/Methods in Linked List
• Conclusion

Linked List is a data structure used to store data where each element has it's own value and the location of the next element.

If you don't understand the above definition, let me just further simplify the things. For some time, consider LinkedList as an array.

This brick-like structure presented here is called a Node. It is the most important thing to understand in LinkedList. Nodes are the building blocks of Linked Lists.

What is a Node?

Node is a data structure that stores a value and the address of the next element. We join two nodes using links (arrows in diagram). On repetition of this process, we get a Linked List.

Now, instead of index, we use the same address held by nodes to get the element. This is where Linked Lists start getting different than arrays.

Creating a Linked List in Java

Don't worry this code is explained in the later sections!

public class LinkedList{

Node head;
Node tail;
int size;

public LL() {
	this.size = 0;
}

private class Node {

        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

Why to use Linked List over Arrays?

Linked Lists are relatively very efficient in terms of memory allocation.

For example, if we talk about Java, for creating a new array of size 5, we write the following code,

int[] arr = new int[5];

The 5 used in int[5] specifies the size of array. Hence if we want want to insert 6th element, we'll need to alter the whole structure of array.

These are the series of steps to change the size of an array

• Create a new array of required size
• Copy the contents of old array into new one

In code, it looks like this,

int[] arr = new int[5];
int[] arr2 = new int[10];
for (int i = 0; i < arr.length; i++) {
	arr2[i]= arr[i];
}

Now imagine if array is of larger size. It will take a lot of space and time to copy the whole chunk of data to a new place.

Since there is no such concept of size in Linked Lists (theoretically), this problem is solved.

Adding extra element in a linked list looks like this

See how easy it was? We just updated tail of the Linked List and the work was done.

Time Complexity of changing size of array is linear while time complexity in case of Linked List is constant. See why Linked List is better?

Pros of Arrays over Linked List

• Organised
• Takes less space
• Easy to search data

Differences between Array and Linked List

Comparison of time and space complexities of Array and Linked List

Now let's talk about some internal implementation of Linked List and how it it coded. I'll be writing the code in Java but I'll explain every line of code so language shouldn't be a barrier.

You should be familiar with basic Object Oriented Programming concepts (Classes and Objects mainly) to understand the code.

Memory allocation in Linked List

To understand this thing, we need to understand what happens when we declare and initialise a variable.‌

int n = 6;

‌What this above code does is that it creates a new variable of integer type then assigns the value '6' to it.

So, when we initialise the 'int type variable', 4 bytes of space( int type values hold 4 bytes of space)  is generated in the RAM where the value will be stored and 6 is stored in that 4 bytes of memory.‌

You can understand the above thing by this example. Suppose you went to a grocery store and you chose certain items, you gave it to the store owner. This is similar to initialisation and declaration of the variable. Now the person will take out a carry bag of suitable size. This is simlar to allocation of 4 bytes of space by the computer. Then the shopkeeper puts the items into the bag, This is simlar to the system using the 4 bytes of space to store the value of '6'.

So, when any element is stored in memory, it is given a memory allocation address. Remember I said that every node in a Linked list stores address of the next element? I was referring to this memory allocation address. So actually, there is no link, it is the address which is used to traverse a Linked List.

This how a Linked List would actually looks like internally‌

‌

Memory Allocation in Arrays

This topic is important to understand so that you get an idea of internal difference between Arrays and LinkedList

When an array is created, the CPU allocates only a fixed size of memory. How does the CPU know how much memory to allocate? Let's understand this thing now.

int[] arr = new int[5];

• The first word in this code is int[]. This represents what is the datatype of each element of the array. This will be 4 bytes in case of int.
• The last word has a 5 in it. This shows how many elements will be present in the array.
• Now the CPU will perform a basic mathematical calculation. It'll multiply no of elements of array with memory requirement of each element.
• In this way, CPU knows how much memory to spare for the array.

How do we access each element of an array?

• CPU has the address of first element of the array.
• Then we add the 4 bytes of memory (or any other size, depending on the datatype) to the address of the previous element.
• So, address of an element = address of previous element + size of each element
• Using these properties we can derive a formula to access element at any index

So the CPU uses this derived address to access the element. Linked List has to store the address, but in case of array, CPU derives it.

This formula is the same reason, only same type of data can be stored in array. Because, if different type of data is stored, the size of element part won't remain constant.

I think now you get a crystal clear idea of difference between Arrays and Linked List.

So this was all about memory allocation in Linked List in arrays. Now let's start with some coding.

Creating a custom Linked List in Java

Now we know, what are the contents of a Linked List. Using these we can create a Linked List. Although languages provide us with Linked Lists, we will create a custom Linked List to get a better understanding of what's happening internally. Here you need to have understanding of classes and objects to understand the code.

Linked List has the following property‌

• Node which further has 2 properties
  1. Value
  2. Address of next element
• Head (this will point towards the first element of the list
• Tail (this will poitn towards the last element of the list
• Size

So we can create a pubic class Linked_List which will further have a nested class Node(can be public/private, doesn't matter atleast for personal use). This Node will have a value and a Node next.‌

public class Linked_List {
	Node head;
    Node tail;
    int size;
    public class Node{
        int value;
//            ↑___This is value any Node will store
        Node next;
//            ↑___This will store the address of next node
    }
}

‌This is how Linked List is created.  Then, we start on writing functions and constructors. Let's first write constructors for creating a new node. There will be two constructors and I should explain it after the code.‌

public Node(int value, Node next) {
// first constructor
            this.value = value;
            this.next = next;
        }

        public Node(int value) {
// second constructor
            this.value = value;
        }

We created two constructors because there can be two conditions.

• User inputs both value contained by the Node and address of the next node (pretty straight forward)
• User inputs only value contained by the Node (this property will be used later in some functions)

Functions/Methods in Linked List

Now we'll be writing functions to perform various operations

1.Insertion of element at the start

• To do this, what we can do is that we create a new Node with the required value. Now, this Node will point to the first element of the Linked List.
• Now we will update the head to point towards this newly created Node.

In diagram, this looks like‌

‌

Now, let's code this thing down‌

public void insertfirst(int val) {
	
    // creation of new node
        Node node = new Node(val);
        
	// New node points towards head element
		node.next = head;
        
    // Head points towards the newly created element    
        head = node;

        if (tail == null) {
    // This is a check to see if the list is empty
    // If yes, tail should be same as head
            tail = head;
            
        }

        size++;
    }

2.Insertion of element at the end

• To do this, we create a new node.
• Now, last element of the Linked List should be pointing towards this newly created node.
• Then we update the tail variable to point towards this newly created Linked List

This is how it would look in a diagram,

Now, let's code this down

public void insertlast(int value){

// Creation of new Node to be added
        Node node = new Node(value);
        
// Last element of the element pointing towards the newly created node        
        tail.next = node;
        
// New node becomes the lsat element of the List
        tail = node;
        
        
// A check to see if the list was empty, if yes then head will be same as tail
        if (head == null){
            head = tail;
        }

// Tail should point towards null
        tail.next = null;
        
// Incremeting the size of array after adding the new element
        size++;
    }

3.Deletion of element from the list

• To do this, we will create a temporary node that is same as head.
• Then, we will traverse the List till the element just before the element to be deleted.
• When we reach the required element, we skip the required element by using the next function 2 times.

In diagram, it looks like this

Now let's code this thing down

public void delete(int index){

// Creation of new temporary node pointing towards head
        Node temp = head;
        
// To check if first element is to be removed
        if (index == 0){

// Head will point towards the next node
            head = head.next;
        }
        
// Traversing the array to reach to the required node        
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        
// Skipping the required node
        temp.next = temp.next.next;

// Decrementing the size since an element is reduced
		size--;
    }

4. Displaying the Linked List

• To solve this, we create a temporary node, and traverse the whole list and print value of each node.
• This could be done directly with traversing the List using the head pointer, but we don't do this because this would change the whole structure.

I don't think there is any need for a diagram in this case so let's jump on to the code!

public void display() {

// Creation of temp node that starts from head
        Node temp = head;
        
// Traversing the list elements, we run the loop till null as next //element of the tail will be null, so loop break when it reaches null
        
        while (temp != null) {
        
// We print the value only of each element since we don't need to show // address of the next element to the user
		System.out.print(temp.value + ",");
        
// Going to the next element for traversal
        temp = temp.next;
        
        // loop ends
        }
        
// Printing null so that user sees that there is nothing after tail

		System.out.print("null")
}

Conclusion

This is all about the basics you need to know about Linked List. I hope I was able to make things a bit more clear for you.