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:
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 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:
- head: Object of type Node.
- 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.
Top comments (0)