What are the distinctive features of a linked list and how does it differ from other data structures?

A linked list is a data structure consisting of nodes, where each node contains data and a reference (or references) to the next (and/or previous) node. The main differences between a linked list and other data structures, such as arrays:

• Dynamic memory allocation: elements of a linked list can be located in different places in memory, unlike arrays where elements are contiguous.
• Fast insertion and deletion: inserting and deleting elements in the middle of the list is performed in O(1) if there is a reference to the desired node, without shifting other elements, whereas in an array this requires shifting.
• No direct access: to access an element by index, you need to traverse the list from the beginning, which takes O(n), unlike arrays with O(1) access.

Example of a singly linked list in Java:

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

class LinkedList {
    Node head;

    void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
}