Arrays are not very efficient with respect to memory usage. Memory is a crucial resource and all the applications keep asking for it. It has following drawbacks:

• Array is always stored in contiguous memory location (i.e one contiguous block of memory). This contiguous block of memory is always referred to by the address of the first memory block.
• When we create an array, the array will get certain chunk of memory allocated to it, depending on the size and type of the array. Since the memory allocation (one contiguous memory block) is done statically, there is a chance of memory wastage, if the array doesn't fill upto its capacity. Also, if we want to create a dynamic array when array elements exceed the array's initial size, we have to create a new array typically twice the size of original array, and then copy the original array into this new space.

Enter Linked lists.

Linked list represents sequence of nodes. Each node is a memory location which stores the data, and each node also points to the next memory location. Since every node contains address of next node, there is no requirement of these nodes to be adjacent or contiguous to each other.

In singly linked list, each node points to the next node in the linked list. In a doubly linked list, each node points to previous as well as next node in the linked list.

The ONLY way to access linked list elements is to get a reference to the head node, and traverse from head to desired node. As a result, the time taken to access the elements is proportional to the size of the list.

Unlike an array, a linked list does not provide constant time access to a particular "index" within the list.
This means that if you'd like to find the Kth element in the list, you will need to iterate through K elements.

The benefit of a linked list is that you can add and remove items from the beginning of the list in constant
time.

Advantages over Arrays

• Dynamic size
• Ease of insertion/deletion

Drawbacks:

• Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
• Extra memory space for a pointer is required with each element of the list.
• Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

Linked List Operations

Problem # 01 - Implementation

A node can be represented as a class in Java. It can have an integer field and a reference of Node class type to point to next node.

public class LinkedList {
    Node head;        // Head of the list

    class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }
}

Problem # 02 - Add a node at head

This is a 4 step process:

1. Create a new node
2. Check if the linked list is empty
3. If empty, set new node as head
4. Else, point from new node to the head, which would cease to be "head" now, and set the new node as head

public class LinkedList {
    Node head;        // Head of the list

    class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    void insertAtHead(int data) {
        Node node = new Node(data);            // 1. Create a new node
        if(this.head == null) {                // 2. Check if linked list is empty
            this.head = node;                  // 3. If YES, then set new node as head
        } else {
            node.next = this.head;             // 4. If NO, then point to head from new node, AND
            this.head = node;                  //    set new node as head
        }
    }
}