LinkedList Implementation of the most critical methods using Java generics.
Tags: java, linkedlist, datastructures, bigo
Published: 2022-07-10 13:31:30

## Introduction
Hi guys!
In this post, I will explain the LinkedList data structure Briefly and try to implement its most critical methods using Java programming language. So, you will know how it works in the memory and how it implements its main methods.
We will implement it using Java's generics, so, we can store any type of data on our LinkedList.

## Linked List
A Linked List Is Linear Data Structure that store values in nodes. Each node contains two parts: **Data** and **Reference for the next node**.

Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

- Node: Each node of a linked list can store data called an 
        element.

- Next: Each node of a linked list contains a link(Reference) to 
         the next node is called Next.

- Head: Each LinkedList contains a head that points to the first 
        node in the list and to NULL if the list is empty.

This image will illustrate the Linked List concepts:


![LinkedList](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xfvxaev8dlzzkih4e3fr.jpg)

## Basic Operations

- Insertion: Adds an element to the LinkedList.
- Deletion: Delete an element from the LinkedList.
- Get: Get the element's data specified in an array-like index (0-length)
- Clear: Clear the LinkedList and make it empty.

_Now we will start implementing all these operations in Java from scratch._

## Node<T> class
First, we will define the Node class that contains two parts: data and next

```
class Node<T> {
        T nodeData;
	Node<T> next; // points to the next node

// Constructor to instantiate the node object with default values
        Node(T data) {
	   this.nodeData = data;
	   next = null;
	}
  }
```

## LinkedList class
Second, we will define the LinkedList class that contains:

1. head: Object of type Node<T>.
2. length: An integer value (length of the list).

```
public class MyLinkedList<T> {
	Node<T> head;
	private int length = 0;
// Constructor 
MyLinkedList() {
		this.head = null;
	}
}
```

_Now we will start implementing the basic operations_

## Insertion 
Insert has two methods:
First `public final void add(T data)` insert to the end of the list
And 
`public final void add(T data, int pos)` Inserts in Specific Position.


```
// Insert on the end of the LinkedList
	// Complexity: O(n)
	public final void add(T data) {
		Node<T> newNode = new Node<T>(data);
		
		if(this.head == null) {
			this.head = newNode;
			newNode.next = null;
		} else {
			Node<T> pointer = this.head;
			
			while (pointer.next != null) {
				pointer = pointer.next;
			} 
			
			pointer.next = newNode;  
			newNode.next = null;
		}
		this.length++;
	}
	// Insert in Specific Position
	// Complexity: O(n)
	public final void add(T data, int pos) {
		if(pos == 0) {
			this.addFirst(data);
			return;
		}
		if(pos < 0 || pos > this.length) {
			System.out.println("Error: Out of range");
		} else {
			Node<T> newNode = new Node<T>(data);
			Node<T> pointer = head;
			
			for(int i = 1; i < pos; i++) {
				pointer = pointer.next;
			}
			newNode.next = pointer.next;
			pointer.next = newNode;
			this.length++;
		}
	}
	
	// Insert First (begging of the list)
	public final void addFirst(T data) {
		
		Node<T> newNode = new Node<T>(data);
		
		newNode.next = head;
		head = newNode;
		this.length++;
	}
```

## Deletion

```
// Delete from last of LinkedList 
	// Complexity: O(n)
	public void remove() {
		if(isEmpty()) {
			System.out.println("Sorry, List is empty!!");
		} else if(this.length == 1) {
			head = null;
			System.out.println("Removed Successfully");
			this.length = 0;
		} else {
			Node<T> pointer = head;
			
			while(pointer.next.next != null) {
				pointer = pointer.next;
			}
			pointer.next = null;
			this.length--;
			System.out.println("Removed Successfully");
		}
	}
	// Remove LinkedList Element from specific position
	// Complexity: O(n)
	public void remove(int pos) {
		if(pos < 0 || pos >= length) {
			System.out.println("Error: Position is out of range");
		} else if (pos == length - 1) {
			remove();
		} else {
			if (pos == 0) {
				removeFirst();
				return;
			}
			Node<T> pointer = head;
			
			for(int i = 1; i < pos; i++) {
				pointer = pointer.next;
			}
			pointer.next = pointer.next.next;
			length--;
		}
	}
	// Remove the first element in the LinkedList
	public void removeFirst() {
		head = head.next;
		length--;
	}
	// Get LinkedList element's Data for specific Index
	// Complexity: O(n)
	public T get(int index) {
		if(index < 0 || index >= length) {
			return  null;
		}
		Node<T> pointer = head;
		for(int i = 0; i < index; i++) {
			pointer = pointer.next;
		}
		return pointer.nodeData;
	}
```

## Get
This method returns the data contained by the node specified by the index parameter.

```
// Get LinkedList element's Data for specific Index
	// Complexity: O(n)
	public T get(int index) {
		if(index < 0 || index >= length) {
			return  null;
		}
		Node<T> pointer = head;
		for(int i = 0; i < index; i++) {
			pointer = pointer.next;
		}
		return pointer.nodeData;
	}
```

## Clear

```
public final void clear() {
		this.head = null;
		length = 0;
	}
```

## Additional methods

```
// Get LinkedList Length
	public int getLingth() {
		return this.length;
	}
	// Return true if the LinkedList is empty
	public boolean isEmpty() {
		if (this.length == 0) return true;
		return false;
	}
	
	// Convert LinkedList to string
	// Complexity: O(n)
	public String toString()
    {
 
        String S = "{ ";
 
        Node<T> X = head;
 
        if (X == null)
            return S + " }";
 
        while (X.next != null) {
            S += String.valueOf(X.nodeData) + " -> ";
            X = X.next;
        }
 
        S += String.valueOf(X.nodeData);
        return S + " }";
    }

```

## Print method

```
// Print all List elements
	// Complexity: O(n)
	public final void print() {
		Node<T> pointer = head;
		
		while (pointer != null) {
			System.out.println(pointer.nodeData);
			pointer = pointer.next;
		}
	}
```
Hope this post is helpful.

I'm sorry if I made any mistakes, and thank you for reading.

BR
Ahmad Mukahal.