Creating a linked list data structure from scratch, using generic types to be more flexible with the usage of the list. In this article I write about the base concept of a linked list and what are the advantages / disadvantages compared to the array. Why generic type is a must in the data structures. What linked list types can we differentiate.

The concept

Linked list is the best data structure if we talk about dynamic structures. We know that arrays are fine and easy to use, but they have one big disadvantage – fixed size. Hence this, we are not able to add new items when we need (and remove items if we don’t need them). This is only half true. Of course we can add and remove but the array’s size won’t change!

If you have an array of 100 slots, you can store 100 items in it at max. Less items can be stored as well, but in that case the “empty slots” are not used, which is not good. It is clearly visible that storing 101 items in 100 slots is simply not possible, so this is the problem.

Arrays need continuous memory segment as the image below shows.

Lists however use a different approach. They contain smaller blocks (or slots as I called them previously) which are “linked” together one by one. These separate blocks also stored in the memory, but since they are separate they don’t need one continuous segment. Important to highlight that one linked list node requires more space than one array item (since you have to store the content and a reference pointer as well).

Array vs List

From now on, it seems that list is every-way better than array, so there is no need from now on to use arrays. Right? No, not really.

Lists has some disadvantages which needs to be noted:

• Complicated (cumbersome use, easy to make errors).
• Nodes cannot be indexed directly.
• Search is slow (linear search)
• A node needs more memory because the address of the next node has to be stored too.

Array disadvantages compared to list:

• Size is fixed (dynamic arrays?)
• Needs a continuous memory segment.
• Insertion is hard.
• Deletion is hard.

Depending on what we want to create, we should find the suitable tools and techniques – this contains the data structures as well.

Creating a list class

1
2
3
4
5
6
7
8
9
10
11
class ChainedList
{
    private ListItem head;
    private ListItem head_pointer;
    class ListItem
    {
        public string content;
        public ListItem next;
    }
    // ADDITIONAL METHODS HERE ...
}

Generic types

In the very moment when we talk about data structures we immediately have to talk about generic types. Data does not have type, data means some general thing. In this case you can’t create a data structure for a given type eg. string. It would mean that you can only store string types inside that structure, which is not good. Imagine that you can use arrays but can only used them with strings inside – not so good.

So for this reason, we should mark the class as generic for T type when we declare the class. We can use this “template” type in the ListItem class as well – as this will represent us what is stored inside the list item.

1
2
3
4
5
6
7
8
9
10
11
class ChainedList < T >
{
    private ListItem head;
    private ListItem head_pointer;
    class ListItem
    {
        public T content;
        public ListItem next;
    }
    // ADDITIONAL METHODS HERE ...
}

From now on, we can use this data structure with any kind of type eg. string, int or Person object. When you create the object from it you have to specify what type will be stored inside (and you must follow that type later on).

1
2
3
4
5
ChainedList<string> list_1 = new ChainedList<string>();
// OR
ChainedList<bool> list_2 = new ChainedList<bool>();
// OR
ChainedList<Person> list_3 = new ChainedList<Person>();

Insertion

Now we know what is a linked list and why could it be better than an array. Let’s talk about how to add items to it. The key will be the ListItem class inside so check it carefully.

There are 3 types of insertion:

• InsertToFront : item will be inserted to the front of the list (before the first item)
• InsertToBack : item will be inserted to the back of the list (after the last item)
• InsertToNth : item will be inserted to the ‘n’th place in the list

Needed pseudo codes can be found here.

Insert to front

This is the most basic insertion, hence this is the easiest to code down. Every new item will be added to the beginning / front of the list. It is a good solution if you just want to store items and you don’t care about the order. Detailed step-by-step walkthrough can be found in the video below, check that out. The main trick here is based on the usage of the head pointer.

Insert to back

If you care about the order of the elements, you probably want to use insertion to the back. Let’s assume that we have the following insertions:

1
2
3
4
5
mylist.InsertToFront(1);
mylist.InsertToFront(2);
mylist.InsertToFront(3);
// OUTPUT: 3,2,1
// PREFERRED OUTPUT: 1,2,3

After we process the items (traverse the list), we will have the output written in the comment section. As you can see, we have the inverse order (compared to how we inserted the items). Generally when you imagine a list (eg. shopping list, to do list etc.), if you add an item it will be palced to the bottom. In programming we usually do like this. For example when we measure distance, let’s say we measure in every second. If we measure for one minute, we have 60 measurement. In most cases the order of the elements will represent time, as we move forward in time we have new and new and new measurements – added to the end of our list. In most cases we prefer this.

Insert to n-th place

In some cases we have to be precise and tell exactly where do we want to insert a given item. For this, we can create a “logic” which will help us to do this. We simply have to move from item to item in the list, and count. If we reached the n-th value, we can insert the item. We have to consider problematic cases, like if the list is empty. Or if we have less item than the place we want to insert.

Video material

You can watch the full course here in this video.

Real life solution

In real life we use mixed data structures which means that we try to combine all the positive sides of each concept. Sounds good, isn’t it?

The problem is that a linked list will always be a linked is, and array will always be an array. So in this case what is the C#’s default List class? It is a list, but it can be used like an array (indexing it with brackets like array[1]). It’s a trick to be simple. It is an array in the background with some additional logic which tries to predict how many elements will be stored inside. If you add 3 items to it, in the background it reserves place for 10 items (let’s say). So you can easily add newer and newer items to it. But what happens when you want to insert 20 more items? It simply creates a new array in the background with more space, copies the items to the new array and adds the new items – that’s all.

Why is it good? Because reaching the items is still O(1) time by indexing it. If you want to reach the 40th item in an array you can use array[40]. If you want to reach the 40th item in a linked list, you have to iterate until you reach the 40th item! Which is O(n) time in general.

Special linked lists

Previously we discussed only one type of linked list: one-directional or singly linked list. What else can we have? Based on the task we can create many variations of a linked list, to be more fit to the task we need to solve. Keep in mind that there is no best alternative, it depends on what you need to achieve.

Doubly linked list

Let’s say that it is not enough for us to go from head to bottom (which means one directional only), but we sometimes want to step back a few items. Combine this with a search algorithm imagine the following: you need to search for a given X item. If you have to, you want to check the 3 previous items in the list. In this case you are going and checking for item X, if you found it, you want to step backwards in the list 3 items. One benefit should be highlighted: during deletion or insertion doubly linked list is good because we can reach the neighbors directly.

Circular linked list

The concept is simple, we can reach the first item from the last. It’s like a circle, there is no end. Of course, you still will have a head pointer, there is no change in that. It can be mixed with singly or doubly concept.

Multily linked list

Multi-directional linked list should be a better name. The concept is basically the continuation of the doubly linked list. Imagine a list node where we can reach the next item and previous item – this is the singly / doubly linked version. Add to this node any number of additional references to other nodes. So not only the next and previous can be reach, but whatever node you want. (Sidenote: this seems to be almost a graph data structure, so we rarely use this concept.)

Sorted linked list

As the name suggests we can have a list where the items are always sorted. This can be achieved by inserting an item always to the right place. If we do so, the list will be always sorted. Other option could be to insert an item and then sorting the list, but this is an exponentially worse approach, avoid this.

List with sentinel items

In this case we can have a list with two starting items: the smallest possible node, and the biggest possible node. If we talk about simple integers let’s say minus infinity, and positive infinity. With these items the logic we can apply is that there is no need to check if the list is empty, or we reached the end. There will be always a starting node, and an ending node. Insertion here is easier, because whatever we want to insert will always be smaller than +inf, and will always be bigger than -inf..