Implementation and Analysis of Singly Linked List

Traverse, insert, delete, reverse and find nth last element in singly linked list


Category: Data Structure And Algorithms Tags: C#

Linked List Code Files

Introduction

    We introduced Doubly Linked List in previous article which had two pointers to move forward and backward from any node. Singly linked list is most common linked list used in many applications like queues and moves only forward from a given node.

Singly Linked List
Fig 1: Singly Linked List

Implementation

    For Singly linked list we will use following node structure which contains Key and one forward pointer which will point to next node in linked list.

public class Node
{
    public Node(int key)
    {
        Key = key;
    }
    public int Key;
    public Node Next;
}

Below operations will be implemented in this article.

public interface ILinkedList
{
    Node Head { get; set; }
    void PrintLinkedList();
    void Insert(int key);
    void Delete(int key);
    void Reverse();
    Node FindNthFromEnd(int n);
}

Lets implement all the methods in interface one by one.

public class LinkedList : ILinkedList
{
    public Node Head { get; set; }

    public void PrintLinkedList()
    {
        var temp = Head;
        while (temp != null)
        {
            Console.WriteLine(temp.Key);
            temp = temp.Next;
        }
    }
}

Print is simple traversal of linked list which uses next pointer to reach end of the linked list. We traverse until reached null because last node of a linked list points to null. Lets implement next method in above class.

public void Insert(int key)
{
    var node = new Node(key);
    if (Head == null)
    {
        Head = node;
        return;
    }

    Node temp = Head;
    while(temp.Next != null)
    {
        temp = temp.Next;
    }
    temp.Next = node;
}

Insert is similar to traversal where we find last element of linked list and add a new node at the end by pointing next pointer of last element to a new node.

public void Delete(int key)
{
    if (Head == null)
        return;

    if (Head.Key == key)
    {
        Head = Head.Next;
        return;
    }

    Node temp = Head.Next;
    Node previous = Head;
    while (temp != null)
    {
        if (temp.Key == key)
        {
            previous.Next = temp.Next;
            return;
        }
        previous = temp;
        temp = temp.Next;
    }
}

In delete we would need one extra pointer to keep track of previous node while traversing. Once target node is found we can bypass the next pointer of previous node to the next node of current node. So linked list: Head->1->2->3->4->null if we want to delete 2 then we have to point 1 directly to 3.

public void Reverse()
{
    Node current = Head;
    Node prev = null;
    Node next;

    while (current.Next != null)
    {
        next = current.Next;
        current.Next = prev;
        prev = current;
        current = next;
    }
    current.Next = prev;
    Head = current;
}

Reverse requires three pointers previous, current and next. We have to change direction from current to previous at each node. So if linked list is: Head->1->2->3->4->null, direction at 2 is 2->3 it should be now changed to 2->1 same way at 3 it should be now 3->2 instead of 3->4. If we go on the list will be reversed like: null<-1<-2<-3<-4<-Head.

public Node FindNthFromEnd(int n)
{
    Node normal = Head;
    Node fastForward = Head;

    while (n > 1)
    {
        fastForward = fastForward.Next;
        n--;
    }
    while (fastForward.Next != null)
    {
        fastForward = fastForward.Next;
        normal = normal.Next;
    }

    return normal;
}

To find nth element from end we have to have 2 pointers one is fast forwarded pointer which is already n times ahead of normal pointer. Then we iterate both of the pointers until fast forwarded pointer is reached to the end and we will have our n'th element from last in normal pointer. Lets run everything:

static void Main(string[] args)
{
    ILinkedList linkedList = new LinkedList();
    // Insert
    linkedList.Insert(1);
    linkedList.Insert(2);
    linkedList.Insert(3);
    linkedList.Insert(4);

    // Print
    Console.WriteLine("Lisnked list elements:");
    linkedList.PrintLinkedList();

    // Delete
    linkedList.Delete(2);
    Console.WriteLine("Lisnked list elements after delete:");
    linkedList.PrintLinkedList();

    // nth element from the end
    var node = linkedList.FindNthFromEnd(2);
    Console.WriteLine($"Lisnked list 2nd last element is: {node.Key}");

    // Reverse
    linkedList.Reverse();
    Console.WriteLine("Lisnked list elements after reverse:");
    linkedList.PrintLinkedList();
}

Output

Lisnked list elements:

1

2

3

4

Lisnked list elements after delete:

1

3

4

Lisnked list 2nd last element is: 3

Lisnked list elements after reverse:

4

3

1

Conclusion

    Most of the operations on linked list can be done in O(n) time. Linked list is most basic data structure when you start learning data structures and algorithms. There are many applications are done using linked lists i.e. Stack, Queue, Dynamic Memory Allocation etc.


Like 0 People
Last modified on 8 January 2022
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 158
Questions: 16
Given Best Solutions: 16 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x