Linked List

Overview #

Linked List is a dynamic linear data structure that stores a collection of data elements.

The Linked List consists of the nodes. The list node is an object that stores some valuable data and a reference (pointer) to the next node. All the nodes are linked to the list.

Advantages #

• Dynamic memory allocation. The memory is allocated and de-allocated according to the actual usage. It doesn’t use extra space.
• Constant time Insert/Remove. Inserts and removes takes constant time, unlike arrays. However, it takes O(N) time to traverse to the target element.
• Fundamental structure. Linked List has a straightforward logic and can be used for other data structures implementation (e.g., Stack, Queue, Graph, and HashMap).

class Node<E> {
  public E data;
  public Node next;
}

Time Complexity #

Common Operations #

• Insertion
• Deletion
• Traversing

Types #

The Linked List might be implemented in the following ways:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Doubly Linked List #

Double-Linked List contains the nodes with the two pointers - to the previous and next list elements.

class Node<E> {
  public E data;
  public Node next;
  public Node prev;
}

Circular Linked List #

In the Circular Linked List, the last node points to the first node, forming a circular loop.