Java sort linked list of objects
|
This Tutorial Explains What is a Linked List Data Structure in Java and How to Create, Initialize, Implement, Traverse, Reverse and Sort a Java Linked List: Show
In Java, a LinkedList is a data structure that stores elements in a non-contiguous location. It is a linear data structure. Each data item is called a Node and each node has a data part and an address part. The address part stores the link to the next node in the LinkedList. => Visit Here To See The Java Training Series For All. What You Will Learn:
LinkedList In JavaGiven below is the general Layout of LinkedList: As shown in the above representation of LinkedList, each item in the LinkedList is the Node. Each node has two parts, the first part stores the data and the second part has a reference or pointer or address of the next node in the LinkedList. This arrangement is necessary as the data in LinkedList is stored in non-contiguous locations, unlike Arrays. The Head of the LinkedList is a pointer that contains the address of the first element in the LinkedList. The last node in the LinkedList is the tail. As shown in the figure above, the address part of the last node in the LinkedList is set to Null indicating the end of the LinkedList. The above diagram represents a Singly-linked List that stores the address of only the next node in the LinkedList. There is another version known as Doubly Linked List whose each node has three parts:
The previous address of the first element in the LinkedList will be set to Null while the next pointer of the Last element in the LinkedList is set to Null. Representation Of Doubly Linked List: As shown in the above representation, each node in the doubly linked list has pointers to its previous and next node (thus represented without arrows). The previous pointer of the first node points to null while the next pointer of the last node points to null. In this LinkedList tutorial, we will deal mostly with the singly linked list. We will discuss the doubly linked list in our next tutorial. Java LinkedList ClassIn Java, the linked list is implemented by the LinkedList class. This class belongs to the java.util package. The LinkedList class implements the List and Deque interfaces and inherits the AbstractList class. Given below is the class hierarchy of the LinkedList class. The above diagram shows the hierarchy of the LinkedList class. As shown, LinkedList class implements the List and Deque interfaces. As already mentioned, LinkedList class is a part of the java.util package. Hence you should be able to use the LinkedList class in your program by including one of the following statements in your program. import java.util.*;Or import java.util.LinkedList;So based on the above hierarchy, a typical definition of LinkedList class is as follows: public class LinkedListEnlisted below are some of the characteristics of the LinkedList class that you should remember:
How To Create A Linked List In JavaBefore we move on to creating a linkedlist in Java, lets first discuss a linked list node in Java. As already discussed, a linked list consists of nodes. Thus in Java, we can represent a LinkedList as a class with its Node as a separate class. Hence this class will have a reference to the Node type. This is shown as below: To create an object of type LinkedList, there are two main constructors as follows: #1) LinkedList() The general syntax for this constructor is: LinkedListThe above statement creates an empty LinkedList. For example, LinkedListThis will create an empty linked list named l_list. #2) LinkedList(Collection c) The general syntax is: LinkedListThe above statement creates a LinkedList with elements from the collection c as its initial elements. Like other list data structures that we have already seen, the linked list can also be initialized using the add method, Arrays.asList () method or by using the constructor with the collection as an argument. Linked List Implementation In JavaGiven below is a simple example of a LinkedList data structure in Java. In this example of implementation, we will use the add method and asList method to initialize the LinkedList objects. import java.util.*; public class Main{ public static void main(String[] args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList<Integer> intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println("Contents of first LinkedList: " + intList); //create an empty list LinkedList<String> colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add("Red"); colorsList.add("Green"); colorsList.add("Blue"); colorsList.add("Cyan"); colorsList.add("Magenta"); // print the LinkedList System.out.println("\nContents of second LinkedList: " + colorsList); } }Output: Contents of first LinkedList: [10, 20, 30, 40, 50] The above program shows the creation and initialization of the LinkedList. First, we create a LinkedList of type Integer and provide an array of Integers converted to list using the asList method as initial values for the LinkedList. Next, we create an empty LinkedList of type String and then using the add method, we add values to the LinkedList. Finally, we display both the LinkedList objects as a string. Traverse/Print Linked List In JavaTo print the contents or carry out any operations on the elements of the LinkedList, you need to traverse through its elements. We have already seen these methods in our previous tutorials. In this section, we will discuss the examples of each with respect to LinkedList. Using for loopimport java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList<String> colorList = new LinkedList<>(); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); // Using for loop,print the contents of the LinkedList System.out.println("LinkedList elements using for loop:"); for(int i=0; i < colorList.size(); i++) { System.out.print(colorList.get(i) + " "); } } }Output: LinkedList elements using for loop: Using forEach Loopimport java.util.LinkedList; class Main { public static void main(String[] args) { // Create a LinkedList and initialize it LinkedList<String> colorList = new LinkedList<>(); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); // Using forEach loop,print the contents of the LinkedList System.out.println("LinkedList elements using forEach loop:"); for(String color:colorList) { System.out.print(color + " "); } } }Output: LinkedList elements using forEach loop: Using Iteratorimport java.util.*; public class Main{ public static void main(String args[]){ //declare a LinkedList object LinkedList<String> l_list=new LinkedList<String>(); //Add elements to LinkedList l_list.add("Red"); l_list.add("Green"); l_list.add("Blue"); l_list.add("Yellow"); //declare an iterator for the LinkedList Iterator<String> itr=l_list.iterator(); System.out.println("The contents of Linked List:"); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + " "); } } }Output: The contents of Linked List: LinkedList MethodsLinkedList class provides API that supports various methods to manipulate the Linked list. We have tabularized the methods in LinkedList API below. We will discuss the main operations/methods in the following section.
The below Java program demonstrates the various methods that we listed above. Output: Linked list : [A, B, C, D, G, E, F] The above program demonstrates various methods of LinkedList class. First, we declare a LinkedList of type String. Then we use various versions of add method like add, andFirst, addLast, addAll, etc. to populate the LinkedList with values. Here we can add the element directly at the end of the list or add the element at a specified position in the list. We also use the addFirst method to add an element at the beginning of the list and addLast to add an element at the end of the list. Then we perform remove operations on the LinkedList like remove, removeFirst, removeLast, etc. For remove method, we can either specify the element to be removed or we can specify the index or the position in the LinkedList at which the element is to be removed. The methods removeFirst and removeLast remove the first and last element in the list respectively. Then we search the list for a particular element using the contains method. Next, we use the size() method to retrieve the size or length of the LinkedList. Then we use get /set methods to retrieve the value at a particular index in the list and then replace a value at a specified position in the list. Finally, we convert the LinkedList to an Array using the toArray method. Reverse Linked List In JavaTo reverse a linked list in Java, we use the descendingIterator () method that returns a reverse iterator for the list. We can then use this iterator to traverse through the list and display elements. The below program reverses the linked list using the descendingIterator () method. import java.util.*; public class Main{ public static void main(String args[]){ //create a LinkedList object LinkedList<String> l_list=new LinkedList<String>(); l_list.add("Pune"); l_list.add("Mumbai"); l_list.add("Nagpur"); System.out.println("Linked List : " + l_list); System.out.println("Linked List in reverse order:"); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + " "); } } }Output: Linked List : [Pune, Mumbai, Nagpur] In the above program, we declare a linked list and then print it. Then we get a reverse iterator and then step through the list using it and display each element. The output shows the linked List contents, first in the order the elements are added and then the output shows the contents in reverse order. Sort A Linked List In JavaLinkedList class objects can be sorted using Collections.sort () method. This method provides two versions with or without using a comparator. When the Collections.sort () method is called without a comparator, the collection is sorted in the natural order. When the comparator is used with this method, we can define our own sorting criteria by overriding the compareTo method. The below Java program sorts a LinkedList using Collections.sort (). Here we sort arrays using natural ordering as well as using a comparator. import java.util.*; public class Main{ public static void main(String args[]) { // create and initialize the LinkedList object LinkedList<String> l_list = new LinkedList<>(); l_list.add("Jan"); l_list.add("Feb"); l_list.add("Mar"); l_list.add("Apr"); l_list.add("May"); l_list.add("Jun"); //print original unsorted linkedlist System.out.println("Original LinkedList (unsorted): " + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println("\nLinkedList (sorted in natural order): " + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator<String>() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println("LinkedList (sorted using Comparator): " + l_list); } }Output: Original LinkedList (unsorted): [Jan, Feb, Mar, Apr, May, Jun] Remove DuplicatesTo remove duplicates, you need to traverse each node and compare it with the next node. If both nodes are the same then we skip one node and move to the next. In this manner, after traversing each and every node and getting rid of duplicate nodes, we will get the resultant list that is without any duplicate elements. Given below is a Java program to remove duplicates. class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } }class Main{ public static void main(String[] args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println("Original Linkedlist: "); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println("LinkedList after removing duplicates: "); l_List.print(); } }Output: Original Linkedlist: In the above program, we have a linked list class created to remove duplicates. We also have a class to define each node. In other words, the nodes in the list are the objects of this class node. We have a method to add the node to a linked list. Then in the removeDuplicate method, we traverse through each node in the linked list starting from the head and compare each subsequent node for the duplicate. If a duplicate is found, we skip that node and proceed to the next node. This way the ist is built by skipping the duplicate nodes and the changed list is printed using the print () method. Circular Linked List In JavaA circular linked list is a list that has its tail or last node connected back to the head or the first node. The below diagram shows the Circular Linked List In Java. As shown in the above diagram, the address part of the last node or tail of the linked list is not set to null. Instead, it points back to the first node or head of the list thus forming a circular linked list. The below program implements a circular linked list wherein we have to manipulate individual nodes of the linked list. class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println("The List is empty"); } else { System.out.println("Circular linked list nodes: "); do{ //Print each node of the linked list System.out.print(current.data + " "); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String[] args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } }Output: Circular linked list nodes: Java 8 LinkedListThough there are no more features added specifically to LinkedList class in Java 8, it still introduced streams to manipulate data. The below program shows the use of Java 8 stream to display LinkedList. import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { //create a LinkedList and initialize it to values List<String> colorsList = new LinkedList<>(); colorsList.add("Red"); colorsList.add("Green"); colorsList.add("Blue"); colorsList.add("Cyan"); colorsList.add("Magenta"); //convert List to stream & print it System.out.println("The contents of LinkedList:"); colorsList.stream().forEach(System.out::println); } }Output: The contents of LinkedList: Frequently Asked QuestionsQ #1) When is the Linked List used in Java? Answer: As it is faster than collections like ArrayList in modification operations, it should be used in applications that require frequent addition/deletion operations. For applications that have mostly read-only data, ArrayList or similar collections can be used. Q #2) What is ListNode? Answer: A ListNode is a basic class associated with a linked list in Java and represents information associated with a single element or a node. Each ListNode consists of data and a pointer or reference to the next element. Q #3) Does the Linked List allow null values? Answer: Yes, the linked list allows any number of null values. Q #4) What are the Advantages of a Linked List? Answer: Some of the advantages are:
Q #5) What is the Application of the Linked List? Answer: It is used mostly in the following applications:
Q #6) What are the Limitations of a Linked List? Answer: Some of the limitations are:
ConclusionIn this tutorial, we have learned the basic linked list data structure. Then we moved on java.util.LinkedList class provided in Java. We discussed this class in detail including its constructors, methods, etc. We also have discussed some special operations related to Linked lists like sorting, reversing a list, removing duplicates, circular linked list, etc. In our next tutorial, we will discuss specific features of the doubly linked list. => Check Out The Complete Java Training Guide Here. Recommended Reading
|
