getting “sub-LinkedLlists” from java's LinkedList class (for MergeSort purposes)

I am trying to practice the MergeSort algorithm on java's standard LinkedList. I am new to standard libraries.

The issue I am having is creating 'sub-LinkedLists' to get the best performance from the MergeSort.

I have a working code, but unfortunately it treats the LinkedList as if it was some array:

public void mergeSort(LinkedList<Integer> lisst)
if (lisst.size() < 2)
return;

int middleindex = lisst.size()/2;
LinkedList<Integer> LeftList = new LinkedList<Integer>();


for(int i = 0; i< middleindex; i++)
LeftList.addLast(lisst.get(i));

mergeSort(LeftList);

LinkedList<Integer> RightList = new LinkedList<Integer>();

for (int i = middleindex; i< lisst.size(); i++)
RightList.addLast(lisst.get(i));


mergeSort(RightList);
SortedMerge(RightList,LeftList,lisst);



From what I have been reading, doing sth like this, kills the purpose of merge sort on linkedlist. But how do I actually get sub linked lists with an object of the standard LinkedList class? I could do this confidently if it was sth I had written with a node class like :

node leftHead = lisst.get(middleindex);
mergeSort(lefthead);// Assuming the method also takes a node instead of LL


but reading the library, I can't figure out how to point to the middle element and use the rest as a sublist without looping over to add it to a new linked list

is there a really simple way to do this ? am I not seeing sth?

Thanks ahead.

1 Answer
1

If you only want the right part of the LinkedList, you should have the following:

LinkedList

public static <T> LinkedList<T> removeUntil(LinkedList<T> list, int index)
for (int i = 0; i < index; i++)
list.removeFirst();


return list;



Usecase

public static void main(String args)
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer 1, 3, 5, 6, 9));
System.out.format("Input : %s%n", list);
list = removeUntil(list, 3);
System.out.format("Output: %s%n", list);



Usecase output

Input : [1, 3, 5, 6, 9]
Output: [6, 9]


If you wish to reserve the left part of the LinkedList, you should have the following instead:

LinkedList

public static <T> LinkedList<T> split(LinkedList<T> list, int index)
LinkedList<T> left = new LinkedList<>();

for (int i = 0; i < index; i++)
T t = list.removeFirst();
left.addLast(t);


return new LinkedList
left, list
;



Usecase

public static void main(String args)
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(new Integer 1, 3, 5, 6, 9));
System.out.format("Input : %s%n", list);
LinkedList alist = split(list, 3);
System.out.format("Output: %s, %s%n", alist[0], alist[1]);



Usecase output

Input : [1, 3, 5, 6, 9]
Output: [1, 3, 5], [6, 9]


Reference:

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.