What is a Linked List? Types, Operations, and Real-World Examples
Why Do We Need Linked Lists?
In real programming, data size is often unknown or frequently changing. Arrays create problems in such situations. Arrays Issues are .
- Fixed size problems
- Array size must be decided at creation
- Can not easily grow or shrink .
- Memory Wastage
- if array size is large but data is small -> unused memory wastage .
- Costly Insertion & Deletion
- Inserting or deleting in the middle requires shifting elements.
- Time complexity becomes high.
- Continuous Memory Requirement
- Requires contiguous memory block.
- Large arrays may fail if continuous space not available.
To overcome the above issues LinkedList comes into the pictures .
Linked Lists are fundamental data structure in computer science and they offer several advantages .
- Dynamic size : Unlike Arrays , linked lists can grow and shrink dynamically for large datasets . this is because Linked lists do not require shifting elements .
- Memory utilization: Linked Lists use memory for more efficient for certain applications. they allocated memory as needed which can be beneficial when dealing with large or unpredictable data .
- Efficient Insertions/Deletions : Adding or removing elements from Linked List is more efficient than Arrays , especially for large datasets . this is because Linked Lists do not require shifting .
- Ease of Concatenation : Concatenating two Linked Lists is straight forward and efficient , unlike arrays where it can be more complex and time consuming .
Types of LinkedList
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Doubly Linked List
1. Singly Linked List
A Singly Linked List is a type of linked list data structure in which each node contains data and a reference (pointer) to the next node only. It is called singly because every node connects in one direction — from the current node to the next node.
Structure of Singly Linked List
Each node has two parts:
- Data → stores the actual value
- Next Pointer → stores the address of the next node
package com.test.rkdigital.school.linkedlist;
public class Node {
int data; // store the data
Node next; //refrence to the next node
public Node(int data) {
// TODO Auto-generated constructor stub
this.data=data;
this.next=null; // initialize the next pointer to null
}
}
1. Linked List Insertion at Beginning: Algorithm
This Java program demonstrates how to insert data at the beginning of a Singly Linked List and display all elements using traversal.
Example :
package com.test.rkdigital.school.linkedlist;
public class LinkedList {
Node head;
static class Node{
int data;
Node next;
Node(int data){
this.data=data;
this.next=null;
}
}
// Method to insert new Node
public void insertAtBegining(int newData) {
// Create a new node with the given data
Node newNode= new Node(newData);
//Make the new node point to the current head
newNode.next=head;
//update the Head to be the new node
head=newNode;
}
//Method to print the Linked list
public void printList() {
Node currentNode=head;
while(currentNode !=null) {
System.out.println(currentNode.data);
currentNode=currentNode.next;
}
}
public static void main(String[] args) {
LinkedList list= new LinkedList();
//Insert Node at the Beginning
list.insertAtBegining(10);
list.insertAtBegining(20);
list.insertAtBegining(30);
list.printList();
}
}
2. Linked List Insertion at End: Algorithm
Step-by-Step Algorithm
- Start
- Create a new node
- Allocate memory for a new node.
- Store the given data in the node.
- Set
next = NULLbecause it will be the last node.
- Check if the linked list is empty
- If
head == NULL- Make the new node as the
head.
- Make the new node as the
- If
- Initialize a temporary pointer
- Create a pointer
last. - Assign
last = head.
- Create a pointer
- Traverse the linked list
- Move last node by node until: last.next == NULL
- This means the last node is reached.
- Insert the new node at the end
- Set: last.next = newNode
Full Implementation
package com.test.rkdigital.school.linkedlist;
public class insertAtEndLinkedList
{
//head of the list
Node head;
//Nodes class
static class Node
{
int data;
Node next;
//Constructor to initiate the Node
Node(int data){
this.data=data;
this.next=null;
}
}
//Create Method to store new Node at the end
public void insertAtEnd(int newData) {
//Create a newNode with the given data
Node newNode =new Node(newData);
if(head==null) {
head=newNode;
return;
}
//Traverse at end of the list
Node last=head;
while(last.next !=null) {
last=last.next;
}
//change the net of the last node to the new node
last.next=newNode;
}
//Method to print the linked list
public void printList() {
Node currentNode=head;
while (currentNode!=null) {
System.out.println(currentNode.data);
currentNode=currentNode.next;
}
}
public static void main(String[] args) {
insertAtEndLinkedList list=new insertAtEndLinkedList();
list.insertAtEnd(40);
list.insertAtEnd(30);
list.insertAtEnd(10);
list.insertAtEnd(20);
list.printList();
}
}
3. Write a program to Insertion After a given locator in LinkedList
Insertion after a given locator in a Linked List means adding a new node immediately after a specific node that already exists in the list. The locator represents the node (or value) after which the new element must be inserted.
package com.test.rkdigital.school.linkedlist;
import java.security.PublicKey;
import java.util.Iterator;
public class LinkedListAtLocator {
//Head of the list
Node head;
//Node class
static class Node
{
int data;
Node next;
//Construct to initialize the node
Node(int data){
this.data=data;
this.next=null;
}
}
//Create Method to insert a new node at a given position
public void insertAtPosition(int position , int newData) {
// Create the newNode with the given data
Node newNode= new Node(newData);
if(position==0) {
newNode.next=head;
head=newNode;
return;
}
// Traverse to the node before the given position
Node current=head;
for (int i = 0; i < position-1; i++) {
if(current==null) {
throw new IndexOutOfBoundsException("out of bound excedption");
}
current=current.next;
}
newNode.next = current.next;
current.next = newNode;
}
//method to print the linked list
public void printList() {
Node currNode=head;
while(currNode!=null) {
System.out.println(currNode.data);
currNode=currNode.next;
}
}
public static void main(String[] args) {
LinkedListAtLocator list=new LinkedListAtLocator();
list.insertAtPosition(0, 10);
list.insertAtPosition(1, 20);
list.insertAtPosition(2, 30);
list.insertAtPosition(1, 40);
//print the Linked List
list.printList();
}
}
4. Write a program to delete from beginning from LinkedList
Deletion at the beginning of a Linked List means removing the first node (head node) from the list.
In this operation, the head pointer is moved to the next node, and the original first node is removed from memory.
package com.test.rkdigital.school.linkedlist;
import com.test.rkdigital.school.linkedlist.LinkedList.Node;
public class DeleteFromBegining
{
Node head;
static class Node{
int data;
Node next;
Node(int data){
this.data=data;
this.next=null;
}
}
// Method to insert new Node
public void insertAtBegining(int newData) {
// Create a new node with the given data
Node newNode= new Node(newData);
//Make the new node point to the current head
newNode.next=head;
//update the Head to be the new node
head=newNode;
}
public void deleteFromBegining() {
if(head==null) {
System.out.println("list is empty, nothing to delete");
return;
}
//move the head to the next
Node temp=head;
head=head.next;
//Remove old head
temp=null;
}
//Method to print the Linked list
public void printList() {
Node currentNode=head;
while(currentNode !=null) {
System.out.println(currentNode.data);
currentNode=currentNode.next;
}
}
public static void main(String[] args) {
DeleteFromBegining list= new DeleteFromBegining();
//Insert Node at the Beginning
list.insertAtBegining(8);
list.insertAtBegining(2);
list.insertAtBegining(3);
list.insertAtBegining(7);
list.printList();
System.out.println("****************************");
list.deleteFromBegining();
list.printList();
}
}
Output:
