DEV Community

Harini
Harini

Posted on

LinkedList in Java

#java #linkedlist #beginners #basic

LinkedList is a class in Java Collections Framework available in the java.util package.It stores data as nodes, where each node contains the element and links to the previous and next nodes.

  • The size of a LinkedList can increase or decrease automatically while the program is running.
  • It maintains the insertion order, meaning elements are stored in the order they are added.
  • It allows duplicate elements.
  • It provides faster insertion and deletion of elements compared to ArrayList, especially at the beginning or middle of the list.

Why LinkedList is Used?
LinkedList is preferred when:

1. Frequent Insertion

  • Adding elements in the middle or beginning is fast. 
list.addFirst("Java");
Enter fullscreen mode Exit fullscreen mode

2. Frequent Deletion

  • Removing elements does not require shifting other elements. 
list.remove(2);
Enter fullscreen mode Exit fullscreen mode

3. Queue and Deque Operations
LinkedList supports operations like:

addFirst()
addLast()
removeFirst()
removeLast()
Enter fullscreen mode Exit fullscreen mode

Hence it can be used as:

  • Queue
  • Deque
  • Stack

What is a Doubly Linked List?
A Doubly Linked List is a type of linked list in which each node contains:

  • Data – the actual value stored.
  • Previous Reference (Prev) – points to the previous node.
  • Next Reference (Next) – points to the next node.

Because each node has links in both directions, we can traverse the list forward as well as backward.

Structure

NULL ← [10] ⇄ [20] ⇄ [30] ⇄ [40] → NULL
Enter fullscreen mode Exit fullscreen mode

Each node contains:

[ Prev | Data | Next ]
Enter fullscreen mode Exit fullscreen mode

For example:

[NULL | 10 | Address of 20]
[Address of 10 | 20 | Address of 30]
[Address of 20 | 30 | Address of 40]
[Address of 30 | 40 | NULL]
Enter fullscreen mode Exit fullscreen mode

Advantages of Doubly Linked List

  • Supports forward and backward traversal.
  • Faster insertion and deletion compared to arrays.
  • Easy to implement Queue, Deque, and Browser History features.
  • No need to shift elements during insertion or deletion.

Disadvantages of Doubly Linked List

  • Requires extra memory to store the previous reference.
  • More complex than a singly linked list.
  • Accessing elements by index is slower because traversal is required.

Top comments (0)