A Custom Ordered Linked List in C#

The .NET Framework has virtually every kind of data structure you need for most programming. But once in a blue moon you may need to create a very specific, custom data structure from scratch. Recently I was working with graphs and writing C# code that had many millions of statements like:

List<int> list = new List<int>();
. . .
list.Add(someInt);
list.Sort();
. . .
list.Remove(someInt);
list.Sort();
. . .

In other words I had a List of int values that needed to be sorted at all times. The List<int> type from the Collections.Generic namespace worked just fine but I wanted to see what a custom data structure would do. I created a MyLinkedList class which implemented an ordered linked list of int values where no duplicates are allowed like:

MyLinkedList list = new MyLinkedList();
. . .
list.Insert(someInt); // insert in order
. . .
list.Delete(someInt); // maintain order
. . .

My initial results were promising: my custom list was significantly faster (about three times) than the List<int> version. Unfortunately I also needed to fetch values from the list, like list[7] for the List<int> or list.GetValue(7) for the custom list. I also needed to search for values like list.BinarySearch(someInt) or list.MyLinearSearch(someInt). When these things were taken into account the custom version was much slower. But I still had fun looking at a custom linked list in C#.

  class MyLinkedList
  {
    private class Node // kind of simulates a pointer
    {
      public int data; // data is just an int
      public Node link; // single linked list; points to next node
    }

    private Node head; // ‘pointer’ to front of list
    private int count; // number data items in list

    public MyLinkedList() // ctor creates an empty list
    {
      head = null;
      count = 0;
    }

    public int Count
    {
      get { return count; }
    }

    public void Insert(int value) // inserts in order
    {
      Node prev = null;
      Node curr = head;
      while (curr != null && curr.data < value)
      {
        prev = curr;
        curr = curr.link;
      }
      Node n = new Node();
      n.data = value;
      if (prev == null) // inserting at beginning of list
      {
        n.link = head;
        head = n;
      }
      else // inserting in middle or at end
      {
        prev.link = n;
        n.link = curr;
      }
      ++count;
    }

    public void Delete(int value)
    {
      // throws if value not in list
      Node prev = null;
      Node curr = head;
      while (curr != null && curr.data != value)
      {
        prev = curr;
        curr = curr.link;
      }
      if (prev == null) // deleting first node
      {
        head = curr.link;
      }
      else // deleting any node other than first node
      {
        prev.link = curr.link;
      }
      –count;
    }

    public override string ToString()
    {
      string s = “”;
      Node p = head;
      while (p != null)
      {
        s += p.data + ” -> “;
        p = p.link;
      }
      s += “X”;
      return s;
    }

    public int GetValue(int i) // fetch value at position i
    {
      Node p = head;
      int ct = 0;
      while (p != null && ct < i)
      {
        p = p.link;
        ++ct;
      }
      return p.data;
    }

    public bool LinearSearch(int value)
    {
      Node p = head;
      while (p != null)
      {
        if (p.data == value)
          return true;
        if (p.data > value) // short circuit out
          return false;
        p = p.link;
      }
      return false;
    }
  }

 

This entry was posted in Software Test Automation. Bookmark the permalink.