Linked List Implementation In C#

• 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”.

• They are dynamic in nature and allocate memory as and when required.
• Insertion and deletion is easy to implement.
• Other data structures such as Stack and Queue can also be implemented easily using Linked List.
• It has faster access time and can be expanded in constant time without memory overhead.
• Since 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 List

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 – previous link and 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, SinglyLinkedList class definition will look like below.

internal class SingleLinkedList {  
    internal Node head;  
}

The DoublyLinkedList class will contain nodes of type DNode class. Hence, 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 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 front of the doubly linked list, we have to follow one extra step .i.e point the previous pointer of 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 Linked List

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;    
}

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;  
}

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

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;  
}

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;  
    }  
}

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;  
}

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;  
    }  
}

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;  
}