A linked list is a data structure that consists of a group of nodes. Each node contains a piece of data and a reference to the next node in the list. The first node of a linked list is known as the head. The last node in the list contains a reference to null, indicating that there is no next node. Linked lists are often used to implement queues and stacks. They can also be used to implement other data structures, such as hash tables and adjacency lists.
Linked lists have several advantages over other data structures, such as arrays. They are easy to insert and delete elements from, and they don't require much memory overhead. Linked lists can also be traversed in multiple ways, making them very flexible.
This tutorial demonstrates how to implement a Linked List in C#. A generic type called LinkedList already exist in the System.Collections.Generic namespace therefore the example code in this tutorial is intented only for educational purpose.
Implementing a Node in C#
Linked lists consists of a set of nodes. So the first step in the implentation of a linked list is to implement a node. Nodes consists of some data and a reference to the next node. We will define a generic class named Node with two members - Data and Next. A generic node class, allows users to create nodes of any data type. We will also define a constructor that creates a new node.
namespace LinkedList
{
internal class Node<T>
{
public T Data;
public Node<T> Next;
public Node(T data, Node<T> next)
{
this.Data = data;
this.Next = next;
}
}
}
LinkedList Class
The LinkedList generic class implements a linked list and basic operations such as adding and removing elements from the list. Let's first look at the program and then go throught the implementation details.
using System;
namespace LinkedList
{
internal class LinkedList
{
private Node<T> head = null;
/// <summary>
/// Add elements to the top of the list
/// </summary>
/// <param name="data">Data</param>
public void Add(T data)
{
Node<T> n = new Node<T>(data, head);
head = n;
}
/// <summary>
/// Add an element to the end of the list
/// </summary>
/// <param name="data">Data</param>
public void AddLast(T data)
{
Node<T> current = head;
while (current.Next != null)
{
current = current.Next;
}
Node<T> n = new Node<T>(data, current.Next);
current.Next = n;
}
/// <summary>
/// Get elements from the top of the list
/// </summary>
/// <returns>First element in the list</returns>
public T Get()
{
if (head != null)
return head.Data;
else
throw new Exception("List is empty");
}
/// <summary>
/// Get the last element in the list
/// </summary>
/// <returns>Last element</returns>
public T GetLast()
{
if (head == null)
{
throw new Exception("List is empty");
} else
{
// Move to the last element of the list
Node<T> current = head;
while (current.Next != null)
{
current = current.Next;
}
return current.Data;
}
}
/// <summary>
/// Remove elements from the top of the list
/// </summary>
public void Remove()
{
head = head.Next;
}
/// <summary>
/// Remove last element from the list
/// </summary>
public void RemoveLast()
{
//If only one element in list
if (head.Next == null)
{
head = null;
}
else
{
// Move to the last element of the list
Node<T> current = head;
Node<T> previous = null;
while (current.Next != null)
{
previous = current;
current = current.Next;
}
previous.Next = current.Next;
}
}
/// <summary>
/// Print all elements
/// </summary>
public void Print()
{
Node<T> current = head;
while (current != null )
{
Console.Write("{0} ",current.Data);
current = current.Next;
}
Console.WriteLine();
}
}
}
void Add(T data): The Add method adds a new node to the top of the list. For example, consider a linked list containing two integers 10 and 18. The following is pictorial representation of this linkedlist.
A linked list with 2 nodes If you call the
Addto add a new element, say 12, then it will be added just after the head as shown in the figure below.
Insert element at the top of a linked list void AddLast(T data): The AddLast method adds a new node to the end of the list. The value to insert is passed as an argument.
Insert element at the back of a linked list T Get(): The Get method returns the first element of the list. First element is the element that follows immediately after the head. Get method call on the two node linked list shown above returns the number 10.T GetLast(): The GetLast method returns the last element of the list. To get the last element you need to traverse upto the last element and fetch it. GetLast method call on the two node linked list shown above returns the number 18.void Remove(): The Remove method removes the first element of the list.void RemoveLast(): The Last method traverses up to the last element and removes it from the list.void Print(): The Print function prints all the elements in the list.
Console program that uses LinkedList class
Here is an console application example to demonstrate how to declare and use the LinkedList class.
class Program
{
static void Main(string[] args)
{
LinkedList<int> list = new LinkedList<int>();
list.Add(18);
list.Add(10);
Console.Write("Linked list contains: ");
list.Print();
Console.WriteLine("First element is {0}",list.Get());
Console.WriteLine("Last element is {0}", list.GetLast());
list.Add(12);
Console.Write("After adding an element, list contains: ");
list.Print();
list.AddLast(12);
Console.Write("After adding an element at the end, list contains: ");
list.Print();
list.Remove();
Console.Write("After removing an element, list contains: ");
list.Print();
list.RemoveLast();
Console.Write("After removing last element, list contains: ");
list.Print();
Console.ReadKey();
}
}
Output from the above program will be like this
Linked list contains: 10 18 First element is 10 Last element is 18 After adding an element, list contains: 12 10 18 After adding an element at the end, list contains: 12 10 18 12 After removing an element, list contains: 10 18 12 After removing last element, list contains: 10 18
