In this article you will learn:
- Create user defined linked list.
- Use of generics, Enum and Comparable.
- Basic design principle.
Problem Statement:
Create custom linked list (i.e. don’t use java’s default linked list) with sorting facility. Sorting facility means data should be inserted in the specified order either ascending or descending.
The Background:
Now days, one of the most famous question is to create your own linked list. Also data should be inserted in some specified order.
Techniques used to impress Interviewer:
- Followed code to interface design principle- to create generalized API.
- Use of generics to make code independent of specific data type.
- Use of ENUM’s to provide type safety.
- Use of Comparable- to provide sorting facility.
Explore this:
Let’s start with basics. We will create following classes in given order:
- Concrete Class: Node- This is most basic part of linked list which contains data and information about next node.
- Enum: SortOder- This ENUM class will contain sort orders to provide.
- Interface: CustomLinkedList- This will be template creating methods for our linked list.
- Concrete class: CustomLinkedListimpl- This will have logic to create our linked list using class node.
- ConcreteClass: CustomLLClient- This will client class to show created linked list.
To learn basics of linked please follow this.
The code is as follows:
package customlinkedlist;
public class Node<T> {
private Comparable<T> data;
private Node<T> next;
public Comparable<T> getData() {
return data;
}
public void setData(Comparable<T> data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
package customlinkedlist;
public enum SortOrder {
ASC,
DSC
}
package customlinkedlist;
public interface CustomLinkedList<T> {
Node<T> insert(Comparable<T> data);
}
package customlinkedlist;
public class CustomLinkedListimpl<T> implements CustomLinkedList<T> {
private Node<T> head;
private SortOrder sortOder;
public CustomLinkedListimpl(SortOrder sortOrder) {
head = new Node<T>();
head.setNext(null);
head.setData(null);
this.setSortOder(sortOrder);
}
public Node<T> insert(Comparable<T> data) {
Node<T> nodeToInsert = new Node<T>();
if (head.getNext() == null) {
nodeToInsert.setData(data);
nodeToInsert.setNext(null);
head.setNext(nodeToInsert);
} else {
Node<T> tempNode = head;
while(tempNode.getNext() != null) {
if (SortOrder.ASC.equals(this.getSortOder()) && data.compareTo((T) tempNode.getNext().getData()) < 0) {
break;
} else if (SortOrder.DSC.equals(this.getSortOder()) && data.compareTo((T) tempNode.getNext().getData()) > 0) {
break;
}
tempNode = tempNode.getNext();
}
nodeToInsert.setData(data);
nodeToInsert.setNext(tempNode.getNext());
tempNode.setNext(nodeToInsert);
}
return nodeToInsert;
}
public void printList() {
if (head == null) {
System.out.println("List is null.");
return;
}
Node<T> tempNode = head.getNext();
System.out.print(tempNode.getData());
while (tempNode.getNext() != null) {
tempNode = tempNode.getNext();
System.out.print(" --> " + tempNode.getData());
}
}
public SortOrder getSortOder() {
return sortOder;
}
public void setSortOder(SortOrder sortOder) {
this.sortOder = sortOder;
}
}
package customlinkedlist;
public class CustomLLClient {
public static void main(String[] args) {
System.out.println("Integer LinkedList");
CustomLinkedListimpl<Integer> intcustomLinkedList = new CustomLinkedListimpl<Integer>(SortOrder.ASC);
intcustomLinkedList.insert(8);
intcustomLinkedList.insert(3);
intcustomLinkedList.insert(5);
intcustomLinkedList.insert(2);
intcustomLinkedList.printList();
System.out.println("\n\nString LinkedList");
CustomLinkedListimpl<String> customLinkedList = new CustomLinkedListimpl<String>(SortOrder.DSC);
customLinkedList.insert("Tango");
customLinkedList.insert("Alpha");
customLinkedList.insert("Ram");
customLinkedList.insert("Romeo");
customLinkedList.printList();
}
}
The result is:
Integer LinkedList</pre> <pre>2 --> 3 --> 5 --> 8 String LinkedList Tango --> Romeo --> Ram --> Alpha
What Next:
Suggestions are most welcome. Let me know if there is any doubt as well.
Print this Article:
Printer friendly version of this document is available: Create custom linked list
Happy Reading.
Nirbhaya Bhava!!
Tanzeem.
