Linked List Implementation in C#

Linked lists are a basic and popular data structure in computer science. In this post, we take a closer look at them and how you might implement one using C#.

Ankit Sharma

Dec. 28, 17 · Tutorial

Likes (4)

Comment

Save

53.4K Views

Introduction

In this article, I am going to discuss one of the most important Data Structures - Linked Lists.

I Will Be Explaining:

Linked lists.
Advantage of a linked list.
Types of linked lists.
How to create a linked list.
Various operations on al inked list.

Before proceeding further, I would recommend you download the source code from GitHub.

What Is a Linked List?

A linked list is a linear data structure which consists of a group of nodes in a sequence. Each node contains two parts.

Data− Each node of a linked list can store a data.
Address − Each node of a linked list contains an address to the next node, called “Next.”

The first node of a linked list is referenced by a pointer called Head

Image title

Advantages of a Linked List

They are dynamic in nature and allocate memory as and when required.
Insertion and deletion are easy to implement.
Other data structures such as Stack and Queue can also be implemented easily using a linked list.
It has faster access time and can be expanded in constant time without memory overhead.
There is no need to define an initial size for a linked list, hence memory utilization is effective.
Backtracking is possible in doubly linked lists.

Types of Linked Lists

Singly Linked List: Singly linked lists contain nodes which have a data part and an address part, i.e., Next, which points to the next node in the sequence of nodes. The next pointer of the last node will point to null.

Doubly Linked List: In a doubly linked list, each node contains two links – the first link points to the previous node and the next link points to the next node in the sequence. The previous pointer of the first node and next pointer of the last node will point to null.

Circular Linked List: In the circular linked list, the Next of the last node will point to the first node, thus forming a circular chain.

Doubly Circular Linked List: In this type of linked list, the Next of the last node will point to the first node and the previous pointer of the first node will point to the last node.

Creating a Linked List

The node of a singly linked list contains a data part and a link part. The link will contain the address of the Next node and is initialized to null. So, we will create a class definition of the node for a singly linked list as follows:

internal class Node {  
    internal int data;  
    internal Node next;  
    public Node(int d) {  
        data = d;  
        next = null;  
    }  
}

The node for a Doubly Linked list will contain one data part and two link parts – the previous link and the next link. Hence, we create a class definition of a node for the doubly linked list as shown below.

internal class DNode {  
    internal int data;  
    internal DNode prev;  
    internal DNode next;  
    public DNode(int d) {  
        data = d;  
        prev = null;  
        next = null;  
    }  
}

Now, our node has been created, so, we will create a linked list class now. When a new Linked List is instantiated, it just has the head, which is Null. The SinglyLinkedList class will contain nodes of type Node class. Hence, the SinglyLinkedList class definition will look like this:

internal class SingleLinkedList {  
    internal Node head;  
}

The DoublyLinkedList class will contain nodes of type DNode class. Hence, the DoublyLinkedList class will look like this:

internal class DoubleLinkedList {  
    internal DNode head;  
}

Various Operations on Linked List

1. Insert Data at Front of the Linked List

The first node, head, will be null when the linked list is instantiated. When we want to add any node at the front, we want the head to point to it.
We will create a new node. The next of the new node will point to the head of the Linked list.
The previous Head node is now the second node of the Linked List because the new node is added at the front. So, we will assign head to the new node.

internal void InsertFront(SingleLinkedList singlyList, int new_data) {    
    Node new_node = new Node(new_data);    
    new_node.next = singlyList.head;    
    singlyList.head = new_node;    
}

To insert the data at the front of the doubly linked list, we have to follow one extra step - point the previous pointer of the head node to the new node. So, the method will look like this:

internal void InsertFront(DoubleLinkedList doubleLinkedList, int data) {  
    DNode newNode = new DNode(data);  
    newNode.next = doubleLinkedList.head;  
    newNode.prev = null;  
    if (doubleLinkedList.head != null) {  
        doubleLinkedList.head.prev = newNode;  
    }  
    doubleLinkedList.head = newNode;  
}

2. Insert Data at the End of a Linked List

If the linked list is empty, then we simply add the new node as the Head of the linked list.
If the linked list is not empty, then we find the last node and make the Next of the last node go to the new node, hence the new node is the last node now.

internal void InsertLast(SingleLinkedList singlyList, int new_data)    
{    
    Node new_node = new Node(new_data);    
    if (singlyList.head == null) {    
        singlyList.head = new_node;    
        return;    
    }    
    Node lastNode = GetLastNode(singlyList);    
    lastNode.next = new_node;    
}

To insert the data at the end of a doubly linked list, we have to follow one extra step: point the previous pointer of the new node to the last node. The method will look like this:

