What is a Linked List?
A linked list is a linear data structure that includes a series of connected nodes. Each node stores the data
and the address of the next node.
Types of Linked Lists
● Singly Linked List: Each node points to the next node in the sequence.
● Doubly Linked List: Each node points to both the next and the previous node.
● Circular Linked List: The last node points back to the first node, forming a circle.
Advantages of Linked Lists
● Dynamic size: They can grow or shrink during runtime.
● Efficient insertions and deletions: Elements can be added or removed without shifting other
elements.
Disadvantages of Linked Lists
● More memory: Each node requires extra memory for the pointer.
● No random access: To access an element, you must traverse the list from the beginning.
Basic Operations on Linked Lists
● Insertion: Adding a new node to the list (at the beginning, end, or specific position).
● Deletion: Removing an existing node from the list.
● Traversal: Visiting each node in the list.
● Search: Finding a specific element in the list.
Implementing a Linked List in Java
● Node Class: Define a class for the node that will hold the data and a reference to the next node.
● LinkedList Class: Implement methods for insertion, deletion, traversal, and search.
Use Cases for Linked Lists
● Implementing stacks and queues.
● Managing dynamic memory allocation.
● Representing polynomial expressions.
● Implementing undo/redo functionality in applications.
A java.util.LinkedList is a part of Java's Collections Framework and implements the List and Deque
interfaces. It is a doubly-linked list implementation, meaning each node in the list holds references to both
the next and previous nodes.
Key Characteristics of java.util.LinkedList
● Doubly Linked: Provides efficient traversal in both forward and backward directions.
● Non-Synchronized: Not thread-safe by default. If multiple threads access a LinkedList
concurrently and at least one of the threads modifies the list, it must be synchronized externally.
● Permits null elements: You can store null values in a LinkedList.
● Ordered Collection: Maintains the insertion order of elements.
When to Use java.util.LinkedList
LinkedList is generally preferred over ArrayList when:
● Frequent insertions and deletions are performed in the middle of the list.
● You need to use it as a stack (LIFO) or a queue (FIFO), as it efficiently supports addFirst(),
addLast(), removeFirst(), removeLast(), etc.
● Memory usage for each node is less of a concern than the performance of insertions/deletions.
When to Avoid java.util.LinkedList
● When random access (accessing elements by index) is frequently required, as it has O(n) time
complexity for get(index). ArrayList would be more efficient for this (O(1)).
● When memory is a critical concern, as each node stores additional pointers.
Common java.util.LinkedList Methods
● add(E e): Appends the specified element to the end of this list.
● add(int index, E element): Inserts the specified element at the specified position in this list.
● addFirst(E e): Inserts the specified element at the beginning of this list.
● addLast(E e): Appends the specified element to the end of this list.
● remove(Object o): Removes the first occurrence of the specified element from this list, if it is
present.
● remove(int index): Removes the element at the specified position in this list.
● removeFirst(): Removes and returns the first element from this list.
● removeLast(): Removes and returns the last element from this list.
● get(int index): Returns the element at the specified position in this list.
● set(int index, E element): Replaces the element at the specified position in this list with the
specified element.
● contains(Object o): Returns true if this list contains the specified element.
● size(): Returns the number of elements in this list.
Here is a sample shopping list java program.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class LinkedListBufferedReaderExample {
public static void main(String[] args) {
LinkedList<String> shoppingList = new LinkedList<>();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Welcome to your Shopping List Manager!");
System.out.println("Enter 'add' to add an item, 'remove' to remove an item, 'display' to view your list,
or 'exit' to quit.");
String command;
try {
while (true) {
System.out.print("\nEnter command: ");
command = reader.readLine();
if (command == null) {
// EOF reached
break;
}
command = command.trim().toLowerCase();
switch (command) {
case "add":
System.out.print("Enter item to add: ");
String itemToAdd = reader.readLine();
if (itemToAdd != null) {
itemToAdd = itemToAdd.trim();
if (!itemToAdd.isEmpty()) {
shoppingList.add(itemToAdd);
System.out.println("'" + itemToAdd + "' added to the list.");
} else {
System.out.println("Item cannot be empty.");
}
} else {
System.out.println("No input received.");
}
break;
case "remove":
if (shoppingList.isEmpty()) {
System.out.println("The shopping list is empty. Nothing to remove.");
} else {
System.out.println("Current Shopping List:");
for (int i = 0; i < shoppingList.size(); i++) {
System.out.println((i + 1) + ". " + shoppingList.get(i));
}
System.out.print("Enter the number of the item to remove: ");
String input = reader.readLine();
if (input != null) {
input = input.trim();
try {
int indexToRemove = Integer.parseInt(input);
if (indexToRemove > 0 && indexToRemove <= shoppingList.size()) {
String removedItem = shoppingList.remove(indexToRemove - 1);
System.out.println("'" + removedItem + "' removed from the list.");
} else {
System.out.println("Invalid item number.");
}
} catch (NumberFormatException e) {
System.out.println("Invalid input. Please enter a number.");
}
} else {
System.out.println("No input received.");
}
}
break;
case "display":
if (shoppingList.isEmpty()) {
System.out.println("Your shopping list is empty.");
} else {
System.out.println("\n--- Your Shopping List ---");
for (int i = 0; i < shoppingList.size(); i++) {
System.out.println((i + 1) + ". " + shoppingList.get(i));
}
System.out.println("--------------------------");
}
break;
case "exit":
System.out.println("Exiting Shopping List Manager. Goodbye!");
return;
default:
System.out.println("Invalid command. Please try again.");
}
}
} catch (IOException e) {
System.err.println("Error reading input: " + e.getMessage());
} finally {
try {
if (reader != null) {
reader.close();
}
} catch (IOException e) {
System.err.println("Error closing reader: " + e.getMessage());
}
}
}
}
