## 1. Introduction

The singly linked list is a common data structure implemented in most high-level programming languages. For instance, these are implementations of singly linked lists:

- C++ STL type std::foward_list
- Scala and F# type List

In its most basic form, a linked list consists of a collection of nodes. **Each node contains data and a reference to the next node**.

In this tutorial, we’ll learn how to find the th element of the singly linked list by traversing through the list.

## 2. Algorithm to Find the *nth* Element

We are interested in implementing a function that gets the th element of a linked list. How might we write such a function? To get the th element, we must traverse through the list.

We introduce an algorithm for getting the element with index , of a singly linked list. In the subsequent section, we shall go over each of the important steps in a structured manner.

Consider the following pseudo-code:

```
algorithm GetItem(head, n):
// INPUT
// head = the reference to the linked list
// n = the index of the node to be fetched
// OUTPUT
// Returns the data of the node at index n
current <- head
i <- 0
// Iterate until the end of the linked list
while current != null:
if i = n:
// We finished counting to n and are done
return current.data
// Move current to the next successive node
current <- current.next
// Increase the counter by 1
i <- i + 1
```

## 3. A Walk-Through of *GetItem(Head,n)*

We begin at the head of the linked list.

Our initial setup is as follows:

We take an empty pointer *current* and set it to refer to the head node – the st node of the linked list. *current* always refers to our current position in the linked list.

*current.next *points to the successive node – the nd node of the linked list. If we assign *current = current.next, *this will move *current* to the right. The below snap is just after current is moved to the right:

Executing *current = current.next *multiple times in a while loop allows us to traverse through the linked list. However, **we must be careful not to go beyond the end of the linked list**. If *current = null, *invoking *current = current.next *on a null object will cause our program to crash. So, we write the boundary condition *current!=null* to control the maximum number of iterations.

The logic so far helps us move through the list. However, **it would be good to keep a track of the index we are at**. Hence, we use a counter-variable *i *and count to *n*. First, we initialize *i=0, *and inside each iteration, we check if the counter *i* equals *n*. If this condition is true, we return the data inside the current node to the caller function. If false, we proceed with the next iteration, moving *current *to the next successive node and increasing the value of the counter variable *i *by .

If the control reaches the statement following the end of the while-loop, it implies that we have reached the end of the list before counting to *n. *

## 4. Algorithm to Find the *nth* Element From the Tail of the List

We can build upon the above basic technique to find the th element from the end of the singly linked list. To be consistent, we use the following convention. We shall refer to the tail of the linked list as the element having index , the last but one element as having index , and so forth.

We are interested in writing a function that takes the *head* of the linked list as the first argument and an index () as the second argument.

Consider the following pseudo-code for getting the element with index , where of a linked list:

```
algorithm GetItemFromEnd(head, n):
// INPUT
// head = the reference to the linked list
// n = the index of the node to be fetched from the end
// OUTPUT
// Returns the data of the node at index n from the end
runner <- head
i <- 0
// Iterate until the end of the linked list
while runner != null:
if i = n:
// We finished counting to n
break
// Move runner to the next successive node
runner <- runner.next
// Increase the counter by 1
i <- i + 1
if runner = null:
Print the message 'The list is smaller than n elements'
return
// Iterate until runner points to the tail of the list
trail <- head
while runner.next != null:
runner <- runner.next
trail <- trail.next
return trail.data
```

## 5. A Walk-Through of *GetItemFromEnd(head,n)*

Let’s walk through the important steps of the algorithm introduced in the previous section. We take an empty pointer *runner *and initialize it to refer to the *head* node of the linked list. We now traverse through the list, moving *runner* to the node with index .

At this point, we may have already reached the end of the linked list, in which case *runner = null*. In such a situation, we abort and print a message to the user that the list is too small. If this is not the case, we take an empty pointer *trail* and set it to refer to the head node of the list.

**The distance between the runner and trail pointers is equal to** . So, our setup is as follows:

**Now, we move both – the runner and the trail pointers to their respective successive nodes iteratively**. Throughout these iterations, the distance between the

*runner*and the

*trail*is kept constant. Thus, when

*runner*refers to the tail of the linked list, the

*trail*pointer should point to the th node from the end of the list.

The below snap depicts the situation, when *runner* has reached the end of the list, for the case :

## 6. Implementation in Python

### 6.1. Creating the Classes

Python’s built-in list data structure is a dynamic array, offering indexed access to its elements. And so, the algorithms we have talked about so far do not apply to them; to write an implementation for the algorithms, we first need to create our own List Data Structure.

To do this, we need to use classes that are not dissimilar to classes in other languages like Scala. There are many tutorials on the internet, from comprehensive to fun.

At a minimum, we’ll need to create a *Node* class to store the data and a *LinkedList* class to maintain the state of the list:

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
```

With these definitions, we have set the foundation for implementing the algorithms to find the nth element from the beginning to the end of the list.

### 6.2. Implementing and Using *GetItem* Method

Python is sometimes referred to as executable pseudocode, and we can see why by implementing the *GetItem* algorithm almost one-to-one, with only minor differences:

```
class LinkedList:
# ... [previous methods]
def get_item(self, n):
runner = self.head
count = 0
while runner:
if count == n:
return runner.data
count += 1
runner = runner.next
print("Error: Index out of bounds")
return None
```

The only appreciable difference from the pseudocode is that the head is implicit in the object, the casing difference in the name to match the naming practices of Python, and returning *None* when the list has fewer elements than the one we are looking for.

Using it is also very simple:

```
# Example usage of the refined LinkedList
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
# Try to get the 4th item (index starts at 0)
item = ll.get_item(3)
if item is not None:
print("The 3th item in the list is:", item)
```

### 6.3. Implementing GetItemFromEnd Algorithm

The implementation of the method to find an element from the end is again a one-to-one translation from the pseudocode:

```
class LinkedList:
# ... [previous methods]
def get_item_from_end(self, n):
runner = self.head
trailer = self.head
count = 0
while count < n:
if runner is None:
print("Error: Index out of bounds")
return None
runner = runner.next
count += 1
while runner:
runner = runner.next
trailer = trailer.next
return trailer.data
```

And using it is as simple as with *GetItem*:

```
item = ll.get_item_from_end(3)
if item is not None:
print("The 3th item from the end of the list is:", item)
```

## 7. Conclusion

In this article, we learned about the algorithms to get an element with index of a linked list. To recap, first, retrieving an element from the beginning of the list requires initializing a *current* pointer to *head*. It should then be moved to its successor node times. Second, when retrieving an element from the end of the list, we set up two pointers *runner* and *trail*, a distance apart. We then move both pointers iteratively to their successor nodes until *runner.next=null*.