Linked List Operations
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.
Code Implementation: Singly Linked List
This code follows the node structure seen in your Stack/Queue tutorials but expands it for general list operations.
JavaPythonCC++
// 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();
list.push(5);
list.display();
list.delete(20);
list.display();
}
}
# 1. Define the Node Class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 2. Define the Linked List Class
class LinkedList:
def __init__(self):
self.head = None
# Operation: Insert at the End
def append(self, data):
newNode = Node(data)
# Case 1: List is empty
if self.head is None:
self.head = newNode
return
# Case 2: Traverse to the end
current = self.head
while current.next is not None:
current = current.next
current.next = newNode
print("Inserted:", data)
# Operation: Insert at the Beginning
def push(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
print("Inserted at head:", data)
# Operation: Delete by Value
def delete(self, key):
current = self.head
prev = None
if current and current.data == key:
self.head = current.next
print("Deleted:", key)
return
while current and current.data != key:
prev = current
current = current.next
if current is None:
print("Element not found")
return
prev.next = current.next
print("Deleted:", key)
# Operation: Display
def display(self):
current = self.head
print("List:", end=" ")
while current:
print(current.data, "->", end=" ")
current = current.next
print("None")
# Main Execution
list = LinkedList()
list.append(10)
list.append(20)
list.append(30)
list.display()
list.push(5)
list.display()
list.delete(20)
list.display()
#include <stdio.h>
#include <stdlib.h>
// 1. Define Node
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
// Insert at End
void append(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
printf("Inserted: %d\n", data);
}
// Insert at Beginning
void push(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
head = newNode;
printf("Inserted at head: %d\n", data);
}
// Delete by value
void deleteNode(int key) {
struct Node* current = head;
struct Node* prev = NULL;
if (current != NULL && current->data == key) {
head = current->next;
printf("Deleted: %d\n", key);
return;
}
while (current != NULL && current->data != key) {
prev = current;
current = current->next;
}
if (current == NULL) {
printf("Element not found\n");
return;
}
prev->next = current->next;
printf("Deleted: %d\n", key);
}
// Display list
void display() {
struct Node* current = head;
printf("List: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("null\n");
}
int main() {
append(10);
append(20);
append(30);
display();
push(5);
display();
deleteNode(20);
display();
return 0;
}
#include <iostream>
using namespace std;
// 1. Define Node
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
// 2. Define Linked List
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = NULL;
}
// Insert at End
void append(int data) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
cout << "Inserted: " << data << endl;
}
// Insert at Beginning
void push(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
cout << "Inserted at head: " << data << endl;
}
// Delete by value
void deleteNode(int key) {
Node* current = head;
Node* prev = NULL;
if (current != NULL && current->data == key) {
head = current->next;
cout << "Deleted: " << key << endl;
return;
}
while (current != NULL && current->data != key) {
prev = current;
current = current->next;
}
if (current == NULL) {
cout << "Element not found" << endl;
return;
}
prev->next = current->next;
cout << "Deleted: " << key << endl;
}
// Display list
void display() {
Node* current = head;
cout << "List: ";
while (current != NULL) {
cout << current->data << " -> ";
current = current->next;
}
cout << "null" << endl;
}
};
int main() {
LinkedList list;
list.append(10);
list.append(20);
list.append(30);
list.display();
list.push(5);
list.display();
list.deleteNode(20);
list.display();
return 0;
}