# Traverse, insert, delete, reverse and find nth last element in singly linked list

 Category: Data Structure And Algorithms Tags:

## Introduction

We introduced Doubly Linked List in previous article which had two pointers to move forward and backward from any node. Singly linked list is most common linked list used in many applications like queues and moves only forward from a given node.

## Implementation

For Singly linked list we will use following node structure which contains Key and one forward pointer which will point to next node in linked list.

public class Node
{
public Node(int key)
{
Key = key;
}
public int Key;
public Node Next;
}

{
Node Head { get; set; }
void Insert(int key);
void Delete(int key);
void Reverse();
Node FindNthFromEnd(int n);
}

Lets implement all the methods in interface one by one.

{
public Node Head { get; set; }

{
while (temp != null)
{
Console.WriteLine(temp.Key);
temp = temp.Next;
}
}
}

Print is simple traversal of linked list which uses next pointer to reach end of the linked list. We traverse until reached null because last node of a linked list points to null. Lets implement next method in above class.

public void Insert(int key)
{
var node = new Node(key);
{
return;
}

while(temp.Next != null)
{
temp = temp.Next;
}
temp.Next = node;
}

Insert is similar to traversal where we find last element of linked list and add a new node at the end by pointing next pointer of last element to a new node.

public void Delete(int key)
{
return;

{
return;
}

while (temp != null)
{
if (temp.Key == key)
{
previous.Next = temp.Next;
return;
}
previous = temp;
temp = temp.Next;
}
}

In delete we would need one extra pointer to keep track of previous node while traversing. Once target node is found we can bypass the next pointer of previous node to the next node of current node. So linked list: Head->1->2->3->4->null if we want to delete 2 then we have to point 1 directly to 3.

public void Reverse()
{
Node prev = null;
Node next;

while (current.Next != null)
{
next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
current.Next = prev;
}

Reverse requires three pointers previous, current and next. We have to change direction from current to previous at each node. So if linked list is: Head->1->2->3->4->null, direction at 2 is 2->3 it should be now changed to 2->1 same way at 3 it should be now 3->2 instead of 3->4. If we go on the list will be reversed like: null<-1<-2<-3<-4<-Head.

public Node FindNthFromEnd(int n)
{

while (n > 1)
{
fastForward = fastForward.Next;
n--;
}
while (fastForward.Next != null)
{
fastForward = fastForward.Next;
normal = normal.Next;
}

return normal;
}

To find nth element from end we have to have 2 pointers one is fast forwarded pointer which is already n times ahead of normal pointer. Then we iterate both of the pointers until fast forwarded pointer is reached to the end and we will have our n'th element from last in normal pointer. Lets run everything:

static void Main(string[] args)
{
// Insert

// Print
Console.WriteLine("Lisnked list elements:");

// Delete
Console.WriteLine("Lisnked list elements after delete:");

// nth element from the end
Console.WriteLine(\$"Lisnked list 2nd last element is: {node.Key}");

// Reverse
Console.WriteLine("Lisnked list elements after reverse:");
}

Output

Lisnked list elements:

1

2

3

4

Lisnked list elements after delete:

1

3

4

Lisnked list 2nd last element is: 3

Lisnked list elements after reverse:

4

3

1

## Conclusion

Most of the operations on linked list can be done in O(n) time. Linked list is most basic data structure when you start learning data structures and algorithms. There are many applications are done using linked lists i.e. Stack, Queue, Dynamic Memory Allocation etc.

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 158 Questions: 16 Given Best Solutions: 16 *