In this article I’m going to show you why we can’t use indexing function by default on self made linked lists. What is the theoretical problem with indexing, and how can we solve it in two ways – using only self-made components.

Problem

I already wrote about linked list data structure (what is the basic concept, how we can implement it etc.) which you can read here. However, dealing with linked lists one disadvantage can be felt immediately (compared to arrays), which is the lack of indexing possibility. In this case we can’t write something like this WriteOut(myLinkedList[100]), because linked lists only have Traverse and Search methods.

Solution

Indexing functionality can be viewed from two approaches. One is when we need to get an item eg. WirteOut(myArray[10]), and one when we need to set an item eg. myArray[10] = 990.

Solution A

As a first solution we can use simply methods created for this purpose. One method will be used for getting an item based on the index, and one will be used for setting an item based on the index.

Searching for an item

In this code we will return back the content of the searched node, if it exists. If not, we return an exception (eg. if the index number is too big / small). After this we can use this method like myLinkedList.SearchForItem(10) which will return us back the 10th item from the list if it exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Note: this code is inside the MyLinkedList<T> class
private T SearchItem(int index)
{
    ListItem p = head;
    int count = 0;
    while (p != null && count < index)
    {
        p = p.next;
        count++;
    }

    if (p != null && count == index)
        return p.content;
    else
        throw new Exception("ERR : Index was not valid.");
}

Modifying an item

In this code we will look for an item based on the index, and if we have it we will modify the content of that. After this we can call the method and use it like myLinkedList.ModItem(10, 320). In this case we will look for the 10th item and (if we have it) change the value from whatever it was previously to 320.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Note: this code is inside the MyLinkedList<T> class
private void ModItem(int index, T newValue)
{
    ListItem p = head;
    int count = 0;
    while (p != null && count < index)
    {
        p = p.next;
        count++;
    }

    if (p != null && count == index)
        p.content = newValue;
    else
        throw new Exception("ERR : Index was not valid.");
}

Solution B

The problem with solution A is that it still not let us use the brackets like we can use them with an array. So solution B will solve this problem for us – using the methods we created in solution A!

In order to be able to use the [] operator, we have to modify our linked list class. We have to place this small code snippet inside the class. As you can see, the syntactical part is very simple… but the logic beneath must be created (SearchItem and ModItem methods). After this we can easily use the [] operators like myLinkedList[10] = 320. Based on what we want to do (get or set), it will automatically call the corresponding method.

1
2
3
4
5
6
// Note: this code is inside the MyLinkedList<T> class
public T this[int i]
{
    get { return SearchItem(i); }
    set { ModItem(i, value); }
}

Waltkhrough

For more detailed information, you can watch how I coded this extension in this waltkhrough video below.

Downloadables

Downloadables

You can download the full solution by clicking here.

Or use CLI with these commands and then look for the LIST folder:

1
2
cd Desktop && mkdir Downloaded_Project && cd Downloaded_Project
git clone https://github.com/data-structures.git