What is the difference between a linked list and an array?

An array stores elements in contiguous memory cells, providing fast access by index (O(1)). Its size is fixed upon creation.

A linked list stores elements in nodes, each containing data and a reference to the next node. Accessing an element by index requires traversal (O(n)). Its size is dynamic.

Main differences:

Attribute	Array	Linked List
Placement	Contiguous memory cells	Nodes with references
Access by index	Fast (O(1))	Slow (O(n))
Insertion/Deletion	Slow (O(n))	Fast (O(1)) at beginning/end of list
Size	Fixed	Dynamic

Example of adding an element to an array requires creating a new array and copying elements:

// Adding an element to an array
int[] originalArray = {1, 2, 3};
int newValue = 4;
int[] newArray = new int[originalArray.length + 1];
System.arraycopy(originalArray, 0, newArray, 0, originalArray.length);
newArray[originalArray.length] = newValue;

Example of adding an element to a linked list (at the end):

// Adding an element to a linked list
class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}
// ...
Node head = new Node(1);
Node second = new Node(2);
head.next = second;
Node tail = second; // assuming second is the last element
Node newNode = new Node(3);
tail.next = newNode;
tail = newNode; // update tail