How to distinguish a linked list from a non-linked list and what are their main differences?

A linked list is a data structure where each element (node) contains a reference to the next element (and, in the case of a doubly linked list, to the previous one). An unlinked list is simply a collection of elements without links between them, such as an array.

Main differences:

• Linked list:

  • Elements are connected by pointers.
  • Convenient for dynamic addition and removal of elements without shifting.
  • Access to elements is sequential, with no direct access by index.

• Unlinked list:

  • Elements are not connected to each other.
  • Usually implemented as an array or collection.
  • Fast access by index, but insertion/deletion operations can be costly due to shifting elements.

Example of a 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;
        }
    }
}