Linked lists are a fundamental data structure used in computer science for organizing and manipulating data. In C#, a linked list is a collection of objects or nodes, each containing a value and a reference to the next node. In this blog, we will dive into the basics of linked lists in C# and explore their uses with examples.
What is a Linked List?
A linked list is a collection of nodes where each node contains a value and a reference (pointer) to the next node in the list. The first node of a linked list is called the head, and the last node is called the tail. The tail node’s reference is null, indicating the end of the list.
Types of Linked Lists
There are two types of linked lists in C#: singly linked lists and doubly linked lists.
Singly Linked List: In a singly linked list, each node has only one reference pointing to the next node. The tail node’s reference is null, indicating the end of the list.
Doubly Linked List: In a doubly linked list, each node has two references pointing to the next node and the previous node. The head node’s previous reference and the tail node’s next reference are null, indicating the start and end of the list, respectively.
Linked List Operations
Linked lists support the following basic operations in C#:
- Insertion: Adding a new node to the list
- Deletion: Removing a node from the list
- Traversal: Iterating through the list to access its elements
Let’s explore these operations in more detail.
Insertion
Inserting a new node into a linked list involves creating a new node with the desired value and inserting it into the list at the appropriate position. There are three scenarios for inserting a new node:
- Insertion at the head of the list: To insert a new node at the head of the list, create a new node with the desired value and set its reference to the current head node. Then, set the head node to the new node.
- Insertion at the tail of the list: To insert a new node at the tail of the list, create a new node with the desired value and set the current tail node’s reference to the new node. Then, set the new node as the tail node.
- Insertion in the middle of the list: To insert a new node in the middle of the list, first, find the node after which the new node should be inserted. Then, create a new node with the desired value and set its reference to the next node. Finally, set the previous node’s reference to the new node.
Here’s an example of how to insert a new node at the head of a singly linked list in C#
public class Node {
public int Value { get; set; }
public Node Next { get; set; }
}
public class LinkedList {
public Node Head { get; set; }
public void InsertAtHead(int value) {
Node newNode = new Node() { Value = value };
newNode.Next = Head;
Head = newNode;
}
}
LinkedList linkedList = new LinkedList();
linkedList.InsertAtHead(1);In this example, we define a Node class to represent each node in the linked list and a LinkedList class to represent the linked list itself. The InsertAtHead method of the LinkedList class creates a new node with the desired value, sets its reference to the current head node, and sets the head node to the new node.
Deletion
Deleting a node from a linked list involves updating the references of the previous and next nodes to bypass the node being deleted. There are three scenarios for deleting a node:
- Deletion at the head of the list: To delete the head node of a linked list, set the head node to its next node.
- Deletion at the tail of the list: To delete the tail node of a linked list, find the previous node and set its reference to null.
- Deletion in the middle of the list: To delete a node in the middle of the list, first, find the previous node and update its reference to the next node. Then, update the next node’s reference to the previous node. This will bypass the node being deleted.
Here’s an example of how to delete a node from a singly linked list in C#:
public class Node {
public int Value { get; set; }
public Node Next { get; set; }
}
public class LinkedList {
public Node Head { get; set; }
public void Delete(int value) {
if (Head == null) {
return;
}
if (Head.Value == value) {
Head = Head.Next;
return;
}
Node current = Head;
while (current.Next != null) {
if (current.Next.Value == value) {
current.Next = current.Next.Next;
return;
}
current = current.Next;
}
}
}
LinkedList linkedList = new LinkedList();
linkedList.InsertAtHead(1);
linkedList.InsertAtHead(2);
linkedList.InsertAtHead(3);
linkedList.Delete(2);In this example, we define a Node class to represent each node in the linked list and a LinkedList class to represent the linked list itself. The Delete method of the LinkedList class iterates through the nodes in the list, finds the node with the desired value, and updates the references of the previous and next nodes to bypass the node being deleted.
Traversal
Traversing a linked list involves iterating through the nodes in the list to access its elements. To traverse a linked list, start at the head node and follow the references to the next node until you reach the tail node. Here’s an example of how to traverse a singly linked list and print its elements in C#:
public class Node {
public int Value { get; set; }
public Node Next { get; set; }
}
public class LinkedList {
public Node Head { get; set; }
public void Traverse() {
Node current = Head;
while (current != null) {
Console.WriteLine(current.Value);
current = current.Next;
}
}
}
LinkedList linkedList = new LinkedList();
linkedList.InsertAtHead(1);
linkedList.InsertAtHead(2);
linkedList.InsertAtHead(3);
linkedList.Traverse();In this example, we define a Node class to represent each node in the linked list and a LinkedList class to represent the linked list itself. The Traverse method of the LinkedList class iterates through the nodes in the list, starting at the head node, and prints their values.
Full Code.
public class Node {
public int Value { get; set; }
public Node Next { get; set; }
}
public class LinkedList {
public Node Head { get; set; }
public void InsertAtHead(int value) {
Node newNode = new Node() { Value = value };
newNode.Next = Head;
Head = newNode;
}
public void InsertAtTail(int value) {
Node newNode = new Node { Value = value };
if (Head == null) {
Head = newNode;
return;
}
Node current = Head;
while (current.Next != null) {
current = current.Next;
}
current.Next = newNode;
}
public void InsertAtMiddle(int value, int position) {
Node newNode = new Node { Value = value };
if (position == 0) {
newNode.Next = Head;
Head = newNode;
return;
}
Node current = Head;
for (int i = 0; i < position - 1 && current != null; i++) {
current = current.Next;
}
if (current == null) {
return;
}
newNode.Next = current.Next;
current.Next = newNode;
}
public void Delete(int value) {
if (Head == null) {
return;
}
if (Head.Value == value) {
Head = Head.Next;
return;
}
Node current = Head;
while (current.Next != null) {
if (current.Next.Value == value) {
current.Next = current.Next.Next;
return;
}
current = current.Next;
}
}
public void Traverse() {
Node current = Head;
while (current != null) {
Console.WriteLine(current.Value);
current = current.Next;
}
}
}Conclusion
Linked lists are a powerful data structure used in computer science for organizing and manipulating data. In C#, you can create singly linked lists and doubly linked lists to suit your needs. By understanding the basics of linked lists, you can begin to use them in your own programs and projects.
Attractive section of content I just stumbled upon your blog and in accession capital to assert that I get actually enjoyed account your blog posts Anyway I will be subscribing to your augment and even I achievement you access consistently fast
Simply desire to say your article is as surprising The clearness in your post is simply excellent and i could assume you are an expert on this subject Fine with your permission let me to grab your feed to keep up to date with forthcoming post Thanks a million and please carry on the gratifying work
helloI really like your writing so a lot share we keep up a correspondence extra approximately your post on AOL I need an expert in this house to unravel my problem May be that is you Taking a look ahead to see you
Its such as you learn my thoughts! You appear to grasp a lot about this, like you wrote the book in it
or something. I think that you simply could do with a few
percent to power the message home a little bit, however instead of that,
that is excellent blog. A great read. I’ll certainly be back.
helloI like your writing very so much proportion we keep up a correspondence extra approximately your post on AOL I need an expert in this space to unravel my problem May be that is you Taking a look forward to see you
Thank you for the auspicious writeup It in fact was a amusement account it Look advanced to far added agreeable from you However how can we communicate
Fantastic site Lots of helpful information here I am sending it to some friends ans additionally sharing in delicious And of course thanks for your effort
I do trust all the ideas youve presented in your post They are really convincing and will definitely work Nonetheless the posts are too short for newbies May just you please lengthen them a bit from next time Thank you for the post
helloI really like your writing so a lot share we keep up a correspondence extra approximately your post on AOL I need an expert in this house to unravel my problem May be that is you Taking a look ahead to see you
Just wish to say your article is as surprising The clearness in your post is just cool and i could assume youre an expert on this subject Fine with your permission allow me to grab your RSS feed to keep updated with forthcoming post Thanks a million and please keep up the enjoyable work
helloI really like your writing so a lot share we keep up a correspondence extra approximately your post on AOL I need an expert in this house to unravel my problem May be that is you Taking a look ahead to see you
Just wish to say your article is as surprising The clearness in your post is just cool and i could assume youre an expert on this subject Fine with your permission allow me to grab your RSS feed to keep updated with forthcoming post Thanks a million and please keep up the enjoyable work
Fantastic site A lot of helpful info here Im sending it to some buddies ans additionally sharing in delicious And naturally thanks on your sweat
BaddieHub I’m often to blogging and i really appreciate your content. The article has actually peaks my interest. I’m going to bookmark your web site and maintain checking for brand spanking new information.
Hello my loved one I want to say that this post is amazing great written and include almost all significant infos I would like to look extra posts like this