##### Problem Statement

Implement a single linked list in Java

###### Solution Explanation

Linked List is one of the heavily used data structure in computer programming. It is basically a linear collection of data elements and is represented by a group of nodes each pointing to the next using a pointer.

```
1 -> 2 -> 3 -> 4 -> 5 -> null
| |
head tail
```

The above sequence is an abstract representation of a single linked list, where each node has a 'value' and a pointer to another node. The first node of the linked list is identified as 'head' and the last node whose pointer stores a null reference is referred to as 'tail'.

There are typically 3 operations which you can perform on a linked list,

- Addition
- Search
- Deletion

There are different types of addition again, like you can add a node at the start, or at the end or at a given index. The same goes with the deletion.

Search is a straightforward operation which takes O(n) time since you have to start with the head, check if each value at every node is the target we are looking for.

###### Node Structure

Represeting the node in your give n programming language is the starting point before you implement a complete linked list. Below is a typical node structure in Java.

```
class Node{
T val;
Node next;
}
```

As you can see, the value can be of any type and the pointer is a self reference to the next node.

To implement addition, search and deletion, you should understand how to nagivate to the next node, changing the link of a node to a different one etc.

Below is the complete java implementation code with annotated method comments,

```
/*
* Author : Venkatesh, Thallam
* Date : 10/09/2017
* Single Linked List Java Implementation
*/
public class LinkedListImpl {
class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
}
Node head = null, tail = null;
public static void main(String[] args) {
LinkedListImpl listImpl = new LinkedListImpl();
listImpl.addNode(10);
listImpl.addNode(20);
listImpl.addNode(30);
listImpl.addNode(40);
listImpl.printLinkedList();
listImpl.addNodeAtStart(50);
listImpl.printLinkedList();
listImpl.removeNode();
listImpl.printLinkedList();
listImpl.removeNodeAtCertainIndex(3);
listImpl.printLinkedList();
}
/*
* Adds node at the end of the current list
*/
public void addNode(int val){
if(head==null){
Node temp = new Node(val);
head = temp;
tail = temp;
}else{
tail.next = new Node(val);
tail = tail.next;
}
}
/*
* Adds node at the start of the current list
*/
public void addNodeAtStart(int val){
if(head==null){
Node temp = new Node(val);
head = temp;
tail = temp;
}else{
Node temp = new Node(val);
temp.next = head;
head = temp;
}
}
/*
* Adds node at the certain index.
*/
public void addNodeAtCertainIndex(int val, int index){
Node temp = head;
int count = 0;
while(temp!=null && ++count!=index)
temp = temp.next;
Node node = new Node(val);
node.next = temp.next;
temp.next = node;
}
/*
* Removes the last node in the given list and updates tail node
*/
public void removeNode(){
Node temp = head;
while(temp.next!=null && temp.next.next!=null){
temp = temp.next;
}
temp.next = null;
tail = temp;
}
/*
* Removes the first node in the given list and updates head node
*
*/
public void removeNodeAtStart(){
//The first node would become zombie and should be garbage collected after the below operation
head = head.next;
}
/*
* Removes the node at the given index in the given list and updates head node
*
*/
public void removeNodeAtCertainIndex(int index){
Node temp = head;
int count = 0;
while(temp!=null && ++count!=index)
temp = temp.next;
temp.val = temp.next.val;
temp.next = temp.next.next;
}
/*
* Checks if a node with the given value exist in the list, returns true or false.
* Alternatively you can return the index too.
*/
public boolean search(int target){
Node temp = head;
while(temp!=null){
if(temp.val == target)
return true;
}
return false;
}
/*
* Checks if a node with the given value exist in the list, returns the index of the given value in the list.
*/
public int searchAndReturnIndex(int target){
Node temp = head;
int count = 0;
while(temp!=null){
count++;
if(temp.val==target) return count;
}
return -1;
}
/*
* Prints the current list
*/
public void printLinkedList(){
System.out.println();
Node temp = head;
while(temp!=null){
System.out.print(" "+temp.val);
temp = temp.next;
}
}
}
```

###### Time Complexity

The time complexity for each of the operations is,

- Addition - O(1)
- Addition at Index - O(n) where n is the number of elements.
- Removal - O(1)
- Removal at Index - O(n) where is the number of elements.
- Search - O(n) where n is the number of elements.

Look at more problems involving linked lists.