Introduction : Linked list is a linear and non-indexed data structure. Arrays and List in java , stores the data in contiguous memory locations but linked list stores the data at random locations and link node to another node.
Advantage : Linked list optimize the memory allocation as compare to Arrays and List.If programmer creates an Array with fixed size, even Array is not fully filled , but it will hold the memory location.In case of linked list, wastage of memory locations are very minimal.If we talk about the performance in terms of insertion and deletion, Linked list is more faster than Array and List in java.Like List, size of Linked list is dynamic.
Drawback : Random access is not allowed in Linked list. To access elements, need to traverse through the nodes starting from root node till the element position.Extra memory is required to store the address of next node.
Representation : A linked list is represented by a pointer to the first node (root node)of the linked list.If linked list is empty , then root node will be NULL.Each node in a linked list consists of two parts:
- Data
- Pointer to the next node
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
Types : Majorly, there are three types of linked list.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
We will talk about the properties of all three types of linked list and their implementation in JAVA.In this post, we will write the implementation of Singly Linked List.
Implementation of Singly Linked List : Singly linked list consists of only one pointer to the next node.Each node will have data and only one pointer .We can traverse the singly linked link in forward direction only. Pointer of last node will be always NULL.
We will start with the simpler implementation where we can add the element in linked list and display the data. We are not going to use the Generics now, but later we will have implementation with Generics type.
Node: Node class consists of data and node (pointer to next node). We can override the hashCode(), equals() and toString methods.
package com.study.singlyLinkedList;
public class Node {
private Object data ;
private Node node;
public Node(Object data) {
this.data = data;
}
public Node getNode() {
return node;
}
public void setNode(Node node) {
this.node = node;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
SinglyLinkedList : This class will have root node and size as instance variables. We have method add(Object data) , which will add the element at end of the linked list.
public void add(Object data) :
Steps:
- If data is null, then don’t do anything. This implementation ensure that, it will not allow null entry.
- If node is null, it means size of singly linked list is 0. In this case, create new node and assign it to root node.
- If node is not null, we should get the last node of the singly linked list and set the pointer node of last node as newly created node. This add implementation will have time complexity of O(n) , because to get the last node, we need to traverse through the entire nodes starting from root node. We will optimize the time complexity to add any element in constant time O(1).
- Added supported methods to get last node, next node, size of linked list and toString() method.[ Try Yourself ]
package com.study.singlyLinkedList;
public class SinglyLinkedList {
private int size = 0;
private Node node; // root node
/**
* Add element at last.
*
* @param data
*/
public void add(Object data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node(data);
} else {
Node newNode = new Node(data);
// To add new node, find the last node of the linked list
// and link last node to newly created node.
Node lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Calling the method recursively till next node is not null.
* Next node of last node will be NULL.
* @param node
* @return
*/
private Node getLastNode(Node node) {
Node lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node next(Node node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
@Override
public String toString() {
String represent = "[";
Node nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
}
package com.study.singlyLinkedList;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList linkedList=new SinglyLinkedList();
System.out.println("****** ADDING DATA TO LINKED LIST ******");
linkedList.add(1);
linkedList.add("JHON");
linkedList.add("SMITH");
System.out.println("****** SIZE OF LINKED LIST AFTER ADDING ELEMENT : " +linkedList.size() +" ******");
System.out.println("SINGLY LINKED LIST : "+linkedList);
}
}
Create object of SinglyLinkedList and add some object in main method. After running the main method we could see the below results on console.
****** ADDING DATA TO LINKED LIST ****** ****** SIZE OF LINKED LIST AFTER ADDDING ELEMENT : 3 ****** SINGLY LINKED LIST : [1,JHON,SMITH]
Let’s see how does it look (after adding three elements) in debug mode in eclipse.
Now, we will try to optimize the add operation .Our goal is to add the element in constant time irrespective of size of the linked linked. In above implementation, we need to traverse through all the nodes to find out the last node, hence time complexity became O(n) . To get rid of traversing the nodes every time, we can add one instance variable “lastNode” to SinglyLinkedList class and set the value on every add method call. Refer the below implementation.
package com.study.singlyLinkedList;
public class SinglyLinkedList {
private int size = 0;
private Node node; // root node
private Node lastNode;
/**
* Add element at last.
*
* @param data
*/
public void add(Object data) {
if (data == null) {
return;
}
Node newNode = new Node(data);
if (node == null) {
node = newNode;
} else {
lastNode.setNode(newNode);
}
lastNode=newNode;
size++;
}
private Node next(Node node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
@Override
public String toString() {
String represent = "[";
Node nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
}
In next post, we will create Singly Linked List using Generics.
Hope you like this post. Please give your valuable suggestions/comments.
You may like –
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Implementation of Index based Linked List.
- Reverse a Singly Linked List.
- Find the middle element of a Singly Linked List.
- Merge sort for Linked List in Java.
- Remove duplicate node from linked list.
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
