I have this basic class structure: public class SinglyLinkedList { private Link
ID: 3916210 • Letter: I
Question
I have this basic class structure:
public class SinglyLinkedList {
private Link head;
private Link tail;
private int size;
private static class Link {
private E data;
private Link next;
}
}
The efficiency should be O(n+m) method that could appear in SinglyLinkedList that “splices” one linked list into another.
public SinglyLinkedList splice(int atIndex, SinglyLinkedList other)
The method will take the nodes of the other SinglyLinkedList and splice copies of them into this list at the given index. If atIndex is is not a valid index, throw an exception. And should return this list.
For example, if in A I have 1 , 2, 3
And B has 4,5,6
When i do a.splice(1, b), i need to get 1,4,5,6,2,3.
And the code that I write should have the efficiency as O(n+m)
Explanation / Answer
Here is the implementation of required method you asked.
/**
* method to splice the other list into this list in the given index
*
* @param atIndex
* - index of insertion
* @param other
* - other singlylinked list
* @return the new list
* @throws Exception
* if index is out of range
*/
public SinglyLinkedList splice(int atIndex, SinglyLinkedList other)
throws Exception {
if (atIndex < 0 || atIndex > size) {
throw new Exception("Invalid index!");// invalid index
}
/**
* creating a new list
*/
SinglyLinkedList<E> list = new SinglyLinkedList();
/**
* getting a reference of head node of this list
*/
Link<E> node = this.head;
/**
* adding items before the given index of this list to the new list
*/
for (int i = 0; i < atIndex; i++) {
list.insert(node.data);
node = node.next;
}
/**
* getting a reference of head node of other list
*/
Link<E> node2 = other.head;
/**
* adding all items of other list to the new list
*/
for (int i = 0; i < other.size; i++) {
list.insert(node2.data);
node2 = node2.next;
}
/**
* adding items after the given index (remaining items )of this list to
* the new list
*/
while (node != null) {
list.insert(node.data);
node = node.next;
}
return list;
}
Below is the complete code for testing the above method, please note that I have added an insert method to the list, so that elements can be added to the tail of a list. Thanks
// SinglyLinkedList.java
public class SinglyLinkedList<E> {
private Link head;
private Link tail;
private int size;
private static class Link<E> {
private E data;
private Link next;
// added a constructor to make things easier
public Link(E data) {
this.data = data;
}
}
/**
* method to insert a value to the list (to the end)
*/
public void insert(E data) {
if (head == null) {
//first entry
head = new Link<E>(data);
tail=head;
} else {
//adding to the tail
Link<E> newNode= new Link<E>(data);
tail.next=newNode;
tail=newNode;
}
size++;
}
/**
* method to splice the other list into this list in the given index
*
* @param atIndex
* - index of insertion
* @param other
* - other singlylinked list
* @return the new list
* @throws Exception
* if index is out of range
*/
public SinglyLinkedList splice(int atIndex, SinglyLinkedList other)
throws Exception {
if (atIndex < 0 || atIndex > size) {
throw new Exception("Invalid index!");// invalid index
}
/**
* creating a new list
*/
SinglyLinkedList<E> list = new SinglyLinkedList();
/**
* getting a reference of head node of this list
*/
Link<E> node = this.head;
/**
* adding items before the given index of this list to the new list
*/
for (int i = 0; i < atIndex; i++) {
list.insert(node.data);
node = node.next;
}
/**
* getting a reference of head node of other list
*/
Link<E> node2 = other.head;
/**
* adding all items of other list to the new list
*/
for (int i = 0; i < other.size; i++) {
list.insert(node2.data);
node2 = node2.next;
}
/**
* adding items after the given index (remaining items )of this list to
* the new list
*/
while (node != null) {
list.insert(node.data);
node = node.next;
}
return list;
}
@Override
public String toString() {
/**
* return a formatted string containing list elements
*/
String data = "[";
Link<E> reference = head;
int i=0;
while (i<size) {
data += reference.data;
if (reference != tail) {
data += ", ";
}
reference = reference.next;
i++;
}
data += "]";
return data;
}
}
// Test.java
public class Test {
public static void main(String[] args) {
/**
* creating two lists and testing splice method
*/
SinglyLinkedList<Integer> list1=new SinglyLinkedList<Integer>();
list1.insert(1);
list1.insert(2);
list1.insert(3);
SinglyLinkedList<Integer> list2=new SinglyLinkedList<Integer>();
list2.insert(4);
list2.insert(5);
list2.insert(6);
System.out.println("list1: "+list1);
System.out.println("list2: "+list2);
try {
System.out.println("list1.splice(1,list2): "+list1.splice(1, list2));
System.out.println("list1.splice(0,list2): "+list1.splice(0, list2));
System.out.println("list1.splice(3,list2): "+list1.splice(3, list2));
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
/*OUTPUT*/
list1: [1, 2, 3]
list2: [4, 5, 6]
list1.splice(1,list2): [1, 4, 5, 6, 2, 3]
list1.splice(0,list2): [4, 5, 6, 1, 2, 3]
list1.splice(3,list2): [1, 2, 3, 4, 5, 6]