Implementing custom LinkedList in C#: Best practices for Node and List classes (Ungureanu approach)

asked 8 hours ago by @qa-1ijyrkztjlf2eozxgpvz 0 rep · 74 views

I am currently learning data structures and decided to implement my own singly linked list in C#. I have created two separate classes: Node (representing the elements) and MyLinkedList (managing the list operations like Add, Push, and Pop).

However, I want to make sure my implementation follows C# best practices and handles edge cases correctly.

Here is my Node class implementation:

csharp:

namespace Verkettete_Liste
{
    internal class Node
    {
        // _name is just an example but this could be any object
        private string _name;
        private Node _next = null;

        public Node(string name)
        {
            _name = name;
        }

        public Node Next
        {
            get
            {
                return _next;
            }
            set
            {
                _next = value;
            }
        }

        public override string ToString()
        {
            return _name;
        }
    }
}

And here is my MyLinkedList class implementation:

csharp:

using System;

namespace Verkettete_Liste
{
    internal class MyLinkedList
    {
        private Node _head = null;

        public void Add(string name)
        {
            if (_head == null)
            {
                _head = new Node(name);
            }
            else
            {
                Node temp = _head;
                // this is where I iterate through the intire list
                while (temp.Next != null)
                {
                    temp = temp.Next;
                }
                temp.Next = new Node(name);
            }
        }

        public void Push(string name)
        {
            if (_head == null)
            {
                _head = new Node(name);
            }
            else
            {
                Node temp = _head;
                _head = new Node(name);
                _head.Next = temp;
            }
        }

        public Node Pop()
        {
            Node temp = null;
            if (_head == null)
            {
                Console.WriteLine("Noch kein Element in der Liste");
            }
            else
            {
                temp = _head;
                _head = _head.Next;
            }
            return temp;
        }

        public override string ToString()
        {
            string s = string.Empty;
            if (_head != null)
            {
                Node temp = _head;

                s += temp.ToString();

                while (temp.Next != null)
                {
                    s += temp.Next.ToString();
                    temp = temp.Next;
                }
            }
            else
            {
                s = "Liste ist leer";
            }
            return s;
        }
    }
}

I have a few specific questions regarding this code:

Memory & Performance: In MyLinkedList.Add, I always iterate through the entire list to append an element. Is it better to maintain a _tail pointer to achieve \(O(1)\) efficiency?
String Concatenation: In ToString(), I use a standard while loop with string concatenation (s += ...). Is ist worth to replace this with StringBuilder to avoid performance bottlenecks with larger lists?
Encapsulation: My Pop() method returns the Node object itself, exposing internal structural properties (Next) to the outside world. Is it better practice to only return the string (the name)?
Code Duplication: In Push(), my if (_head == null) block does exactly the same thing as the else block would do if temp was null. Can this logic be simplified to fewer lines?
C# Conventions: Are the properties, backing fields, and null-initializations aligned with modern C# standards?

Any feedback or optimization tips would be highly appreciated!

Comments on this question (0)

Use comments to ask for clarification — answers go in the answer box below.

6 answers

Using a tail pointer would greatly improve performance for Add in larger lists. It does increase memory requirements. But not by a significant amount. It ends up being a design decision for your list implementation. Though considering that use cases probably contain more notes and less lists, increasing the memory footprint of a list by one pointer, should be insignificant.
You can try to profile performance differences between += and StringBuilder. You can also implement a conditional algorithm that uses += for short lists and StringBuilder for long lists. But probably using StringBuilder will be the best option for every situation here.
You should probably not expose your implementation details by returning a Note object. Both your classes are defined as internal. When providing your list as a library, you have to expose MyLinkedList. But you should avoid exposing your implementation details, like Note.
You can refactor the function to be shorter. But I doubt it's going to make it simpler. As the function is implemented, it's very easy to understand. You first handle the case where the list is empty. Otherwise the situation where it isn't. This is extremely simple. Optimizing the size or performance of the code, usually introduces complexity. Making it harder to read, modify and reason about the code.
I can't go too much into C# conventions. But a few thoughts regardless:
1. Namespaces should use PascalCase.
2. Usings should be inside of namespace blocks. (though, I'm not sure this is official and usually not relevant anyway)
3. You should activate the Nullable option (NRT) for your project (in the project properties). This makes nullable members explicit. In your case head and next (and tail) should be defined as Note? to indicate null-ability.
4. Prefer to make Node immutable. Immutable objects are usually much easier to reason about.
5. Don't use Console.WriteLine in your library. You don't know if the users of your library will have a console to begin with. Prefer to throw an exception in case of an error.
6. Keep your code in one language. It's just regarding to some string literals and the namespace. But you're mixing English with German. Try to avoid it.
7. Prefer file-scoped Namespaces instead of block-scoped.
8. Prefer properties over exposing fields. And consider that the user of your library wants to get the value out of the Node after Pop(). Right now, it only works because the user can use ToString() on the Node. But if you implement a generic version that takes a different payload, ToString() won't work anymore.
9. Implement a generic version of your list that can't just handle string.
10. Consider using var where appropriate.

Jamie Singh · 0 rep · 8 hours ago

In addition to the other answers and unrelated to your specific questions, I'd recommed to also implement the apprpriate interfaces for collections (IEnumerable or if you choose to switch to a generic implementation IEnumerable<T>, for example).

On a second note, I'd not particularly "recommend" but suggest to think about this: The Node class is (or should be, in the current implementation it's not) local to the MyLinkedList class and should be completely invisible to the user. So, I personally would make it a nested class.

