# Singly Linked Lists (With Code in C, C++, Java, and Python)

## Introduction

Singly linked lists are a type of a linked list where each node points to the next node in the sequence. It does not have any pointer that points to the previous node. That means we can traverse the list only in forward direction. Figure 1 shows an example of a singly linked list with 4 nodes.

The first item in the list is pointed by a pointer called `head`. Sometimes we use another pointer called `tail` that points to the last item in the list. I am using only `head` in this tutorial to make it simple.

## Operations on a singly linked list

### Insert item at the head

Inserting an item at the head of the list requires 3 steps.

1. Create a new node. Insert the item in the `data` field of the node.
2. Set the new node’s `next` pointer to the node current `head` is pointing to.
3. Make the `head` pointer point to the newly added node.

### Insert an item at the end

To insert an item at the end of the list, use following steps.

1. Seek through the list until the final node is reached.
2. Create a new node using the item to be inserted.
3. Set the last node’s `next` pointer to the newly created node.
4. Set the `next` pointer of the new node to `null`.

### Insert item after another item

To insert an item anywhere between the first and the last node, use the following steps.

1. Seek through the list until the desired node N (after which you want to insert the new node) is found.
2. Create a new node using the item to be inserted.
3. Set the new node’s `next` pointer to the node N.
4. Set N’s `next` pointer to the newly created node.

### Searching an item in the list

Searching for an item in the list requires the following step.

1. Start with the `head`.
2. If the data matches, your search is complete.
3. If the data does not match, go to the next node and repeat step 2.
4. If the `next` of the item is null, we reach the end of the list and data is not found in the list.

### Delete item at the head

For all the delete operations, please keep in mind that, the object needs to be deleted from the heap memory. Languages like Java, Python have Garbage Collector that takes care of this but in C/C++ you need to delete the objects yourself

Use the following steps to delete the item at the `head` of the linked list.

1. Set the `next` pointer of the first node to null.
2. Move the current `head` of the list to the second node.
3. Delete the first node.

### Delete item at the end

Use the following steps to delete the item at the end of the list.

1. Seek through the list until you get to the last node (You might need to keep track of the previous node as well).
2. Set the previous node’s `next` to null.
3. Delete the last node.

### Delete item anywhere in the list

1. Search the list until you find the item you are looking for (You might need to keep track of the previous node as well). Let’s call this node N.
2. Set N’s previous node’s `next` to the N’s next node’s `next`.
3. Delete N.

## Complexities

The complexities of the operations discussed above are summarized in the table below.

OperationComplexity
The complexities given above are for the linked list that has only `head` pointer. If we have `tail` pointer then inserting at the end takes only a constant time.