This is a basic class structure: public class SinglyLinkedList<E> { private Link
ID: 3912235 • Letter: T
Question
This is a basic class structure:
public class SinglyLinkedList<E> {
private Link<E> head;
private Link<E> tail;
//...
private static class Link<E> {
private E data;
private Link<E> next;
//...
}
}
I want to have a O(n) method that could appear in SinglyLinkedList that appends one list to the end of the other.
public SinglyLinkedList<E> append(SinglyLinkedList<E> other)
The method will take the nodes of the other SinglyLinkedList and append copies of them to the end of this list. The method should not change the other list. You should return this list.
Example : If a has {1,2,3} and b has {4,5,6}
Then after a.append(b), it should be 1,2,3,4,5,6
Explanation / Answer
Here is the definition of append method you asked for.
/**
* method to append contents of another list to the end of this list in O(n)
* time
*
* @param other
* - other singly linked list
* @return this list containing copies of other list's contents at the end
*/
public SinglyLinkedList<E> append(SinglyLinkedList<E> other) {
/**
* Taking a reference to the other list's head
*/
Link<E> otherNode = other.head;
/**
* looping until otherNode's value is null
*/
while (otherNode != null) {
if (this.head == null) {
/**
* Adding as the first entry of this list, in case if this
* doesn't have any elements
*/
this.head = new Link<E>(otherNode.data);
this.tail = this.head;
} else {
/**
* appending to the tail and updating the tail
*/
this.tail.next = new Link<E>(otherNode.data);
this.tail = this.tail.next;
}
this.size++; //incrementing size
otherNode = otherNode.next;//moving to next node
}
return this; //returning updated list
}
Below is the complete definition of SinglyLinkedList class along with a test class to test the append method after creating two lists. This is just for understanding the code better. If you have any doubts, drop a comment. 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;
}
public Link() {
}
}
/**
* method to insert a value to the list (to the end). This method is just
* for testing
*/
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++;
}
@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;
}
/**
* method to append contents of another list to the end of this list in O(n)
* time
*
* @param other
* - other singly linked list
* @return this list containing copies of other list's contents at the end
*/
public SinglyLinkedList<E> append(SinglyLinkedList<E> other) {
/**
* Taking a reference to the other list's head
*/
Link<E> otherNode = other.head;
/**
* looping until otherNode's value is null
*/
while (otherNode != null) {
if (this.head == null) {
/**
* Adding as the first entry of this list, in case if this
* doesn't have any elements
*/
this.head = new Link<E>(otherNode.data);
this.tail = this.head;
} else {
/**
* appending to the tail and updating the tail
*/
this.tail.next = new Link<E>(otherNode.data);
this.tail = this.tail.next;
}
this.size++; //incrementing size
otherNode = otherNode.next;//moving to next node
}
return this; //returning updated list
}
}
// Test.java
public class Test {
public static void main(String[] args) {
/**
* creating two lists and testing append 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);
System.out.println("list1.append(list2): "+list1.append(list2));
}
}
/*OUTPUT*/
list1: [1, 2, 3]
list2: [4, 5, 6]
list1.append(list2): [1, 2, 3, 4, 5, 6]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.