internal void InsertLast(DoubleLinkedList doubleLinkedList, int data) {  
    DNode newNode = new DNode(data);  
    if (doubleLinkedList.head == null) {  
        newNode.prev = null;  
        doubleLinkedList.head = newNode;  
        return;  
    }  
    DNode lastNode = GetLastNode(doubleLinkedList);  
    lastNode.next = newNode;  
    newNode.prev = lastNode;  
}

The last node will be the one with its next pointing to null. Hence we will traverse the list until we find the node with Next as null and return that node as the last node. Therefore the method to get the last node will be:

internal Node GetLastNode(SingleLinkedList singlyList) {  
    Node temp = singlyList.head;  
    while (temp.next != null) {  
        temp = temp.next;  
    }  
    return temp;  
}

In the above-mentioned method, pass the doubleLinkedList object to get the last node for the doubly linked list.

3. Insert Data After a Given Node of Linked List

We have to insert a new node after a given node.
We will set the Next of the new node to the Next of the given node.
Then we will set the Next of the given node to the new node.

So the method for a singly linked list will look like this:

internal void InsertAfter(Node prev_node, int new_data)  
{  
    if (prev_node == null) {  
        Console.WriteLine("The given previous node Cannot be null");  
        return;  
    }  
    Node new_node = new Node(new_data);  
    new_node.next = prev_node.next;  
    prev_node.next = new_node;  
}

To perform this operation on a doubly linked list we need to follow two extra steps:

Set the Previous of the new node to the given node.
Set the Previous of the next node of the given node to the new node.

So, the method for a doubly linked list will look like this:

internal void InsertAfter(DNode prev_node, int data)  
{  
    if (prev_node == null) {  
        Console.WriteLine("The given prevoius node cannot be null");  
        return;  
    }  
    DNode newNode = new DNode(data);  
    newNode.next = prev_node.next;  
    prev_node.next = newNode;  
    newNode.prev = prev_node;  
    if (newNode.next != null) {  
        newNode.next.prev = newNode;  
    }  
}

4. Delete a Node From a Linked List Using a Given Key Value

The first step is to find the node that has the key value.
We will traverse the linked list, and use one extra pointer to keep track of the previous node while traversing the linked list.
If the node to be deleted is the first node, simply set the Next pointer of the Head to point to the next element from the Node to be deleted.
If the node is in the middle somewhere, then find the node before it, and make the Node before it point to the node next to it.
If the node to be deleted is the last node, then find the node before it, and set it to point to null.

So, the method for a singly linked list will look like this:

internal void DeleteNodebyKey(SingleLinkedList singlyList, int key)  
{  
    Node temp = singlyList.head;  
    Node prev = null;  
    if (temp != null && temp.data == key) {  
        singlyList.head = temp.next;  
        return;  
    }  
    while (temp != null && temp.data != key) {  
        prev = temp;  
        temp = temp.next;  
    }  
    if (temp == null) {  
        return;  
    }  
    prev.next = temp.next;  
}

To perform this operation on a doubly linked list, we don’t need any extra pointers for the previous node, as a doubly linked list already has a pointer to the previous node. So the delete method will be:

internal void DeleteNodebyKey(DoubleLinkedList doubleLinkedList, int key)  
{  
    DNode temp = doubleLinkedList.head;  
    if (temp != null && temp.data == key) {  
        doubleLinkedList.head = temp.next;  
        doubleLinkedList.head.prev = null;  
        return;  
    }  
    while (temp != null && temp.data != key) {  
        temp = temp.next;  
    }  
    if (temp == null) {  
        return;  
    }  
    if (temp.next != null) {  
        temp.next.prev = temp.prev;  
    }  
    if (temp.prev != null) {  
        temp.prev.next = temp.next;  
    }  
}

5. Reverse a Singly Linked List

This is one of the most famous interview questions. We need to reverse the links of each node to point to its previous node, and the last node should be the head node. This can be achieved by iterative as well as recursive methods. Here I am explaining the iterative method.

We need two extra pointers to keep track of the Previous and Next nodes and initialize them to null.
Start traversing the list from the head node to the last node and reverse the pointer of one node in each iteration.
Once the list is exhausted, set the last node as the head node.

The method will look like this,

public void ReverseLinkedList(SingleLinkedList singlyList)  
{  
    Node prev = null;  
    Node current = singlyList.head;  
    Node temp = null;  
    while (current != null) {  
        temp = current.next;  
        current.next = prev;  
        prev = current;  
        current = temp;  
    }  
    singlyList.head = prev;  
}

Conclusion

We have implemented a singly linked list and doubly linked list using C#. We have also performed various operations on them. Please refer to the attached code for better understanding. You will find a few more methods in the attached code such as finding the middle element and searching a linked list.

Please give your valuable feedback in the comment section.

You can also find this article at C# Corner.

You can find my other articles on data structures here.

csharp Pointer (computer programming) Data (computing) Links Implementation

Published at DZone with permission of Ankit Sharma, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

Trending