Page 1 of 1

Singly-Linked List, A Basic Example

#1 andrewsw  Icon User is online

  • the case is sol-ved
  • member icon

Reputation: 6377
  • View blog
  • Posts: 25,768
  • Joined: 12-December 12

Posted 18 October 2015 - 05:45 PM

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.

Linked list :wikipedia

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.



Start a new Console Application. Here is our PersonNode class:
namespace SinglySimple {
    class Program {
        public class PersonNode {
            public string FirstName { get; set; }
            public string LastName { get; set; }

            public PersonNode Next { get; set; }

            public PersonNode(string first, string last) {
                this.FirstName = first;
                this.LastName = last;
                this.Next = null;
            }
        }


(The full code is provided at the end of the tutorial.)

Attached Image

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).

Here is the beginning of our PersonNodeList class:
        public class PersonNodeList {
            private PersonNode _first;

            public PersonNodeList(PersonNode pers) {
                _first = pers;
            }


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.
        public void Add(PersonNode pers) {
            PersonNode temp = _first;
            // find the last node
            while (temp.Next != null) {
                temp = temp.Next;
            }
            temp.Next = pers;
            // ensure that this is the last node
            pers.Next = null;
        }


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.



It isn't essential to set the new item's Next to null as this is its default. I prefer to do so, and recommend it, to prevent any possibility of there not being an end, null value (the list's terminator). Our code, and list, will fall down if this value isn't present. (Compare with a circular linked list.)

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.



The simplest to implement is a method that iterates/navigates the entire list:
        public void DisplayAll() {
            PersonNode temp = _first;
            do {
                Console.WriteLine(string.Format("{0} {1}", temp.FirstName, temp.LastName));
                temp = temp.Next;
            } while (temp != null);
        }


Start with the first node, using Next to move forward, stopping when null is encountered.

The next method is InsertAfter.

Attached Image

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.
        public bool InsertAfter(PersonNode pExisting, PersonNode pNew) {
            PersonNode temp = _first;
            do {
                if (temp.FirstName == pExisting.FirstName && temp.LastName == pExisting.LastName) {
                    pNew.Next = temp.Next;
                    temp.Next = pNew;
                    return true;
                }
                temp = temp.Next;
            } while (temp != null);
            return false;
        }


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.

Nor have we needed to make any special provision for the existing person being the last node. The newly inserted person's Next will be the same as the existing person's Next which, in the case of the last node, will be null. (If a reference were being retained to the last node then this would need to be adjusted.)

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.

(If indexes are used then methods such as Find() or IndexOf() are likely to be implemented to give some meaning to an index number.)

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.



Now the Remove method.

Attached Image

Removal is more complicated than insertion. It isn't that the operation is any more technical than for insertion, it is because:

  • 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.

(If we were maintaining a reference to the last node, then removing the last node would also require an adjustment to this reference.)

Here's the full code for the method:
        public bool Remove(PersonNode pers) {
            PersonNode temp = _first;
            // is it the first node?
            if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
                // check if only single node
                if (temp.Next == null) {
                    // currently, cannot allow empty list
                    return false;
                } else {
                    _first = _first.Next;
                    return true;
                }
            }
            while (temp.Next != null) {
                PersonNode prev = temp;
                temp = temp.Next;
                if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
                    prev.Next = temp.Next;
                    return true;
                }
            }
            return false;
        }


We start with special handling for the first node:
        PersonNode temp = _first;
        // is it the first node?
        if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
            // check if only single node
            if (temp.Next == null) {
                // currently, cannot allow empty list
                return false;
            } else {
                _first = _first.Next;
                return true;
            }
        }


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.

Another consideration - not just for the case of an empty list - is to include an extra sentinel or dummy node before the "true" first node (or after the last). This simplifies a lot of the navigation because there will always be at least one node. (The reported size of the list would just be reduced by one.)



        } else {
            _first = _first.Next;
            return true;
        }


Actually removing the first item is simple, just change _first so that it points to _first.Next. The previous first node is just discarded.

Now we can continue beyond the first node:
        while (temp.Next != null) {
            PersonNode prev = temp;
            temp = temp.Next;
            if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
                prev.Next = temp.Next;
                return true;
            }
        }
        return false;


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.
namespace SinglySimple {
    class Program {
        public class PersonNode {
            public string FirstName { get; set; }
            public string LastName { get; set; }
            
            public PersonNode Next { get; set; }

            public PersonNode(string first, string last) {
                this.FirstName = first;
                this.LastName = last;
                this.Next = null;
            }
        }
        public class PersonNodeList {
            private PersonNode _first;

            public PersonNodeList(PersonNode pers) {
                _first = pers;
            }
            public void Add(PersonNode pers) {
                PersonNode temp = _first;
                // find the last node
                while (temp.Next != null) {
                    temp = temp.Next;
                }
                temp.Next = pers;
                // ensure that this is the last node
                pers.Next = null;
            }
            public void DisplayAll() {
                PersonNode temp = _first;
                do {
                    Console.WriteLine(string.Format("{0} {1}", temp.FirstName, temp.LastName));
                    temp = temp.Next;
                } while (temp != null);
            }
            public bool InsertAfter(PersonNode pExisting, PersonNode pNew) {
                PersonNode temp = _first;
                do {
                    if (temp.FirstName == pExisting.FirstName && temp.LastName == pExisting.LastName) {
                        pNew.Next = temp.Next;
                        temp.Next = pNew;
                        return true;
                    }
                    temp = temp.Next;
                } while (temp != null);
                return false;
            }
            public bool Remove(PersonNode pers) {
                PersonNode temp = _first;
                // is it the first node?
                if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
                    // check if only single node
                    if (temp.Next == null) {
                        // currently, cannot allow empty list
                        return false;
                    } else {
                        _first = _first.Next;
                        return true;
                    }
                }
                while (temp.Next != null) {
                    PersonNode prev = temp;
                    temp = temp.Next;
                    if (temp.FirstName == pers.FirstName && temp.LastName == pers.LastName) {
                        prev.Next = temp.Next;
                        return true;
                    }
                }
                return false;
            }
        }

        static void Main(string[] args) {
            PersonNodeList personList = new PersonNodeList(new PersonNode("Bob", "Biscuit"));
            personList.Add(new PersonNode("Peter", "Griffin"));
            personList.Add(new PersonNode("Ted", "Jones"));
            personList.Add(new PersonNode("Mary", "Bourbon"));

            personList.DisplayAll();

            personList.Remove(new PersonNode("Peter", "Griffin"));

            Console.WriteLine("Peter removed..");
            personList.DisplayAll();

            personList.InsertAfter(new PersonNode("Ted", "Jones"), new PersonNode("Fred", "Fiddle"));

            Console.WriteLine("Fred inserted after Ted..");
            personList.DisplayAll();

            Console.ReadKey();
        }
    }
}



Is This A Good Question/Topic? 0
  • +

Replies To: Singly-Linked List, A Basic Example

#2 andrewsw  Icon User is online

  • the case is sol-ved
  • member icon

Reputation: 6377
  • View blog
  • Posts: 25,768
  • Joined: 12-December 12

Posted 19 October 2015 - 01:31 AM

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1