Understanding and implementing linked list data structures in Java. Learn about the mechanics, benefits, and trade-offs of using linked lists versus other collection types.
This video introduces the concept of linked lists, explaining their structure, basic operations, and comparative advantages over array-based lists in certain scenarios.
// Basic Node class for a singly linked list
public class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
// Simple LinkedList implementation
public class LinkedList<T> {
private Node<T> head;
private int size;
public LinkedList() {
head = null;
size = 0;
}
// Add to the beginning - O(1) operation
public void addFirst(T data) {
Node<T> newNode = new Node<>(data);
newNode.setNext(head);
head = newNode;
size++;
}
// Get element at index - O(n) operation
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index);
}
Node<T> current = head;
for (int i = 0; i < index; i++) {
current = current.getNext();
}
return current.getData();
}
}
This example shows a basic implementation of a singly linked list with a Node class and essential operations. Note how adding to the beginning is an O(1) operation (constant time) because it only requires updating the head reference, while accessing an element by index is an O(n) operation (linear time) as we must traverse from the head to the desired index.
This video discusses Java's built-in LinkedList implementation in the Collections framework, comparing it with ArrayList and examining when to use each.
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
public class ListPerformanceComparison {
public static void main(String[] args) {
// Creating both types of lists
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// Measuring insertion time at the beginning
long startTime = System.nanoTime();
// ArrayList insertion at beginning (slow - O(n))
for (int i = 0; i < 100000; i++) {
arrayList.add(0, i); // Have to shift all elements
}
long endTime = System.nanoTime();
System.out.println("ArrayList insertion at beginning: " +
(endTime - startTime) / 1000000 + " ms");
startTime = System.nanoTime();
// LinkedList insertion at beginning (fast - O(1))
for (int i = 0; i < 100000; i++) {
linkedList.add(0, i); // Just update references
}
endTime = System.nanoTime();
System.out.println("LinkedList insertion at beginning: " +
(endTime - startTime) / 1000000 + " ms");
// Random access performance (get by index)
startTime = System.nanoTime();
// ArrayList random access (fast - O(1))
for (int i = 0; i < 10000; i++) {
int index = (int) (Math.random() * arrayList.size());
arrayList.get(index); // Direct index calculation
}
endTime = System.nanoTime();
System.out.println("ArrayList random access: " +
(endTime - startTime) / 1000000 + " ms");
startTime = System.nanoTime();
// LinkedList random access (slow - O(n))
for (int i = 0; i < 10000; i++) {
int index = (int) (Math.random() * linkedList.size());
linkedList.get(index); // Must traverse from head/tail
}
endTime = System.nanoTime();
System.out.println("LinkedList random access: " +
(endTime - startTime) / 1000000 + " ms");
}
}
This code demonstrates performance differences between ArrayList and LinkedList. LinkedList excels at insertions/deletions at the beginning or end (O(1) operations) but is inefficient for random access (O(n) operations). ArrayList has the opposite characteristics: fast random access (O(1)) but slow insertions/deletions that require shifting elements (O(n)).
This video walks through building a custom linked list implementation, demonstrating key operations and design considerations.
// More complete linked list implementation
public class CustomLinkedList<E> {
private static class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
this.next = null;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public CustomLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// Add to the end - with tail reference this is O(1)
public void add(E element) {
Node<E> newNode = new Node<>(element);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
// Add at specific index - O(n) in worst case
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index);
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
add(element);
return;
}
Node<E> current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
Node<E> newNode = new Node<>(element);
newNode.next = current.next;
current.next = newNode;
size++;
}
// Add to the beginning - O(1)
public void addFirst(E element) {
Node<E> newNode = new Node<>(element);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head = newNode;
}
size++;
}
// Get element at index - O(n)
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index);
}
Node<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
// Remove first element - O(1)
public E removeFirst() {
if (head == null) {
throw new NoSuchElementException();
}
E data = head.data;
head = head.next;
if (head == null) {
tail = null;
}
size--;
return data;
}
}
This more comprehensive implementation demonstrates key linked list operations with time complexity analysis. Note the use of tail reference to make adding to the end an O(1) operation. The code includes methods for inserting elements at different positions, retrieving elements by index, and removing elements, each with appropriate time complexity considerations.
This video provides a comprehensive overview of linked lists, summarizing key concepts, implementations, and use cases covered in this module.
// Example: Choosing the right list implementation for the job
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class ListSelectionExample {
// Queue/stack operations (add/remove at ends) - use LinkedList
public static void queueOperationExample() {
Deque<String> queue = new LinkedList<>();
// Add to end (enqueue)
queue.addLast("First");
queue.addLast("Second");
queue.addLast("Third");
// Remove from front (dequeue)
String first = queue.removeFirst(); // "First"
String second = queue.removeFirst(); // "Second"
}
// Random access and modification - use ArrayList
public static void randomAccessExample() {
List<Integer> numbers = new ArrayList<>();
// Fill with data
for (int i = 0; i < 1000; i++) {
numbers.add(i);
}
// Fast random access
int value = numbers.get(500); // O(1) operation
// Update value at specific index
numbers.set(500, 9999); // O(1) operation
}
// Frequent insertions/deletions in the middle - consider choices carefully
public static void frequentModificationExample() {
// If most operations are at the beginning/end
LinkedList<String> linkedNames = new LinkedList<>();
// If most operations are random access with occasional insertions
ArrayList<String> arrayNames = new ArrayList<>();
// LinkedList is better when you have a reference to the node
// and can directly insert/remove without traversal
// But often ArrayList is still faster overall due to cache locality
// and lower overhead, unless insertions/deletions dominate
}
}
This code demonstrates practical scenarios for choosing between LinkedList and ArrayList. LinkedList is optimal for queue/stack operations (adding/removing at ends) and for frequent insertions in the middle when you already have a reference to the position. ArrayList excels with random access and performs better overall in many scenarios due to memory locality and lower overhead per element.