Sign in to follow this  

C# Linked List implementation review

This topic is 1044 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all,

 

I am part way through implementing my own Linked List class (only stores Strings for now) to better understand how they work. I have completed the major portions of it; Add, Delete, Insert etc. and was just wondering if I could get some feedback on the code thus far.

private StringNode list;

public MyStringList()
{
     list = null;    // empty by default;
}
public void InsertNode(string stringIn, uint index)
        {
            // Check that user is not trying to insert outside the valid
            // range of nodes.
            if (IndexOutOfUpperBounds(index))
            {
                return;
            }

            // create a string node to insert into the list
            StringNode newNode = new StringNode(stringIn);
            StringNode current;
            StringNode temp;

            if (index == 0)
            {
                // store the list head.
                temp = list;
                // set the new node as the new list head
                list = newNode;
                // reconnect the old list head to the new list head.
                list.next = temp;

                return;
            }

            // temp node that is a reference to the beginning node
            current = list;

            // loop to the position of the node at index
            // because of the way that current is initialized, we can
            // skip index zero.
            for (int i = 1; i < index; i++)
            {
                // check that there is another node to process.
                if (current.next != null)
                {
                    current = current.next;
                }
            }

            // store a reference to the next node (the one at the index we desire) so as to preserve it
            temp = current.next;

            // set the current.next to point to the location of the new node
            // and set the new nodes next to point to that of the old
            current.next = newNode;
            newNode.next = temp;
        }

        public bool DeleteNode(uint index)
        {
            if (IndexOutOfUpperBounds(index))
            {
                return false;
            }

            // temp node representing the current node in the list.
            StringNode current = list;
            // temp node representing the previous node in the list.
            StringNode previous = null;

            // if the user has searched for a node that is not the first in the list

            if (index > 0)
            {
                // loop from 0 to the index position.
                for (int i = 0; i < index; i++)
                {
                    if (current != null)
                    {
                        previous = current;
                        current = current.next;
                    }
                }
            }

            // need conditions to assure that the predecessor of a node,
            // removed from the end will point to null

            // a check to see if we are at the end of the list.
            if ((current.next == null) && (current != list))
            {
                // make the very last node null, so it will be removed by
                // garbage collection
                previous.next = null;
                current = null;
            }

            // condition that a node removed from the middle will link the two
            // nodes that surround it, properly
            else if ((current.next != null) && (current != list))
            {
                // change the previous node to link to the node up ahead.
                previous.next = current.next;
                current = null;
            }

            // condition that the successor of a node removed from the front
            // will properly set the new list head.
            else
            {
                // check that the list head is not the only node
                if (current.next != null)
                {
                    list = current.next;
                }
                else
                {
                    list = null;
                }
            }

            // reduce number of nodes by 1, if we have got to this point,
            // there is no need to check if we are allowed to decrement.
            this.Count--;

            return true;
        }

I have not included the entire implementation, for simplicity's sake. I would like to draw your attention to the Insert and Delete methods. They work in all the tests I have performed. I feel like they could be streamlined more. If you need anymore information, feel free to ask and I shall do my best to explain.

 

Many thanks,

 

Stitchs.

Share this post


Link to post
Share on other sites
Try to delay the declaration of variables until you actually need them. I think some of the complexity of the InsertNode comes from feeling like you have to make use of the temporaries you declared.

The DeleteNode seems to be handling a lot of special cases. I think you can get away with only one special case, and that is for the "head" node.

For example, look at this bit:
if (current.next != null)
{
    list = current.next;
}
else
{
    list = null;
}
We assign current.next to list if it is not null, otherwise we explicitly assign null. That block is functionally equivalent to:
list = current.next;
In addition, don't be afraid to write helper methods to split out some of the logic.

I think they could be simplified to something not unlike this:
public void InsertNode(string stringIn, uint index)
{
    if (IndexOutOfUpperBounds(index))
    {
        return;
    }

    StringNode newNode = new StringNode(stringIn);

    if (index == 0)
    {
        newNode.next = list;
        list = newNode;
    }
    else
    {
        StringNode node = GetNodeAt(index - 1);
        newNode.next = node.next;
        node.next = newNode;
    }

    this.Count++;
}

