LinkedList Operations and Use Cases

Creating a LinkedList and using its specific methods like

addFirst()
addLast(), add()
removeFirst(), removeLast()
getFirst(), getLast(), get(index)
contains()
clear()

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // A LinkedList of Strings
        LinkedList<String> destinations = new LinkedList<>();

        // Add elements to the first and last positions
        destinations.addFirst("Tokyo");  // Add to the beginning
        destinations.add("Paris");     // add() is equivalent to addLast()
        destinations.addLast("London");  // Add to the end
        destinations.addFirst("Sydney"); // Add to the beginning again
        System.out.println("Current list: " + destinations);

        // Access elements (similar to ArrayList, but can also peek)
        System.out.println("First destination: " 
	        + destinations.getFirst());
        System.out.println("Last destination: " 
	        + destinations.getLast());

        System.out.println("Third destination: " 
	        + destinations.get(2));

        System.out.println("The list contains 'London': " 
	        + destinations.contains("London"));

        for (String destination : destinations){
	        System.out.println("- " + destination);
        }
        
        // Remove elements from the first and last positions
        String removedFirst = destinations.removeFirst();
        String removedLast = destinations.removeLast();
        System.out.println("Removed first element: " 
	        + removedFirst);
        System.out.println("Removed last element: " 
	        + removedLast);
        System.out.println("List after removals: " + destinations);

		destinations.clear();
		System.out.println("Is the list empty? " 
			+ destinations.isEmpty());
    }
}

Current list: [Sydney, Tokyo, Paris, London]
First destination: Sydney
Last destination: London
Third destination: Paris
The list contains 'London': true
- Sydney
- Tokyo
- Paris
- London
Removed first element: Sydney
Removed last element: London
List after removals: [Tokyo, Paris]
Is the list empty? true

When to Use a LinkedList

A LinkedList stores elements in nodes, with each node holding a reference to the next and previous node. This structure makes it the preferred choice in these scenarios:

• Frequent Insertions and Deletions: When you need to add or remove many elements from the beginning or middle of the list, LinkedList is very fast. Unlike an ArrayList, it doesn't need to shift subsequent elements; it just updates the links between nodes. This is a constant-time operation.

• Implementing Stacks and Queues: LinkedList provides methods like addFirst(), removeFirst(), and addLast(), which make it a perfect fit for implementing stack (LIFO) and queue (FIFO) data structures.

Avoid LinkedList when frequent random access is needed of elements by index (e.g., list.get(500)). To find the 500th element, it has to traverse the list from the beginning, which is a slow operation (O(n)). In that case, an ArrayList is much better.

5. Implementing a Queue with LinkedList

A queue follows a First-In, First-Out (FIFO) principle. Creating a simple TicketQueue class that uses a LinkedList to manage a queue of people.

Enqueue: addLast()Dequeue: removeFirst()isEmpty() for checking

import java.util.LinkedList;

class TicketQueue {
    private LinkedList<String> queue = new LinkedList<>();
	
    public void addPerson(String name) {
        queue.addLast(name);  // Enqueue: Add to end of the line
        System.out.println(name + " has joined the queue.");
        System.out.println("Current Queue: " + queue);
    }
    
    public void servePerson() {
        if (queue.isEmpty()) {
            System.out.println("The queue is empty. No one to serve.");
            return;
        }
        String servedPerson = queue.removeFirst(); // Dequeue: Serve person at the front
        System.out.println(servedPerson + " has been served.");
        System.out.println("Remaining Queue: " + queue);
    }
}

public class QueueImplementationDemo {
    public static void main(String[] args) {
        TicketQueue ticketCounter = new TicketQueue();
        
        System.out.println("--- Ticket counter opens ---");
        
        // People join the queue (enqueue)
        ticketCounter.addPerson("Alice");
        ticketCounter.addPerson("Bob");
        ticketCounter.addPerson("Charlie");
        
        System.out.println("\n--- Serving customers ---");
        
        // People are served in FIFO order (dequeue)
        ticketCounter.servePerson(); // Alice should be first
        ticketCounter.servePerson(); // Then Bob
        ticketCounter.servePerson(); // Then Charlie
        ticketCounter.servePerson(); // Queue is now empty
    }
}

--- Ticket counter opens ---
Alice has joined the queue.
Current Queue: [Alice]
Bob has joined the queue.
Current Queue: [Alice, Bob]
Charlie has joined the queue.
Current Queue: [Alice, Bob, Charlie]

--- Serving customers ---
Alice has been served.
Remaining Queue: [Bob, Charlie]
Bob has been served.
Remaining Queue: [Charlie]
Charlie has been served.
Remaining Queue: []
The queue is empty. No one to serve.