0
\$\begingroup\$

I have a small Linked list program which I created for just brushing up the concepts.

Following is my Node class

public class Node
{
    private int element;
    public int Element 
    { 
        get 
        { 
            return element; 
        } 
        set 
        {
            element = value; 
        } 
    }

    private Node next;
    public Node Next
    {
        get
        {
            return next;
        }
        set
        {
            next = value;
        }
    }

    public Node(int e, Node n)
    {
        Element = e;
        Next = n;
    }
}

Here is my linked list Class Logic.

public class CustomLinkedList
{
    private int size;
    private Node head;
    private Node tail;
    public int Size
    {
        get
        {
            return size;
        }
        private set
        {
            size = value;
        }
    }
    public Node Head
    {
        get
        {
            return head;
        }
        private set
        {
            head = value;
        }
    }
    public Node Tail
    {
        get
        {
            return tail;
        }
        private set
        {
            tail = value;
        }
    }

    public CustomLinkedList()
    {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }
    private bool isEmpty()
    {
        return Head == null;
    }

    public virtual void AddLast(int e)
    {
        Node newnode = new Node(e, null);
        if(isEmpty())
            this.head = newnode;
        else
            this.tail.Next = newnode;

        this.tail = newnode;
        this.size = this.size + 1;
    }

    public Node FindLast(int e)
    {
        Node node = this.head;
        while(node!=null)
        {
            if(node.Element==e)
                return node;
            else
                node = node.Next;
        }
        return null;

    }
    public virtual void AddFirst(int e)
    {
        Node newnode = new Node(e, null);
        if(isEmpty())
        {
            this.head = newnode;
            this.tail = newnode;
        }
        else
        {
            newnode.Next = this.head;
            this.head = newnode;
        }
        
        this.size = this.size + 1;
    }
    public virtual void AddAfter(Node n,int e)
    {
        Node newnode = new Node(e, null);
        newnode.Next = n.Next;
        n.Next = newnode;
        this.size = this.size + 1;
    }

    public virtual void RemoveFirst()
    {
        this.head = this.head.Next;
        this.size = this.size - 1;
    }

    public virtual void RemoveLast()
    {
        Node n = this.head;
        while(n!=null)
        {
            if(n.Next == this.tail)
            {
                n.Next = null;
                this.tail = n;
                this.size = this.size - 1;
            }
            n = n.Next;
        }
    }
    public virtual void Remove(int e)
    {
        Node n = this.head;
        while (n != null)
        {
            if(n.Next.Element == e)
            {
                n.Next = n.Next.Next;
                this.size = this.size - 1;
                break;
            }
            n = n.Next;
        }
    }
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        Node n = this.head;
        while(n!=null)
        {
            sb.Append(n.Element.ToString());
            n = n.Next;
            if(n!=null)
                sb.Append(" -> ");
        }

        return sb.ToString();
    }
}

After creating this class I decided to apply colors to the list output after each and every operation.

I didn't wanted to implement the coloriing logic inside the class which process the linked list. So implemented the logic like this in a derived class using virtual and override methods.

public sealed class ColoredCustomLinkedList : CustomLinkedList
{
    public override void AddLast(int e)
    {
        Console.ForegroundColor = ConsoleColor.Green;
        base.AddLast(e);
    }
    public override void AddFirst(int e)
    {
        Console.ForegroundColor = ConsoleColor.Blue;
        base.AddFirst(e);
    }
    public override void AddAfter(Node n, int e)
    {
        Console.ForegroundColor = ConsoleColor.Yellow;
        base.AddAfter(n, e);
    }
    public override void RemoveFirst()
    {
        Console.ForegroundColor = ConsoleColor.Red;
        base.RemoveFirst();
    }
    public override void RemoveLast()
    {
        Console.ForegroundColor = ConsoleColor.DarkRed;
        base.RemoveLast();
    }
    public override void Remove(int e)
    {
        Console.ForegroundColor = ConsoleColor.DarkMagenta;
        base.Remove(e);
    }

}

I am getting the desired output as follows. enter image description here

