Compare Two Singly Linked Lists in Java

Singly linked list is a very common data structure which consists of different nodes.

There are some basic operations can be performed on singly linked lists such as add, insert, delete, remove from tail or head.

In addition to above operations a comparison method for two different singly linked lists can be implemented.

In the following sample there two different singly linked lists which are SinglyLinkedList1 and SinglyLinkedList2.

SinglyLinkedList1 consists of nodes node1, node2, node3 and node4 with a head node of headA.

SinglyLinkedList2 consists of nodes node11, node21, node31 and a head node of headB.

For this CompareLists method implementation, following design restrictions applied :

1-) Method takes just the head references for different singly linked lists.
2-) In order to be equal number of nodes in singly linked lists must be the same.
3-) In order to be equal data in each node for different singly linked lists must be the same.
4-) In order to be equal order of nodes in each singly linked lists must be the same.

If the above conditions apply then CompareLists method returns 1 otherwise returns 0.

Package contains following classes.

SinglyLinkedList.java contains Node and SinglyLinkedList classes.

package datastructures.linkedlists;

class Node
{
 int data;
 Node next;
}

public class SinglyLinkedList {

 Node head; 
 public SinglyLinkedList() {
  head = null;
 }
}

SinglyLinkedListUtility.java contains CompareLists method.

package datastructures.linkedlists;


public class SinglyLinkedListUtility {

 public int CompareLists(Node headA, Node headB) {

     if( headA == null || headB == null ) return 0;
     Node walkA = headA;
     Node walkB = headB;
     while( walkA != null )
     {
      if( walkA.data != walkB.data ) return 0;
         walkA = walkA.next;
         walkB = walkB.next;
         if( walkA==null && walkB!=null ) return 0;
         if( walkA!=null && walkB==null ) return 0;
     }
     return 1;
 }
 
}

TestSinglyLinkedListUtility is the unit test class including testCompareLists unit test method.

package datastructures.linkedlists;

import static org.junit.Assert.*;
import org.junit.Test;

public class TestSinglyLinkedListUtility {

 @Test
 public void testCompareLists() {
  
  Node node4 = new Node();
  node4.data = 4;
  
  Node node3 = new Node();
  node3.data = 3;
  node3.next = node4;
  
  Node node2 = new Node();
  node2.data = 2;
  node2.next = node3;
  
  Node node1 = new Node();
  node1.data = 1;
  node1.next = node2;
  
  Node headA = node1;
  
  Node node31 = new Node();
  node31.data = 3;
  node31.next = null;
  
  Node node21 = new Node();
  node21.data = 2;
  node21.next = node31;
  
  Node node11 = new Node();
  node11.data = 1;
  node11.next = node21;
  
  Node headB = node11;

  SinglyLinkedListUtility linkedListUtility = new SinglyLinkedListUtility();
  assertEquals( linkedListUtility.CompareLists(headA, headB), 0 );

 }

}

JUnit execution result is :