Unrelated: If you want answers in relation to a specific "Ungureanu approach" that's mentioned in the title, you maybe should give a reference to what that is supposed to be. I'll admit I've never heard of it and googling the name produced nothing outside a romanian(?) professor of computer science but no specific "approach" regarding data structures.

Morgan Singh · 0 rep · 8 hours ago

The Node cannot be immutable since the Next of the current head needs to be modified when adding a new node.

Drew Chen · 0 rep · 8 hours ago

I just want to note that while my data-structures teacher loved linked lists, it is a very specialized type of collection that is rarely used in practice. I do not think I have used one in 20 years of professional development. Making a implementation for learning is perfectly fine, and very common, but implementations like this should not be used in any production code. Just make sure to write some unit tests so you known your implementation works as you expect it to.

So concerns about performance is not very important. If you are interested, do some profiling and/or benchmarking to see what impact your ideas have.

One suggestion I do have is making the collection generic, and implementing some suitable interfaces, like IReadOnlyCollection<T>. It can also be a good idea to take a look at the LinkedList<T> class to see how that API is designed, and what methods/properties might be useful.

Drew Diaz · 0 rep · 8 hours ago

Yes, to achieve O(1) for add/append a trail reference is mandatory
I probably would choose a hybrid solution. StringBuilder itself carries some overload. So better use string.Join() if the collection contains fewer items and switch to StringBuilder for large collections. Don't use + concatenation.
Returning the node object is semantically wrong. The caller age strings and expected to retrieve the same strings. So your instinct is right. I would not return a node hehe. Not because it breaks encapsulation (it does) bit primarily because it violates the semantics of your list. It's a specialized list. A better name would be StringLinkedList or similar. Now the semantic contract becomes apparent: handle strings.
I agree with your instinct again. You can safely remove the null check and only use the swapping. It will also handle the case where _head is null. In this case (inserting an item at the beginning of an empty list) it simply sets the Node.Next to null, which is already your chosen default.

I would introduce a Node.HasNext property to avoid null handling and improves readability. I would introduce same HasNext to the collection. Then let it return the Node.HasNext value of the _tail:
```
public bool HasNext => _tail?.HasNext ?? false;

public void Push(string name)
{
    Node temp = _head;
    _head = new Node(name);
    _head.Next = temp;

    if (!_head.HasNext)
    {
        _tail = _head;
    }
}
```
Yes. But I would use auto properties here and also I've null ability analyser checks to improve code quality. Backing field in Node can be removed. Then define Next as
```
public Node? Next { get; set; }
```
In your list also introduce nullability checking:
```
private Node? _head = null;
private Node? _tail = null;
```
I would also introduce a Node.Value read-only auto property to store and retrieve the node's value:
```
public string? Value { get; }
```
and remove the _name field. It's cleaner in this context than calling ToString().

In C# namespace names are usually Pascal case.

Riley Reed · 0 rep · 8 hours ago

Performance: As a general rule, you should optimize the parts which are "hot paths", e.g. used a lot. If Add() is rarely used in a performance-sensitive location, and/or your lists are always short, then there is no need to make it more efficient.

That being said, if you want Add() to be a O(1) operation, then you should indeed keep and manage a _tail pointer. If you effectively use the linked list as a stack, then you probably don't need to bother.

I fact, if you introduce a _tail, you are one step closer to making it a doubly-linked list. Consider other operations, such as removing an arbitrary node from the list, or iterating the list from tail to head. With each additional pointer you add, you also add complexity and thus room for bugs.

Additionally, keep in mind that linked lists are pretty inefficient in terms of space if their payload is just a single string pointer. Each object on the heap has a 16 byte object header (in 64 bit systems), then you have the _next pointer (8 bytes), and finally your payload (8 bytes in your example). That makes the nodes use 4 times the memory footprint of the payload. Making it doubly-linked makes this ratio even worse, and memory alignment requirements may make it even worse.

Same goes for the string concatenation. Using a StringBuilder would be a good practice, but if the ToString() is only called for debugging purposes, than this doesn't seem that relevant.

Encapsulation: yes, I think you should rather return the name, but not that much because of encapsulation considerations, but more so because your current API is inconsistent and in fact broken. You pass in a string (when adding nodes), but you get back a node object, and since it's actually removed from the list, having it's Next property available is inconsistent and may lead to logical issues.

Code duplication: you don't need to implement a special case, always use the same code whenever possible without any special handling.

You nay look into using a sentinel node for the list end, so that your code has even less special cases to handle.

C# conventions: conventions are mostly based on the context/project you're working in. Be consistent.

You could use features such as initializers to make the code more compact. For instance:

                Node temp = _head;
                _head = new Node(name);
                _head.Next = temp;

Could also be written as :

                _head = new Node(name) { Next = _head };

Jamie Kim · 0 rep · 8 hours ago

Implementing custom LinkedList in C#: Best practices for Node and List classes (Ungureanu approach)

Comments on this question (0)

6 answers

Your answer