Initiated by this thread I intended to create a very simple example of a singly-linked list. However, I got distracted by the possibilities in C#, with generics and interfaces, etc.. This tutorial presents a much simpler example, concentrating on the basics and the essential methods to Add, Remove and Insert a node, as well as iterating the list.
I am not presenting a tutorial on linked lists, their uses, importance, issues, etc.. Refer to the wikipedia link, your course materials or book, for this, and I assume that you've read such material already. My purpose is to demonstrate simple implementations of the essential methods: Add, Insert and Remove. I demonstrate iterating the list as well, which is more straightforward. I do, however, discuss a few points as they arise.
Once you have a basic understanding of what linked lists are (and hopefully realise their significance to computer science and data structures) the next important step is to understand how nodes are added, inserted and removed from the list. There are other methods and features that can be added, but it is this trio of methods that embody the essential algorithms/techniques needed with linked lists.
I anticipate some criticism of this class. It is preferable that a node contain a single data-item (its payload) and a reference to the Next node, not merging the data (a Person) and node behaviour into a single PersonNode in this way. The Person and node behaviour are too tightly integrated, and will have to be broken apart to extend this example to move towards a flexible, generic, linked list that could work with different object types.
However, now that I've explained this, and given that this is a basic example whose purpose is to demonstrate Add, Insert, etc., we can move on. See the DIC topic I linked at the beginning for examples which separate a Data item.
It isn't that difficult to separate Person from node behaviour. Nevertheless, for a first example, I still think it is easier to follow with a single class rather than two (or more).
It is essential that we always hold a reference to the beginning of our linked list. I am not allowing the default constructor, a person must always be supplied to initiate the list.
Let's look at the Add method, which always adds at the end of the list.
Before we can add to the end of the list we first have to find where this end is. We start at the first node, checking what its .Next refers to. It will either refer to another node, or be null. If it isn't null, meaning there is another node, then we point the temp variable at this next node, and repeat.
Eventually, we reach the end of the list, which we know because temp.Next is null. Now all we need to do is point temp.Next at the new node (Person) that we are adding, and ensure that this new Person's Next is null, because it is the new end of list item.
Some implementations of a singly-linked list will maintain a reference to the last node in addition to the first. This obviously has the benefit of not needing to navigate to the end each time a new item is added, it just requires a little care to ensure that it always correctly refers to the last node.
The code that first navigates to the end of the list could be separated out as a helper method.
Start with the first node, using Next to move forward, stopping when null is encountered.
The next method is InsertAfter.
My method finds an existing person in the list, and inserts a new person after him/her. The method returns true or false to confirm if the new person was successfully inserted.
We must consider that the existing person we are looking for could be the first node. We immediately check the first node's data (FirstName and LastName) and then, if not a match, move forward using Next. Once again, Next being null tells us that we have reached the end of the list. In addition though, it also tells us that the person we are looking for is not in the list, so we can return false because the new person has not been inserted.
If the existing person is found, then we make sure that the new person's Next points to the node we have found's Next. Then the existing person's (the found node's) Next is pointed to the new person we are inserting. The image just above makes this process clearer.
I consider it an important point to understand why this operation has to occur in this order. If it doesn't, and the order is switched, then the newly inserted person has broken the list, the chain. Its Next is a self-reference and there is no way to recover, to re-attach to the remaining, following, items in the list. Not only is the list broken, but our application will eventually crash because of the self-referencing node.
It doesn't matter if the existing person is the first node; because we are inserting after this person the reference to the first node will not change.
Another common method is InsertAt(index). To achieve this we would just need to update a counter as the list is iterated, and pause when we reach the correct index. If indexes are used then it makes sense to maintain a count (size) of the list, so that we don't waste time trying to find an index that won't exist.
It is not trivial nor, more importantly, sensible, to implement InsertBefore() or RemoveBefore() methods. If you need these then use a different data structure; for example, a doubly-linked list.
Removal of the first node requires updating of the held reference to the first node.
Removal of this first node could result in an empty list, requiring special handling.
We need to keep track of the previous node, the one that points to the one we are removing.
// is it the first node?
For my simple example I decided just to not allow an empty list, the user cannot remove the last remaining item. This isn't typical, or expected, behaviour. In particular, my code doesn't distinguish between the person not existing in the list, or him/her existing but not being removed because he/she is the last item in the list.
To allow for an empty list it would first be sensible to offer the default, nullary constructor. Then to maintain a count/size of the list, and probably to provide an IsEmpty property.
Actually removing the first item is simple, just change _first so that it points to _first.Next. The previous first node is just discarded.
Remember, we need to keep a reference to the previous node, which we do before examining the Next node.
If the item to remove is found then we set the previous item's Next to point to the current item's Next, skipping past the one we are removing. Refer to the diagram above. Realise that it doesn't matter if the item we are removing is the last item, because the previous item's Next will be set to the last item's Next, which is null.
Here's the full code which includes some test code in the Main method.
It should be noted that .NET already has LinkedList<T> Class, as well as Queue, Stack and many other collection types. Studying and understanding linked lists and data structures is important, it doesn't necessarily mean that we would create such structures for ourselves from scratch.