public bool DeleteNode(uint index)
{
    if (IndexOutOfUpperBounds(index))
    {
        return false;
    }

    if (index == 0)
    {
        list = list.next;
    }
    else
    {
        StringNode node = GetNodeAt(index - 1);
        node.next = node.next.next;
    }

    this.Count--;
    return true;
}

private StringNode GetNodeAt(uint index)
{
    // TODO: decide how to handle bounds checking

    StringNode current = list;
    for (uint i = 0 ; i < index ; ++i) {
        current = current.next;
    }
    return current;
}
I haven't tested this.

Share this post


Link to post
Share on other sites


am part way through implementing my own Linked List class (only stores Strings for now) to better understand how they work. I have completed the major portions of it; Add, Delete, Insert etc. and was just wondering if I could get some feedback on the code thus far.

 

Vector-based containers are almost always better than linked lists nowadays, but the linked list still wins by being able to do fast insertions and deletions without moving stuff around. So, if you're going to make a linked list, at a minimum your interface to that list should be able to do the things that make it better than a vector. By forcing Add, Delete, Insert, etc. to use an index and than scanning through the list to get to the right spot, you're not taking advantage of what you can do with a linked list.

 

Whenever you design a the public functions for a class, you should consider how it will be used. For example, how would Insert be used? Well, I might want to put something right at the beginning - your version is good for that, so we're covered there. I might want to put something at the end. This is pretty common, and your list does not support doing that quickly, but maybe that's an intentional trade-off so I'll skip that usage.

 

I might also want to search for somewhere to put an item - maybe the list is meant to be sorted in some way - and then place it there. Your list requires keeping a separate index, counting upwards through through the list. I don't see any way to access the contents of the list, but I'm afraid it would also use an index, and each access will have to count through the nodes to find the correct string, so a typical loop would have n-squared complexity. Then you would have to pass that index back into the list so it can scan through the list one last time and actually do the insertion. This is unnecessarily inefficient.

 

You should look at the interface to the C# linked list to get an idea of how this would work efficiently. The library's linked list has a LinkedListNode class you can access. This allows you to hold onto your place in the list and make insertions and deletions based off that node. Putting a vector style interface on a linked list is not taking advantage of what it can do well.

Share this post


Link to post
Share on other sites

Also worth noting that using uint indices may not be in your consumers' best interest, the reason being that the de facto type for indices in C# is int, not uint (yes, I know, that makes no sense, and there is no viable size_t-like type either, but that's the way it is) which together with C#'s type system means you are going to be inflicting a lot of tedious casting to people who will want to use your interface in any nontrivial application. Furthermore, using uint's in the interface makes it impossible for .NET languages without an unsigned type to make use of your linked list class.

 

This is mostly irrelevant for a linked list implementation, of course, but I thought I'd point it out as a design flaw (to users).

Share this post


Link to post
Share on other sites

Hi all,

 

Thanks for the feedback so far. I am implementing it to further my understanding of how they work. My intent would be to use the .NET implementation.

 

I did think as I was implementing the loops with indexes that what happens if the list gets too big? I know that each node is stored, non-sequentially, in memory which makes it longer to iterate over.

 

I have thought about adding a reference for the tail; making it the result of AddNode().

 

What I'm stuck on is the idea of holding a place in the list. Isn't this just as slow as starting from the beginning? If you start at the beginning then you don't have to worry about going backwards. Otherwise I need to create a doubly Linked List to be able to traverse back and forth.

 

I have some great feedback to work on from this.

 

Thanks,

 

Stitchs.

Share this post


Link to post
Share on other sites

The idea of a linked list is that you only iterate it start to end in one direction and that additions and deletions are cheap.

 

If you wanted to reference any index you would need a vector type list, where this operation is cheap, however addition and deletion of items is much more expensive. 

 

When selecting a container to use, algorithmic complexity is important to consider as is memory usage. It is usually a matter of trading one off against another depending on your needs.

 

If you wanted both speed of addition and deletion as well as rapid finding of indexed items you would be best reading up how rb-trees and hash maps (dictionaries) work.

 

Let me know if you aren't sure about this. :)

Share this post


Link to post
Share on other sites

