Tech Off Thread

22 posts

Conversation Locked

This conversation has been locked by the site admins. No new comments can be made.

A simple and pure C# implementation of the good old linked list

Back to Forum: Tech Off
  • Mauricio Feijo

    While interviewing for a gig I was asked to complete an assignment, as a test. The request was to implement a C# linked list, without using Collections.  They also required me to write Add, Delete and Retrieve methods with the signatures as they are in the code below.

    This is an ages old exercise but every time a do it I feel it gets a bit cleaner and better.

    With no more delay, here is the code:

    using System;
    
    namespace LinkedListExample
    {
        public class List
        {
    
            public class Node
            {
                public object NodeContent;
                public Node Next;
            }
    
            private int size;
            public int Count
            {
                get
                {
                    return size;
                }
            }
    
            /// <summary>
            /// The head of the list.
            /// </summary>
            private Node head;
    
            /// <summary>
            /// The current node, used to avoid adding nodes before the head
            /// </summary>
            private Node current;
    
            public List()
            {
                size = 0;
                head = null;
            }
    
    
            /// <summary>
            /// Add a new Node to the list.
            /// </summary>
            public void Add(object content)
            {
                size++;
    
                // This is a more verbose implementation to avoid adding nodes to the head of the list
                var node = new Node()
                {
                    NodeContent = content
                };
    
                if (head == null)
                {
                    // This is the first node. Make it the head
                    head = node;
                }
                else
                {
                    // This is not the head. Make it current's next node.
                    current.Next = node;
                }
    
                // Makes newly added node the current node
                current = node;
    
    
                // This implementation is simpler but adds nodes in reverse order. It adds nodes to the head of the list
    
                //head = new Node()
                //{
                //    Next = head,
                //    NodeContent = content
                //};
    
            }
    
            /// <summary>
            ///  Throwing this in to help test the list
            /// </summary>
            public void ListNodes()
            {
                Node tempNode = head;
    
                while (tempNode != null)
                {
                    Console.WriteLine(tempNode.NodeContent);
                    tempNode = tempNode.Next;
                }
            }
    
    
    
            /// <summary>
            /// Returns the Node in the specified position or null if inexistent
            /// </summary>
            /// <param name="Position">One based position of the node to retrieve</param>
            /// <returns>The desired node or null if inexistent</returns>
            public Node Retrieve(int Position)
            {
                Node tempNode = head;
                Node retNode = null;
                int count = 0;
    
                while (tempNode != null)
                {
                    if (count == Position - 1)
                    {
                        retNode = tempNode;
                        break;
                    }
                    count++;
                    tempNode = tempNode.Next;
                }
    
                return retNode;
            }
    
            /// <summary>
            /// Delete a Node in the specified position
            /// </summary>
            /// <param name="Position">Position of node to be deleted</param>
            /// <returns>Successful</returns>
            public bool Delete(int Position)
            {
                if (Position == 1)
                {
                    head = null;
                    current = null;
                    return true;
                }
    
                if (Position > 1 && Position <= size)
                {
                    Node tempNode = head;
    
                    Node lastNode = null;
                    int count = 0;
    
                    while (tempNode != null)
                    {
                        if (count == Position - 1)
                        {
                            lastNode.Next = tempNode.Next;
                            return true;
                        }
                        count++;
    
                        lastNode = tempNode;
                        tempNode = tempNode.Next;
                    }
                }
    
                return false;
            }
        }
    }
    

     

    I added a client console app to test the linked list. Here is how it turned out:

     

    using LinkedListExample;
    using System;
    
    namespace LinkedListExampleClient
    {
        class Program
        {
            static void Main(string[] args)
            {
                List list = new List();
        
                list.Add("A");
                list.Add("B");
                list.Add("C");
                list.Add("D");
                list.Add("E");
                list.Add("F");
                list.Add("G");
                list.Add("H");
    
                list.ListNodes();
                Console.WriteLine();
    
                Console.WriteLine();
                Console.WriteLine("Deleting node 8");
                list.Delete(8);
                list.ListNodes();
                
                Console.WriteLine();
                Console.WriteLine("Position 5: " + list.Retrieve(5).NodeContent);
    
                Console.WriteLine();
                Console.WriteLine("Deleting node 5");
                list.Delete(5);
    
                Console.WriteLine();
                Console.WriteLine("Position 5: " + list.Retrieve(5).NodeContent);
    
                Console.WriteLine();
                list.ListNodes();
    
                Console.ReadLine();
    
            }
        }
    }
    

     

    So running the client, we can see the linked list adding nodes ( In the correct order. See the Add method in code for details on that.), Listing, deleting and retrieving.

     

    This was a fun little implementation, so I thought I'd share.

     

    I appreciate  your comments. Thanks!

  • PopeDai

    For the sake of completeness, I'd ensure my LinkedList implements IList, IEnumerable, supports Generic type arguments, conforms to .NET's naming guidelines (e.g. "Remove" instead of "Delete", etc), and passes FxCop.

  • blowdart

    Now make it thread safe Smiley

  • MasterPi

    Implement Sort(), bonus with a passed-in comparator.

    Also, write a bunch of unit tests and write some of the methods recursively.

  • Sven Groot

    , blowdart wrote

    Now make it thread safe Smiley

    Without using a lock. Tongue Out

    (It can be done, but I'm glad I didn't get that as an interview question last week)

  • PopeDai

    , MasterPie wrote

    Also, write a bunch of unit tests and write some of the methods recursively.

    Rewrite it in Haskell.

  • MasterPi

    , Sven Groot wrote

    Without using a lock. Tongue Out

    Thread.Sleep(Thread.CurrentThread.ManagedThreadId * c);

    where c is verrrrrry large. Tongue Out

  • Mauricio Feijo

    @PopeDai: Yep, I agree. Thing is, requirements dictated, no generics, no Collections and also dictated the method names.

  • Mauricio Feijo

    @MasterPie: Like

  • evildictait​or

    , Sven Groot wrote

    *snip*

    Without using a lock. Tongue Out

    (It can be done, but I'm glad I didn't get that as an interview question last week)

    Writing a lock free thread safe linked list is hard. Doing the same for a doubly-linked list is much harder (but still possible) Smiley

  • evildictait​or

    , MasterPie wrote

    *snip*

    Thread.Sleep(Thread.CurrentThread.ManagedThreadId * c);

    where c is verrrrrry large. Tongue Out

    No. Thread.Sleep guarantees that your thread will sleep for at least N milliseconds, but makes no guarantee about when it will wake up after that.

    Suppose that c is a million, and we have two threads with managed id 1 and 2.

    The first thread sleeps for 1 * one million milliseconds. The second sleeps for 2 * one million milliseconds.

    But in your code there is no guarantee that the first thread will start before 2.1 million milliseconds after the call. And consequently you still have a race-condition.

  • Ion Todirel

    the hello world of data structures? now make a tree Smiley

  • satchitanand

    In line 61, shouldn't the line

     current.Next = node;

    be

     current.Next = null; ??

    Where will the statement  while (tempNode != null) stop in ListNodes, Retrieve and Delete functions ?

    Thanks,

    Satchitanand

  • cheong

    @Ion Todirel:For bonus, make an AVL tree.

    Recent Achievement unlocked: Code Avenger Tier 4/6: You see dead program. A lot!
    Last modified
  • MasterPi

    , cheong wrote

    @Ion Todirel:For bonus, make an AVL tree.

    ...and generate a visualization showing the balancing. Tongue Out

  • Ion Todirel

    , MasterPie wrote

    *snip*

    ...and generate a visualization showing the balancing. Tongue Out

    with smooth animations, naturally using opengl

  • cheong

    , Ion Todirel wrote

    *snip*with smooth animations, naturally using opengl

    While generating steps on how it's done could be "at" the level of interview assignments, IMO generate smooth animation is asking for too much.

    Recent Achievement unlocked: Code Avenger Tier 4/6: You see dead program. A lot!
    Last modified
  • ahmedelkila​ni

    list.Delete(1); // deletes everything ????

    Line 126 to 131 should be replaced with:

     

    if (Position == 1)
    {
    if(Position == size) 
    {
         head = head;
         current = null;
         return true;
    } 
    else if (Position > size)
    {
    return false;
    }
    else
    {
    head = head.Next;
    return true;
    }
    }

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.