Is this the right way to do this? is there any better methods to suggest?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Which .NET and C# versions are you using? I'm asking this because your whole Node class can be simplified like this in newer C# versions: record class Node(int Element, Node Next); \$\endgroup\$ Oct 6, 2023 at 13:18
  • 1
    \$\begingroup\$ Why do you use the "ancient" coding style of using backing fields when you don't do anything with them? Why not simply have auto-implemented properties? \$\endgroup\$
    – BCdotWEB
    Oct 10, 2023 at 1:22

1 Answer 1

5
\$\begingroup\$
  1. When you Generate an override in Visual Studio, a call to the base method is automatically added. This is quite a common way to extend the behavior of a method.

    If you do not call the base method, you can provide a completely different implementation, which is also valid.

  2. I understand that this Colored... class is only for debugging. It mixes business logic with UI behavior. This is okay for this purpose.

    For a more general approach, I would create an observable collection. For this purpose, we add an event that we can attach to in order to observe changes in the collection. This allows us to separate UI stuff from the logic or to do something completely different like logging, etc.

  3. The Element is limited to int. It is easy to make the collection generic and to allow any element type.

  4. FindLast actually finds the first element. I renamed it to FindFirst in the following examples.

  5. The constructor of CustomLinkedList initializes fields to 0 and null. Fields are initialized anyway with these default values in C#. But you can keep the constructor like this for clarity if you prefer.

  6. See my appendix for coding style below.

To make the list generic we also make the Node class generic:

public class Node<T>
{
    private T element;
    public T Element
    {
        get {
            return element;
        }
        set {
            element = value;
        }
    }

    private Node<T> next;
    public Node<T> Next
    {
        get {
            return next;
        }
        set {
            next = value;
        }
    }

    public Node(T e, Node<T> n)
    {
        Element = e;
        Next = n;
    }
}

Then we adapt the custom collection accordingly. Note that == does not work anymore on generic types. Instead, we now call Equals:

public class CustomLinkedList<T>
{
    private int size;
    private Node<T> head;
    private Node<T> tail;

    public int Size
    {
        get {
            return size;
        }
        private set {
            size = value;
        }
    }

    public Node<T> Head
    {
        get {
            return head;
        }
        private set {
            head = value;
        }
    }

    public Node<T> Tail
    {
        get {
            return tail;
        }
        private set {
            tail = value;
        }
    }

    public CustomLinkedList()
    {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    private bool isEmpty()
    {
        return Head == null;
    }

    public virtual void AddLast(T e)
    {
        Node<T> newnode = new Node<T>(e, null);
        if (isEmpty())
            this.head = newnode;
        else
            this.tail.Next = newnode;

        this.tail = newnode;
        this.size = this.size + 1;
    }

    public Node<T> FindFirst(T e)
    {
        Node<T> node = this.head;
        while (node != null) {
            if (node.Element.Equals(e))
                return node;
            else
                node = node.Next;
        }
        return null;
    }

    public virtual void AddFirst(T e)
    {
        Node<T> newnode = new Node<T>(e, null);
        if (isEmpty()) {
            this.head = newnode;
            this.tail = newnode;
        } else {
            newnode.Next = this.head;
            this.head = newnode;
        }

        this.size = this.size + 1;
    }

    public virtual void AddAfter(Node<T> n, T e)
    {
        Node<T> newnode = new Node<T>(e, null);
        newnode.Next = n.Next;
        n.Next = newnode;
        this.size = this.size + 1;
    }

    public virtual void RemoveFirst()
    {
        this.head = this.head.Next;
        this.size = this.size - 1;
    }

    public virtual void RemoveLast()
    {
        Node<T> n = this.head;
        while (n != null) {
            if (n.Next == this.tail) {
                n.Next = null;
                this.tail = n;
                this.size = this.size - 1;
            }
            n = n.Next;
        }
    }

    public virtual void Remove(T e)
    {
        Node<T> n = this.head;
        while (n != null) {
            if (n.Next.Element.Equals(e)) {
                n.Next = n.Next.Next;
                this.size = this.size - 1;
                break;
            }
            n = n.Next;
        }
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        Node<T> n = this.head;
        while (n != null) {
            sb.Append(n.Element.ToString());
            n = n.Next;
            if (n != null)
                sb.Append(" -> ");
        }

        return sb.ToString();
    }
}

Implementing an observable linked list:

Let us start by declaring the infrastructure types we need for the event:

public enum ListOperation
{
    AddLast,
    AddFirst,
    AddAfter,
    RemoveFirst,
    RemoveLast,
    Remove
}

public class ObservableListArgs : EventArgs
{
    public ObservableListArgs(ListOperation operation)
    {
        Operation = operation;
    }

