Jump to content
  • Advertisement
Sign in to follow this  
stitchs_login

C# Linked List implementation review

This topic is 1294 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
Advertisement

Why are you implementing your own linked list?

 

Is this purely for academic purposes to learn how it works or do the existing list containers that come with C# not fit your needs? If not, how come?

 

Just curious... 

Share this post


Link to post
Share on other sites
I'm not the best on linked lists, so I won't really comment there; it looks good and I can't think of any way to improve it.

I did want to point out you have a type mismatch though. Your iterators (i) are ints while index is a uint.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!