Linked List

Posted by Abhishek on December 15, 2019

Fundamentals

Linked Lists are one of the most commonly used Linear Data Structures after arrays. They solve many problems of arrays and are used for building complex data structures. Unlike arrays, Linked Lists can grow and shrink automatically.

Linked List

Runtime Complexity of Linked List Operations

Basic Program of how to work with Linked Lists

LinkedList numbersList = new LinkedList();
numbersList.AddLast(10);
numbersList.AddLast(20);
numbersList.AddLast(30);
numbersList.AddFirst(5);
numbersList.RemoveLast();
numbersList.RemoveFirst();
Console.WriteLine(numbersList.IndexOf(20));
Console.WriteLine(numbersList.Contains(20));
Console.WriteLine(numbersList.Count);
foreach (var number in numbersList.ToArray())
{
    Console.WriteLine(number);
}

Coding Exercise – Linked List

Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.

public class LinkedList
{
    private Node First;
    private Node Last;
    private int size;

    public int Count
    {
        get { return size; }
    }
    public class Node
    {
        public int Value;
        public Node Next;

        public Node(int value)
        {
            Value = value;
        }
    }

    public void AddLast(int number)
    {
        var newNode = new Node(number);
        if (IsEmpty())
        {
            First = Last = newNode;
        }
        else
        {
            Last.Next = newNode;
            Last = Last.Next;
        }
        size++;
    }

    public void AddFirst(int number)
    {
        var newNode = new Node(number);
        if (IsEmpty())
        {
            First = Last = newNode;
        }
        else
        {
            newNode.Next = First;
            First = newNode;
        }
        size++;
    }

    private bool IsEmpty()
    {
        return First == null;
    }

    public void RemoveFirst()
    {
        if (IsEmpty())
            throw new System.Exception("No Such Element to Remove");
        if (First == Last)
        {
            First = Last = null;
        }
        else
        {
            var nodeToDelete = First;
            First = First.Next;
            nodeToDelete.Next = null;
        }
        size--;
    }

    public void RemoveLast()
    {
        if (IsEmpty())
            throw new System.Exception("No Such Element to Remove");
        if (First == Last)
        {
            First = Last = null;
        }
        else
        {
            var previous = GetPrevious(Last);
            Last = previous;
            Last.Next = null;
        }
        size--;
    }

    private Node GetPrevious(Node node)
    {
        var currentNode = First;
        while (currentNode != null)
        {
            if (currentNode.Next == node)
                return currentNode;
            else
                currentNode = currentNode.Next;
        }
        return null;
    }

    public bool Contains(int number)
    {
        return IndexOf(number) != -1;
    }

    public int IndexOf(int number)
    {
        int index = 0;
        var currentNode = First;
        while (currentNode != null)
        {
            if (currentNode.Value == number)
            {
                return index;
            }
            else
            {
                currentNode = currentNode.Next;
                index++;
            }
        }
        return -1;
    }

    public int[] ToArray()
    {
        int[] array = new int[size];
        var current = First;
        var index = 0;
        while (current != null)
        {
            array[index++] = current.Value;
            current = current.Next;
        }
        return array;
    }
}

Difference between Arrays & Linked Lists

Types of Linked Lists

Coding Exercise: Reverse a Linked List

Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.

public void Reverse()
{
    if (IsEmpty())
        return;
    var prev = First;
    var current = First.Next;
    while (current != null)
    {
        var next = current.Next;
        current.Next = prev;
        prev = current;
        current = next;
    }

    Last = First;
    Last.Next = null;
    First = prev;
}

Coding Exercise: Get the kth node from the end

Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.

public int GetKthFromTheEnd(int k)
{
    if (IsEmpty())
        throw new System.Exception("List is already empty");
    var n1 = First;
    var n2 = First;
    for (int i = 0; i < k - 1; i++)
    {
        n2 = n2.Next;
        if (n2 == null)
            throw new System.Exception("K is greater than the size of the list");
    }

    while (n2 != Last)
    {
        n1 = n1.Next;
        n2 = n2.Next;
    }

    return n1.Value;
}

Thanks for reading this post. Enjoy !!
Share on: