There is some problem in the mergeSort method that I couldn't fix.
Singly linked list:
All operations works as expected.
class Node {
/*
* An object for storing a single node in a linked list
*
* Attributes:
* data: Data stored in node
* nextNode: Reference to the next node in the linked list
*/
var data;
Node? nextNode;
Node(this.data, [this.nextNode]);
@override
String toString() {
return '<Node data: $data>';
}
}
class LinkedList {
/*
* Linear data structure that stores values in nodes.
* The list maintains a reference to the first node, also called head.
* Each node points to the next node in the list.
*
* Attributes:
* head: The head node of the list
*/
Node? head;
// Maintaining a count attribute allows for length() to be implemented in
// constant time
var _count = 0;
LinkedList();
bool isEmpty() {
// Determines if the linked list is empty.
// Takes O(1) time.
return head == null;
}
int size() {
Node? current = head;
int count = 0;
while (current != null) {
count++;
current = current.nextNode;
}
return count;
}
int get length {
// Returns the length of the linked list.
// Takes O(1) time.
return _count;
}
void add(dynamic data) {
/*
Adds a new Node containing data to the head of the list
Also called prepend
Takes O(1) time
*/
var newNode = Node(data);
newNode.nextNode = head;
head = newNode;
_count++;
}
void insert(dynamic data, int index) {
/*
* Inserts a new Node containing data at the specified index position.
* Insertion takes O(1) time but finding the node at the insertion point
* takes O(n) time.
* Takes overall O(n) time.
*/
if (index > _count) {
throw IndexError.withLength(index, _count, message: 'index out of range');
}
if (index == 0) {
add(data);
return;
}
if (index > 0) {
var newNode = Node(data);
var position = index;
var current = head;
while (position > 1) {
current = current?.nextNode!;
position--;
}
var prevNode = current;
var nextNode = current?.nextNode;
prevNode?.nextNode = newNode;
newNode.nextNode = nextNode;
}
_count++;
}
Node? nodeAtIndex(int index) {
if (index >= _count) {
throw IndexError.withLength(index, _count, message: 'index out of range');
}
if (index == 0) {
return head;
}
Node? current = head;
int position = 0;
while (position < index) {
current = current?.nextNode;
position++;
}
return current;
}
Node? remove(dynamic key) {
/* Removes Node containing data that matches the key
Returns the node or `null` if key doesn't exist
Takes O(n) time */
Node? current = head;
Node? previous;
bool found = false;
while (current != null && !found) {
if (current.data == key && current == head) {
found = true;
head = current.nextNode;
_count--;
return current;
} else if (current.data == key) {
found = true;
previous?.nextNode = current.nextNode;
_count--;
return current;
} else {
previous = current;
current = current.nextNode;
}
}
return current;
}
Node? removeAtIndex(int index) {
if (index >= _count) {
throw IndexError.withLength(index, _count, message: 'index out of range');
}
Node? current = head;
if (index == 0) {
head = current?.nextNode;
_count--;
return current;
}
int position = index;
while (position > 1) {
current = current?.nextNode;
position--;
}
Node? prevNode = current;
current = current?.nextNode;
Node? nextNode = current?.nextNode;
prevNode?.nextNode = nextNode;
_count--;
return current;
}
Node? search(dynamic key) {
/*
* Search for the first node containing data that matches the key.
* Returns the node or `null` if not found.
* Takes O(n) time.
*/
var current = head;
while (current != null) {
if (current.data == key) {
return current;
} else {
current = current.nextNode;
}
}
return null;
}
@override
String toString() {
// Returns a string representation of the list.
// Takes O(n) time.
List<String> nodes = [];
var current = head;
while (current != null) {
if (identical(current, head)) {
nodes.add("[Head: ${current.data}]");
} else if (current.nextNode == null) {
nodes.add("[Tail: ${current.data}]");
} else {
nodes.add("[${current.data}]");
}
current = current.nextNode;
}
return nodes.join(' -> ');
}
}
Merge Sort Implementation:
import 'linked_list.dart';
LinkedList mergeSort(LinkedList linkedList) {
/* Sorts a linked list in ascending order
* - Recursively divide the linked list into sublists containing a single node
* - Repeatedly merge the sublists to produce sorted sublists until one remains
*
* Returns a sorted linked list
*
* Takes O(n log n) time
* Takes O(n) space
*/
if (linkedList.size() == 1) {
return linkedList;
} else if (linkedList.head == null) {
return linkedList;
}
var (leftHalf, rightHalf) = split(linkedList);
var left = mergeSort(leftHalf);
var right = mergeSort(rightHalf);
return merge(left, right);
}
(LinkedList, LinkedList) split(LinkedList linkedList) {
// Divide the unsorted list at midpoint into sublists
// Takes O(log n) time
// ignore: unnecessary_null_comparison
if (linkedList == null || linkedList.head == null) {
LinkedList leftHalf = linkedList;
LinkedList rightHalf = LinkedList();
return (leftHalf, rightHalf);
} else {
var size = linkedList.size();
var mid = size ~/ 2;
var midNode = linkedList.nodeAtIndex(mid - 1);
var leftHalf = linkedList;
var rightHalf = LinkedList();
rightHalf.head = midNode?.nextNode;
midNode?.nextNode = null;
return (leftHalf, rightHalf);
}
}
LinkedList merge(LinkedList left, LinkedList right) {
/*
* Merges two linked lists, sorting by data in nodes
* Returns a new merged list
* Takes O(n) space
* Runs in O(n) time
*/
var merged = LinkedList();
// Add a fake head that is discarded later.
merged.add(0);
// Set current to the head of the linked list
var current = merged.head;
// Obtain head nodes for left and right linked lists
var leftHead = left.head;
var rightHead = right.head;
// Iterate over left and right as long until the tail node of both left and right
while (leftHead != null || rightHead != null) {
// If the head node of left is None, we're at the tail
// Add the tail node from right to the merged linked list
if (leftHead == null) {
current?.nextNode = rightHead;
// Call next on right to set loop condition to False
rightHead = rightHead?.nextNode;
// If the head node of right is None, we're at the tail
// Add the tail node from left to the merged linked list
} else if (rightHead == null) {
current?.nextNode = leftHead;
// Call next on left to set loop condition to False
leftHead = leftHead.nextNode;
} else {
// Not at either tail node
// Obtain node data to perform comparison operations
var leftData = leftHead.data;
var rightData = rightHead.data;
// If data on left is lesser than right set current to left node
// Move left head to next node
if (leftData < rightData) {
current?.nextNode = leftHead;
leftHead = leftHead.nextNode;
} else {
// If data on left is greater than right set current to right node
// Move right head to next node
current?.nextNode = rightHead;
rightHead = rightHead.nextNode;
}
}
// Move current to next node
current = current?.nextNode;
}
// Discard fake head and set first merged node as head
var head = merged.head?.nextNode;
merged.head = head;
return merged;
}
void main(List<String> args) {
var l = LinkedList();
l.add(99);
l.add(25);
l.add(3);
l.add(47);
print('Unsorted list: $l');
final sortedList = mergeSort(l);
print('Sorted list: $sortedList');
// var r = l.remove(25);
// print('$r is removed');
// var n = l.search(99);
// print('$n is found');
// int index = 0;
// var ni = l.nodeAtIndex(index);
// print('$ni at index $index');
// var ri = l.removeAtIndex(index);;
// print('$ri at index $index is removed');
}
The split and merge methods seem to work just fine.
I tried the split and merge methods separately. They work. Unhandled exception occurs when I call the mergeSort method.
Output:
Unsorted list: [Head: 47] -> [3] -> [25] -> [Tail: 99]
Unhandled exception:
RangeError: index out of range: no indices are valid: 0
#0 LinkedList.nodeAtIndex (file:///D:/Documents/Development/projects/dartpad/bin/linked_list.dart:116:7)
#1 split (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:27:30)
#2 mergeSort (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:10:31)
#3 mergeSort (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:12:15)
#4 main (file:///D:/Documents/Development/projects/dartpad/bin/merge_sort_linked_list.dart:84:22)
#5 _delayEntrypointInvocation.<anonymous closure> (dart:isolate-patch/isolate_patch.dart:294:33)
#6 _RawReceivePort._handleMessage (dart:isolate-patch/isolate_patch.dart:189:12)
Exited (255).
class LinkedList {
// ... Existing code ...
void updateCount(int newCount) {
_count = newCount;
}
// ... Rest of the code ...
}
(LinkedList, LinkedList) split(LinkedList linkedList) {
// ignore: unnecessary_null_comparison
if (linkedList == null || linkedList.head == null) {
LinkedList leftHalf = linkedList;
LinkedList rightHalf = LinkedList();
return (leftHalf, rightHalf);
} else {
var size = linkedList.size();
var mid = size ~/ 2;
var midNode = linkedList.nodeAtIndex(mid - 1);
var leftHalf = linkedList;
leftHalf.updateCount(mid);
var rightHalf = LinkedList();
rightHalf.head = midNode?.nextNode;
rightHalf.updateCount(size - mid);
midNode?.nextNode = null;
return (leftHalf, rightHalf);
}
}