    public ListOperation Operation { get; }
}

public delegate void ListOperationDelegate(object sender, ObservableListArgs e);

Now, we can implement the observable linked list like this:

public sealed class ObservableLinkedList<T> : CustomLinkedList<T>
{
    public event ListOperationDelegate CollectionChanged;

    private void OnCollectionChanged(ListOperation operation)
    {
        CollectionChanged?.Invoke(this, new ObservableListArgs(operation));
    }

    public override void AddLast(T e)
    {
        base.AddLast(e);
        OnCollectionChanged(ListOperation.AddLast);
    }

    public override void AddFirst(T e)
    {
        base.AddFirst(e);
        OnCollectionChanged(ListOperation.AddFirst);
    }

    public override void AddAfter(Node<T> n, T e)
    {
        base.AddAfter(n, e);
        OnCollectionChanged(ListOperation.AddAfter);
    }

    public override void RemoveFirst()
    {
        base.RemoveFirst();
        OnCollectionChanged(ListOperation.RemoveFirst);
    }

    public override void RemoveLast()
    {
        base.RemoveLast();
        OnCollectionChanged(ListOperation.RemoveLast);
    }

    public override void Remove(T e)
    {
        base.Remove(e);
        OnCollectionChanged(ListOperation.Remove);
    }
}

Now let us rewrite the console test. We declare a PrintChanges method having the same signature as our ListOperationDelegate.

static void PrintChanges(object sender, ObservableListArgs e)
{
    Console.ForegroundColor = e.Operation switch {
        ListOperation.AddLast => ConsoleColor.Green,
        ListOperation.AddFirst => ConsoleColor.Blue,
        ListOperation.AddAfter => ConsoleColor.Yellow,
        ListOperation.RemoveFirst => ConsoleColor.Red,
        ListOperation.RemoveLast => ConsoleColor.DarkRed,
        ListOperation.Remove => ConsoleColor.DarkMagenta,
        _ => ConsoleColor.White
    };
    Console.WriteLine(sender.ToString());
}

The new test:

var list = new ObservableLinkedList<int>();
list.CollectionChanged += PrintChanges;

list.AddLast(1);
list.AddLast(2);
list.AddLast(3);
list.AddFirst(30);
Node<int> node = list.FindFirst(2);
list.AddAfter(node, 10);
list.RemoveFirst();
list.RemoveLast();
list.Remove(2);

It produces the exact same output.

We can also easily create a list for strings now:

var stringList = new ObservableLinkedList<string>();
stringList.CollectionChanged += PrintChanges;
stringList.AddLast("Hello");
stringList.AddLast("World");

My Visual Studio code analysis proposes me some code fixes. Their behavior is configurable, and they are also a matter of personal preference. Therefore, I did not apply these changes to my example above, but I still would like to list them here as they may lead to a better coding style:

  • "Add braces to 'if' statement" and "Add braces to 'else' statement".
  • "Naming rule violation: Missing prefix: '_'". Many developers prepend field names with an _. This makes it easier to distinguish between fields and local variables or parameters.
  • "Naming rule violation: These words must begin with upper case characters: isEmpty". The widely accepted naming conventions for C# state that type, method, and property names must be written in PascalCase.
  • "Object initialization can be simplified" and "use 'var' instead of explicit type". Instead of writing Node<T> newnode = new Node<T>(e, null); and repeating the type name twice, you can either write var newnode = new Node<T>(e, null); or Node<T> newnode = new(e, null);. I would keep the C# alias for the primitive types like int or string or when the type is not immediately obvious from the code, so. int i = 0; is more readable than var i = 0;.
  • "Use '++' operator" and "Use '--' operator". this.size = this.size + 1; and this.size = this.size - 1; can also simply be written as this.size++; and this.size--; respectively.
  • "Remove 'this' qualification". You can simply write size++; and size--;. If you also use the naming convention mentioned above, it becomes clear that this refers to fields, which makes the this qualification even more obsolete: _size++; and _size--;.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.