In JAVA The following exercise deal with coding a LinkedList. - The methids you
ID: 3755388 • Letter: I
Question
In JAVA
The following exercise deal with coding a LinkedList.
- The methids you are writing are instance methods inside of LinkedList, so you can use the Node class.
- The LinkedList contains a Node<E> head and tail(optional).
- The LinkedList contains a method size() that returns the number of elements in the list.
- The Node objects are singly-linked, and contain public variable next, which references the next node in the list.
- you can use an Iterator if you want but you dont need to.
part2: time complexity?
0. (5 points) Write a method called concatenate, which takes two lists, which we'll refer to as A and B and changes A such that it has A's elements first, then B's elements. For example, if A is [1,3,5) and B is 12, 4,6], concatenate changes A to 1,3,5,2, 4, 6]. Make your solution as optimal as possible. // Since this is inside LinkedList // You can use the head and tail of A andB public void concatenate (LinkedList A, LinkedList B)Explanation / Answer
assuming you are using default Linked List class as already defined as mentioned in the question (not making a custom class).
the function definition is as :
import java.util.ListIterator;
public void concatenate(LinkedList<E> A, LinkedList<E> B)
{
ListIterator<E> it = B.listIterator(); // creates an iterator for list B
while (lt.hasNext()) {
A.add( it.next() ); //appends data of list B at the end of list A untill loop terminates
}
}
LinkedList :: add function adds the data at the end in O(1) time
so total time complexity in O(m) where m is size of LinkedList B
or without iterator we can do it as :
public void concatenate(LinkedList<E> A, LinkedList<E> B)
{
Node lastNode;
while (A.head.next != null)
{
lastNode=A.head;
A.head= A.head.next;
}
lastNode.next=B.head; //point B's first node to after first Node of A
}
// here time complexity is O(n) where n is size of list A
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.