Data Structure: Understand LinkedList

Photo by Caspar Camille Rubin on Unsplash

Introduction

So in this post, we are going to discuss the LinkedList Data Structure. So the common things first:

LinkedList is a Linear data Structure, which stores the values in the memory addresses which are not sequential.

LinkedList is just a collection of Nodes, and these nodes are connected, and the head node has the address of the first node and the last node is known as the tail node.

A node is a combination of two fields data and address.

In LinkedList for every operation head will be given to us, most operations will start from the head because we can not access any random node directly we should start from the head node. (head means simply the first node)

The node we create as an inner class removes manipulation from other places.

public class LinkedList {
    
    Node head;
    
    class Node {
        int data;
        Node next;
        
        Node(int d) {
            this.data = d;
            this.next = null;
        }
    }   
}

This is a very simple implementation of LinkedList.

public LinkedList insert(LinkedList list, int data) {
    Node n = new Node(data);

    if (list.head == null) {
        head = n;
    } else {
        Node last = list.head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = n;
    }
    return list;
}

public void printList(LinkedList ll) {

    Node head = ll.head;
    while (head != null) {
        System.out.println(head.data);
        head = head.next;
    }
}

public static void main(String[] args) {
    LinkedList ll = new LinkedList();

    ll.insert(ll, 10);
    ll.insert(ll, 20);
    ll.insert(ll, 30);
    ll.insert(ll, 40);

    ll.printList(ll);
}

Methods to add nodes and print LinkedList.

Similar way we can do different operations and we can solve different problems related to Linked Lists.

The main concept that we should remember is for the LinkedList to always keep track of pointers. We can create multiple pointers for accessing the next and previous nodes as well.

Rest we will solve more problems on LinkedList for building concepts. I will keep on adding problems to the list.

1. Reverse a LinkedList using an iterative and recursive approach.
2. Program to detect a loop on LinkedList.
3. Remove duplicates in sorted and unsorted LinkedList.
4. Add two numbers represented by LinkedList.
5. Check if a LinkedList is a circular LinkedList.

Continue Reading

Important LinkedList Questions

Thanks for reading!!