Removing linked list nodes

Question

I have this code to remove nodes in a linked list which have odd values. This works well but I want to fine tune it for better reading. Can you please suggest improvements?

public class MyLinkedList
{
    public int data;
    public MyLinkedList next;

    public MyLinkedList(int v)
    {
        this.data = v;
    }

    //public void add(int i)
    //{
    //    this.next = new MyLinkedList(i);
    //    this.next.next = null;
    //}

    public void printLL()
    {
        MyLinkedList mmm = this;
        while (mmm != null)
        {
            Console.Write(mmm.data);
            Console.Write("->");
            mmm = mmm.next;
        }
    }
}

public static void deleteOdd(ref MyLinkedList mll)
{
    MyLinkedList head, previous, curr;
    head = mll;
    while (head.data % 2 != 0)
    {
        head = head.next;
    }
    mll = head;

    previous = head;
    curr = previous.next;

    while (curr != null)
    {
        if (curr.data % 2 != 0)
        {
            previous.next = curr.next;
            curr = previous.next;
        }
        else
        {
            previous = previous.next;
            curr = curr.next;
        }
    }
}

static void Main(string[] args)
    {
        MyLinkedList myll1 = new MyLinkedList(1); MyLinkedList myll2 = new MyLinkedList(3);
        MyLinkedList myll3 = new MyLinkedList(4); MyLinkedList myll4 = new MyLinkedList(4);
        MyLinkedList myll5 = new MyLinkedList(5); MyLinkedList myll6 = new MyLinkedList(6);
        MyLinkedList myll7 = new MyLinkedList(5); MyLinkedList myll8 = new MyLinkedList(6);
        MyLinkedList myll9 = new MyLinkedList(6); MyLinkedList myll10 = new MyLinkedList(9);
        MyLinkedList myll11 = new MyLinkedList(11); MyLinkedList myll12 = new MyLinkedList(12);

        myll1.next = myll2; myll2.next = myll3; myll3.next = myll4; myll4.next = myll5;
        myll5.next = myll6; myll6.next = myll7; myll7.next = myll8; myll8.next = myll9;
        myll9.next = myll10; myll10.next = myll11; myll11.next = myll12; myll12.next = myll12; myll12.next = null;


    myll1.printLL();
    Console.WriteLine();
    deleteOdd(ref myll1);
    Console.WriteLine();
    myll1.printLL();
}

Answer 1

Lack of abstraction

MyLinkedList isn't really a linked list - it's a single node. The lack of an encapsulating list class makes it difficult to provide reusable methods such as Add, Remove and Contains, and the lack of such methods (among others) makes your linked list difficult and error-prone to use.

• MyLinkedList is a misleading name. Something like MyLinkedListNode would be more accurate.
• Creating a proper linked list class that 'manages' its nodes allows you to create general-purpose methods like Add and Remove, and it can implement IEnumerable and other useful interfaces (this makes it usable with foreach and Linq methods). With such methods, removing odd entries will be easier. Without them, your class is practically useless.
• Collection classes are almost always generic - this makes them usable with different data-types.
• printLL not only ties your class to the console (which VisualMelon already pointed out), it also doesn't need to be part of the class (it's using public data), and it shouldn't be part of the class because it doesn't contribute to the core responsibilities (storing data).
• All data in your class is public. That's often a bad idea, as it allows any code to modify it, and indeed, it's easy to create a problematic state: a.next = b; b.next = a; (try calling a.printLL() or removeOdd(ref a); on that).

If you're reinventing a wheel for educational purposes, then don't forget to study existing wheels (such as LinkedList<T>).

Other notes

• The use of ref here is a hack. Consider the following situation: MyLinkedList b = a; deleteOdd(ref b); a.printLL(); - a can still contain odd values. You don't need this if you create a proper linked list class.
• Squashing multiple statements on a single line makes code harder to read. It also doesn't solve the underlying problem, which is that this linked list is cumbersome to use. It would be easier if it offered a constructor that accepted an IEnumerable<T>. And if it had an Add method, you could use collection initializer syntax: var myList = new MyLinkedList { 1, 3, 5 };.

Answer 2

Simple Commentary

• The MSDN provides some naming conventions, the relevant bit being that public members should be ProperCamelCase (e.g. Data, not data).

• Public Members, and types, should ideally have at least minimal inline documentation (\\\) to make it perfectly clear how to consume the API.

• It's usually for the best to strip out old (commented) code. It has a habit of not being maintained and becoming incompatable with the code that is there. It also adds clutter.

• For 'export' code, it's rarely useful to have methods which explicitly write to the console: much more useful to have something that writes to an abstract TextWriter (which can take Console.Out or a StreamReader), or that just returns a string. These give the consumer many more options.

• deleteOdd(ref MyLinkedList) probably can't cope with empty lists (being passed them or returning them).

• printLL isn't a great variable name: what is "LL"? It's a member of MyLinkedList, so the "LL" bit is redundant; I spect a while trying to work out if it was something to do with printing left to right or something.

• mmm isn't a great variable name either: I can only assume it was meant to be mll!

