Linked List Tutorial
What is a Linked List?
A linked list is a linear data structure where elements, called nodes, are connected using pointers.
Unlike arrays, linked lists do not have a fixed size, which means they can dynamically grow or shrink
as elements are added or removed. Each node in a linked list contains two parts:
1. Data: The actual data or value of the node.
2. Next: A reference or pointer to the next node in the list.
Types of Linked Lists:
1. Singly Linked List: Each node contains data and a reference to the next node in the sequence.
2. Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the
previous node.
3. Circular Linked List: The last node points back to the first node, creating a loop.
Basic Operations on Linked Lists:
1. Insertion: Adding a new node to the list.
- At the beginning (head insertion)
- At the end (tail insertion)
- After a given node
2. Deletion: Removing a node from the list.
- From the beginning (head deletion)
- From the end (tail deletion)
- From a specific position
3. Traversal: Visiting each node in the list to access the data.
4. Searching: Finding a node with a particular value.
Implementation of a Singly Linked List in C#:
using System;
public class Node
public int Data;
public Node Next;
public Node(int data)
Data = data;
Next = null;
public class LinkedList
private Node head;
// Add node at the end
public void Add(int data)
{
Node newNode = new Node(data);
if (head == null)
head = newNode;
else
Node temp = head;
while (temp.Next != null)
temp = temp.Next;
temp.Next = newNode;
// Display all nodes
public void Display()
Node temp = head;
while (temp != null)
Console.Write(temp.Data + " ");
temp = temp.Next;
Console.WriteLine();
}
// Search for a node
public bool Search(int value)
Node temp = head;
while (temp != null)
if (temp.Data == value)
return true;
temp = temp.Next;
return false;
// Delete node from the beginning
public void Delete()
if (head != null)
head = head.Next;
}
class Program
static void Main()
LinkedList list = new LinkedList();
list.Add(10);
list.Add(20);
list.Add(30);
Console.WriteLine("Linked List: ");
list.Display();
Console.WriteLine("Search for 20: " + list.Search(20));
Console.WriteLine("Search for 40: " + list.Search(40));
list.Delete();
Console.WriteLine("Linked List after deletion: ");
list.Display();
Advantages of Linked Lists:
1. Dynamic Size: Unlike arrays, the size of the linked list can grow or shrink dynamically.
2. Efficient Insertions and Deletions: Inserting or deleting nodes, especially at the beginning, is
faster than with arrays.
Disadvantages of Linked Lists:
1. Memory Usage: Each node requires extra memory to store the reference to the next (or previous)
node.
2. No Random Access: To access a node, you must traverse the list from the head, making random
access slower (O(n) time complexity).
Applications of Linked Lists:
- Dynamic Memory Allocation: Linked lists are often used in dynamic memory allocation systems
where memory needs to be allocated and deallocated dynamically.
- Implementing Stacks and Queues: Linked lists can be used to implement other data structures like
stacks and queues.
- Graph Representation: In graph algorithms, linked lists are used to represent adjacency lists.
Conclusion:
Linked lists are a fundamental data structure that provide flexibility with dynamic size and efficient
insertions/deletions. They are especially useful when memory allocation needs to be flexible and
when frequent changes are made to the data. However, they come with trade-offs such as
increased memory usage and slower access times.
