Difference Between Array and Linked List

 

Arrays and linked lists are both fundamental data structures used to store collections of elements, but they differ significantly in their structure, operations, and use cases. Here is the key Difference Between Array and Linked List:

1. Definition

Array

• A collection of elements stored in contiguous memory locations.
• Each element is accessed by its index.

Linked List

• A collection of elements called nodes, where each node contains the element and a reference (or pointer) to the next node in the sequence.
• Nodes are not stored in contiguous memory locations.

2. Structure

Array

• Fixed size (static array) or can be resized dynamically (dynamic array).
• Elements are stored sequentially in memory.

Linked List

• Consists of nodes that are linked together using pointers.
• Can grow or shrink dynamically as elements are added or removed.
• Types: singly linked list (each node points to the next node), doubly linked list (each node points to both the next and the previous nodes), circular linked list (the last node points back to the first node).

3. Memory Allocation

Array

• Requires contiguous memory allocation.
• Efficient use of memory if the size is known in advance.

Linked List

• Does not require contiguous memory allocation.
• More flexible in memory usage as it grows and shrinks dynamically.

4. Access Time

Array

• Constant time \(O(1)\) access to elements using their index.
• Efficient for random access.

Linked List

• Linear time \(O(n)\) access to elements, as it requires traversal from the head to the desired node.
• Not efficient for random access.

5. Insertion and Deletion

Array

• Inserting or deleting elements can be expensive as it may require shifting elements.
• Best case: \(O(1)\) (if inserting/deleting at the end).
• Worst case: \(O(n)\) (if inserting/deleting at the beginning or middle).

Linked List

• Inserting or deleting elements is generally more efficient as it only involves updating pointers.
• Best case: \(O(1)\) (if inserting/deleting at the beginning).
• Worst case: \(O(n)\) (if inserting/deleting requires traversal).

6. Memory Usage

Array

• Fixed-size arrays can waste memory if not all elements are used.
• Dynamic arrays may need to allocate additional memory and copy elements when resized.

Linked List

• Uses more memory per element due to storage of pointers/references.
• No wasted memory as it allocates memory as needed for each element.

7. Use Cases

Array

• Suitable for applications where quick access to elements is required.
• Preferred when the number of elements is known and relatively stable.
• Example: storing elements of a matrix, look-up tables.

Linked List

• Suitable for applications where frequent insertion and deletion of elements are required.
• Preferred when the number of elements is unknown or changes frequently.
• Example: implementing stacks, queues, and other dynamic data structures.

8. Examples

Array

    c

  int arr[5] = {1, 2, 3, 4, 5};

  // Accessing the third element

  int element = arr[2]; // element = 3

Linked List

    c

  struct Node {

      int data;

      struct Node* next;

  };

  // Creating a linked list with three nodes

  struct Node* head = (struct Node*)malloc(sizeof(struct Node));

  head->data = 1;

  head->next = (struct Node*)malloc(sizeof(struct Node));

  head->next->data = 2;

  head->next->next = (struct Node*)malloc(sizeof(struct Node));

  head->next->next->data = 3;

  head->next->next->next = NULL;

  // Accessing the second element

  struct Node* second = head->next;

  int element = second->data; // element = 2