---

Alternative implementation

Below are some methods which just about tally with yours, but using LinkedList<T>, and incorporating some of the suggestions above.

I don't know if you have a particular reason for needing a custom LinkedList implementation (not suggested by the code), but you can implement your methods tidily with .NET's built in LinkedList<T>, which could be argued to provide a nicer API. Crucially, it wraps up a linked list of LinkedListNode<T>s under a LinkedList<T>, which allows some (illusion of) separation of concerns, and spares you having to keep track of the head of the list explicitly. It also allows you to have an 'empty' list, which is good.

Delete Odd

This method is considerably shorter than before, and doesn't require a ref parameter. This works with empty lists. This is a much more understandable implementation, and much harder to 'get wrong', because of the API for LinkedList<T>.

/// <summary>
/// Removes odd elements from a LinkedList of integers
/// </summary>
public static void DeleteOdd(LinkedList<int> ll)
{
    LinkedListNode<int> cur = ll.First; // grab first node

    while (cur != null)
    {
        var next = cur.Next; // make a note of the next node (will be null if cur is the last element)

        if (cur.Value % 2 != 0)
        {
            ll.Remove(cur); // remove the current node if odd
        }

        cur = next; // advance to the next node
    }
}

printLL

Here are two possible alternatives, which don't depend explicitly on Console: one just produces a string, the other prints to a TextWriter (sadly there is no better interface). These are both extension methods for LinkedList<T>, but there is no particular need for this.

/// <summary>
/// Renders a linked list as a string
/// </summary>
public static string Render<T>(this LinkedList<T> ll)
{
    StringBuilder sb = new StringBuilder();

    foreach (var e in ll)
    {
        sb.Append(e.ToString());
        sb.Append("->");
    }

    return sb.ToString();
}

/// <summary>
/// Prints a linked list to a TextWriter, optionally appending a NewLine
/// </summary>
public static void Print<T>(this LinkedList<T> ll, TextWriter textWriter, bool newLine = true)
{
    foreach (var e in ll)
    {
        textWriter.Write(e.ToString());
        textWriter.Write("->");
    }

    if (newLine)
        textWriter.WriteLine();
}

I wouldn't necessarily condone having the newLine parameter being optional, or indeed being there at all: this is just for illustration of some options. It would probably be better to have both Print and PrintLine if you need both.

Example usage

Note the nicer API for building a LinkedList<T>.

private static void ExampleUsage()
{
    LinkedList<int> ll = new LinkedList<int>();
    ll.AddLast(1);
    ll.AddLast(2);
    ll.AddLast(3);
    ll.AddLast(4);
    ll.AddLast(5);

    Console.WriteLine(ll.Render());
    ll.Print(Console.Out);
    DeleteOdd(ll);
    Console.WriteLine(ll.Render());
    ll.Print(Console.Out);
}

Answer 3

Naming of variables:

• Consider the reader who has never seen your code (which will presumably be the position you will be in if you have to revisit this code in some 6 months time). What about these names: public MyLinkedList(int v) (what is v?) and MyLinkedList mmm = this; what is mmm? And again you've named the int variable data. What is data?

• And my pet peeve MyLinkedList myll1 - now is that an 'L' or an 'I' capitalised or is that a numeral '1'? It's very hard to tell and I would counsel against doing it.

• Secondly, the name “LinkedList” has certain connotations. Is it in fact a derivative class of linked List? I'm just saying that the naming of the class has considerable ambiguity, and that is the enemy of writing lucid code. If someone receives an instance of your linked list, are they entitled to expect that they can call AddFirst method on it without issues? A better name would be appropriate to reflect this.

• PrintLL change to Print? list has certain connotations. I'd probably want to steer clear of the word 'list'.

(I will return and add in further suggestiosn for improvement when I get a proper opportunity - and where relevant will show tests.).

Answer 4

Having a quick look on your source code, it suggests that you are trying to implement a singly linked list. Is that correct? Based on that I disagree with the suggestions in the previous posts to use the LinkedList<T>. The reason is that LinkedList<T> implements a doubly Linked list, as one can read in the description or in the current .NET Core implementation. So if you are really looking for a single Linked List, the LinkedList<T> will not work for you. Please dont get me wrong, if you can also use a doubly linked list then go for it and use LinkedList in the Collections, but it is important to be aware of the differences between a singly linked list and a doubly linked list.

Based on what I see in the source code above, I recommend the following refactorings:

• Your "MyLinkedList" class is actually the "Node" in your linked List and should be named so. Please also try to use the naming conventions as they make your source code much more readable.

• I recommend the following "deleteOdd" method:

  ListNode current = head;
  
  while (current != null)
  {
  
      if (current.data % 2 != 0)
      {
          if(current.previous != null) // As the list is non circular, if current!=head
          {
              current.previous.next = current.next;
          }
          else
          {
             setListHead(current.next); // current is your head
          }
      }
  
      current = current.next;
  }
  

  • Try to make your add functions run properly and use them for your test data. The best way to set up test preconditions is of course using Unit tests.