As an update: I went back to my AddNode method. If I use a reference (let's call it tail) which stores the final node in the list so that new nodes can be added without traversing the list.

public void AddNode(string stringIn)
        {
            StringNode newNode = new StringNode(stringIn);

            if (IsEmpty())
            {
                list = newNode;
                tail = list;
            }
            else
            {
                tail.next = newNode;
                tail = tail.next;
            }
        }

What I'm struggling to understand is how my else statement works. It works, as in it adds nodes successfully. Can anyone clarify that my thought process as to what I'm doing is correct?

 

If the list is empty, I add the new node as the head and make the tail equal to the head (the head is both the first and last node).

 

If there is a node (say we are at the point that we haven't added anymore than one), then we make the tail.next (aka list.next) equal to our new node. Then we make tail equal this last node.

 

What I'm struggling to understand; once we exit the AddNode function, and the temp variable newNode is no longer in memory, what is preserving the references to these different nodes in memory? Only list and tail exist, I'm changing what tail points to every time I add a node to a non-empty list, how are any nodes in-between able to be referenced/not being flagged for garbage collection?

 

Please ask if you need anymore clarification.

 

Stitchs.

Share this post


Link to post
Share on other sites

What I'm struggling to understand; once we exit the AddNode function, and the temp variable newNode is no longer in memory, what is preserving the references to these different nodes in memory? Only list and tail exist, I'm changing what tail points to every time I add a node to a non-empty list, how are any nodes in-between able to be referenced/not being flagged for garbage collection?

 
The links in the list are preserving the references.
 

Empty list:
list -> null
tail -> null

after 1 insertion:
node1 = create new node 
list -> node1
node1.next -> null
tail -> node1

after 2 insertions:
node2 - create new node
list -> node1
node1.next -> node2
node2.next -> null
tail -> node2

after 3 insertions:
node3 - create new node
list -> node1
node1.next -> node2
node2.next -> node3
node3.next -> null
tail -> node3

 So list links to node1 which links to node2 which links to node3, etc
 
 As a side question, why haven't you made it generic? It wouldn't really add any complexity to your implementation

class LinkedList<T>
{
  class Node<T>
  {
    Node<T> next;
    T value;
  }   

  Node<T> list, tail;

  public void AddNode(T value)
  {
    var newNode = new Node<T>(value);

    if (IsEmpty())
    {
        list = newNode;
        tail = list;
    }
    else
    {
        tail.next = newNode;
        tail = tail.next;
    }
  }
}

Share this post


Link to post
Share on other sites

Hi all,

 

Thanks for the feedback so far. I am implementing it to further my understanding of how they work. My intent would be to use the .NET implementation.

 

I did think as I was implementing the loops with indexes that what happens if the list gets too big? I know that each node is stored, non-sequentially, in memory which makes it longer to iterate over.

 

I have thought about adding a reference for the tail; making it the result of AddNode().

 

What I'm stuck on is the idea of holding a place in the list. Isn't this just as slow as starting from the beginning? If you start at the beginning then you don't have to worry about going backwards. Otherwise I need to create a doubly Linked List to be able to traverse back and forth.

 

I have some great feedback to work on from this.

 

Thanks,

 

Stitchs.

 

You cannot just focus on low-level details such as memory footprint and cache usage. There's a place for that, but before you get there, you should at least be aware of some basic algorithm analysis. Yes, a doubly-linked list has an extra cost, and non-sequential memory access has an extra cost, but you're forgetting about the plain old cost of having to do N steps when there's an alternative that would take a constant amount of time.

 

Before you even get to insertion, let's say I want to loop over the whole list and do something with each string. I'm curious, what would that code look like, to the list user and internally?

Share this post


Link to post
Share on other sites

@ChaosEngine: I was going to implement it as a Generic Type, but I'm never going to use it for my projects and wanted something that I could get information from quickly, for testing, which is why I pre-made it using the String class.

 

@Pink Horror: I' guessing that if I wanted to look at/use every item I would (internal code):

for(int i = 0; i < list.Length; i++)
{
     DoSomething(currentNode);
     currentNode = currentNode.next;
}

User code:

DoSomethingWithAllListItems(int pLength);

This would be O(N) Linear as it will take an amount of time and resources proportional, to the size of the list (which if it gets very big, will cost a lot). If I want constant time, such as the change I have made to my AddNode() method, I would need to be able to access a node directly, knowing it's location beforehand.

 

I hope I have understood what you are trying to say, but what would be a constant alternative to looping the list. Would I have to order it first?

 

Stitchs.

Share this post


Link to post
Share on other sites

This topic is 1044 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this