There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.
- Traversal: Visiting every node to print or process data.
- Insertion: Adding a new node (at the beginning, end, or specific position).
- Deletion: Removing an existing node and updating the links.
- Search: Finding a node with a specific value.
Java Implementation: Singly Linked List
This code follows the node structure seen in your Stack/Queue tutorials but expands it for general list operations.
// 1. Define the Node Class
class Node {
int data;
Node next;
// Constructor
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 2. Define the Linked List Class
public class LinkedList {
private Node head; // The entry point to the list
// Operation: Insert at the End
public void append(int data) {
Node newNode = new Node(data);
// Case 1: List is empty
if (head == null) {
head = newNode;
return;
}
// Case 2: Traverse to the end
Node current = head;
while (current.next != null) {
current = current.next;
}
// Link the last node to the new node
current.next = newNode;
System.out.println("Inserted: " + data);
}
// Operation: Insert at the Beginning (Head)
public void push(int data) {
Node newNode = new Node(data);
newNode.next = head; // Point new node to current head
head = newNode; // Update head to be the new node
System.out.println("Inserted at head: " + data);
}
// Operation: Delete by Value
public void delete(int key) {
Node current = head;
Node prev = null;
// Case 1: Head holds the key
if (current != null && current.data == key) {
head = current.next; // Move head forward
System.out.println("Deleted: " + key);
return;
}
// Case 2: Search for the key
while (current != null && current.data != key) {
prev = current;
current = current.next;
}
// Case 3: Key was not found
if (current == null) {
System.out.println("Element not found");
return;
}
// Unlink the node
prev.next = current.next;
System.out.println("Deleted: " + key);
}
// Operation: Display (Traversal)
public void display() {
Node current = head;
System.out.print("List: ");
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// Main Method to Run Code
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.display(); // Output: 10 -> 20 -> 30 -> null
list.push(5);
list.display(); // Output: 5 -> 10 -> 20 -> 30 -> null
list.delete(20);
list.display(); // Output: 5 -> 10 -> 30 -> null
}
}