Create User Defined Linked List with Sorting Facility

In this article you will learn:

  • Create user defined linked list.
  • Use of generics, Enum and Comparable.
  • Basic design principle.

maxresdefault

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:

  1. Concrete Class: Node– This is most basic part of linked list which contains data and information about next node.
  2. Enum: SortOder– This ENUM class will contain sort orders to provide.
  3. Interface: CustomLinkedList– This will be template creating methods for our linked list.
  4. Concrete class: CustomLinkedListimpl– This will have logic to create our linked list using class node.
  5. 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s