Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
LinkedList utils - singly and doubly linked
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class DoubleLinkedListJTests {
DoubleLinkedListNode input, output;
boolean isEqual = false;
@Test
public void nullEmpty() {
input = null;
output = null;
input = LinkedListUtils.reverseList(input);
assertEquals("reverse null expected null", output, input);
input = new DoubleLinkedListNode();
output = new DoubleLinkedListNode();
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse empty expected empty", true, isEqual);
}
@Test
public void reverseList() {
//single node
input = new DoubleLinkedListNode(1, "A");
output = new DoubleLinkedListNode(1, "A");
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse A expected A", true, isEqual);
//multiple nodes
input = new DoubleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
output = new DoubleLinkedListNode(3, "C");
output.addLast(2, "B");
output.addLast(1, "A");
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse A,B,C expected C,B,A", true, isEqual);
}
}
package com.blogspot.groglogs.structures;
public class DoubleLinkedListNode {
public Integer id;
public String data;
public DoubleLinkedListNode next, prev;
public DoubleLinkedListNode(){
this.id = null;
this.data = null;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id){
this.id = id;
this.data = null;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id, DoubleLinkedListNode prev){
this.id = id;
this.data = null;
this.next = null;
this.prev = prev;
}
public DoubleLinkedListNode(Integer id, String data){
this.id = id;
this.data = data;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id, String data, DoubleLinkedListNode prev){
this.id = id;
this.data = data;
this.next = null;
this.prev = prev;
}
public int length(){
if(this.id == null || this.data == null) return 0;
int count = 0;
DoubleLinkedListNode next = this;
while(next != null){
count++;
next = next.next;
}
return count;
}
public void addLast(Integer id, String data){
DoubleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new DoubleLinkedListNode(id, data, next);
}
public void addLast(Integer id){
DoubleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new DoubleLinkedListNode(id, next);
}
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
DoubleLinkedListNode other = (DoubleLinkedListNode) obj;
return this.id == other.id && this.data == other.data;
}
public boolean equalsData(DoubleLinkedListNode other) {
if(other == null) return false;
return this.data == other.data;
}
public boolean equalsId(DoubleLinkedListNode other) {
if(other == null) return false;
return this.id == other.id;
}
public boolean equalsList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equals(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsDataList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsData(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsIdList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsId(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public void printList(){
DoubleLinkedListNode next = this;
while(next != null){
System.out.println("id: " + next.id + " - data: " + next.data);
next = next.next;
}
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class LinkedListSumJTests {
SingleLinkedListNode x, y, output, result;
boolean isEqual;
@Test
//null or empty lists
public void nullEmpty() {
x = null;
y = null;
output = LinkedListUtils.sumListsFromLSD(x, y);
assertEquals("null list expected null", null, output);
x = new SingleLinkedListNode();
y = new SingleLinkedListNode();
output = new SingleLinkedListNode(0);
result = LinkedListUtils.sumListsFromLSD(x, y);
assertEquals("empty list expected 0", output.id, result.id);
}
@Test
public void oneEmpty() {
//null + 125 = 125
x = null;
y = new SingleLinkedListNode(5);
y.addLast(2);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = y;
isEqual = output.equalsIdList(result);
assertEquals("null + 125 = 125 expected 5,2,1", true, isEqual);
}
@Test
public void differentLength() {
//4037 + 125 = 4162
x = new SingleLinkedListNode(7);
x.addLast(3);
x.addLast(0);
x.addLast(4);
y = new SingleLinkedListNode(5);
y.addLast(2);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(2);
output.addLast(6);
output.addLast(1);
output.addLast(4);
isEqual = output.equalsIdList(result);
assertEquals("4037 + 125 = 4162 expected 2,6,1,4", true, isEqual);
}
@Test
//have a carry at the last operation
public void carryLast() {
//90 + 10 = 100
x = new SingleLinkedListNode(0);
x.addLast(9);
y = new SingleLinkedListNode(0);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(0);
output.addLast(0);
output.addLast(1);
isEqual = output.equalsIdList(result);
assertEquals("90 + 10 = 100 expected 0,0,1", true, isEqual);
}
@Test
//have multiple carry
public void multipleCarry() {
//999 + 999 = 1998
x = new SingleLinkedListNode(9);
x.addLast(9);
x.addLast(9);
y = x;
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(8);
output.addLast(9);
output.addLast(9);
output.addLast(1);
isEqual = output.equalsIdList(result);
assertEquals("999 + 999 = 1998 expected 8,9,9,1", true, isEqual);
}
}
package com.blogspot.groglogs.linkedlistutils;
import com.blogspot.groglogs.structures.*;
public class LinkedListUtils {
public static void removeDuplicates(SingleLinkedListNode head){
SingleLinkedListNode curr, prev, next;
curr = head;
//for each single node
while(curr != null){
//track 2 nodes at the same time
prev = curr;
next = prev.next;
//walk the whole list
while(next != null){
/*
if the next node is a duplicate, delete it by linking the previous to the next.next
CAUTION: do NOT move the previous node because we could lose a value
*/
if(next.data == curr.data) prev.next = next.next;
//only move previous if the next one was unique
else prev = prev.next;
//move next to the new next element
if(prev != null) next = prev.next;
}
curr = curr.next;
}
}
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNode(SingleLinkedListNode head, int k){
if(head == null) return head;
int length = head.length();
/*
list is 1 to length, so check k is in that range
CAUTION: we are removing kth to last so k = 0 means remove last
k = length -1 means remove first
*/
if(k < 0 || k > length - 1) return head;
int n, count = 1;
SingleLinkedListNode prev = head, next;
//find out which element we want to remove
n = length - k;
//if it's the head, just return next
if(n == 1){
return prev.next;
}
//otherwise walk through the list and delete the desired element
while(prev != null){
next = prev.next;
//CAUTION: check with count + 1 so we do not skip the element we want to delete. next will be it!
if(n == count + 1){
if(next != null) prev.next = next.next;
//CAUTION: avoid NullPointerException when we are deleting tail
else prev.next = null;
return head;
}
prev = prev.next;
count++;
}
return head;
}
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNodePointers(SingleLinkedListNode head, int k){
if(head == null || k < 0) return head;
int fast_idx = 0;
SingleLinkedListNode fast = head, slow = null;
/*
keep two pointers running after each other
the slow one starts k+1 steps after the fast one
when the fast one reaches the end of the list, the slow one should be exactly before the element to remove
*/
while(fast.next != null){
if(slow != null) slow = slow.next;
fast = fast.next;
fast_idx++;
if(fast_idx == k + 1) slow = head;
}
//if the slow one is actually pointing somewhere, remove the following node
if(slow != null) slow.next = slow.next.next;
//otherwise if we want to remove the head (k = list length), just return the next from head
if(fast_idx == k) return head.next;
return head;
}
/*
Given two lists representing integer numbers
with the least significant digit in the head position
return a new list containing the sum
*/
public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){
if(x == null && y == null) return null;
int carry = 0, curr = 0, val = 0;
SingleLinkedListNode result = null, n = null;
//keep going until we have data in either list and do not forget the last carry!
while(x != null || y != null || carry != 0){
curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry
val = curr % 10; //take only LSD
//track if we have a carry
carry = (curr >= 10) ? 1 : 0;
if(n == null){
n = new SingleLinkedListNode(val);
result = n;
}
else{
n.next = new SingleLinkedListNode(val);
n = n.next;
}
//move to next digit
if(x != null) x = x.next;
if(y != null) y = y.next;
}
return result;
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class RemoveDuplicatesJTests {
SingleLinkedListNode input, output;
boolean isEqual;
@Test
//empty
public void empty() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsList(output);
assertEquals("new list expected true", true, isEqual);
}
@Test
public void removeDuplicates() {
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
output = input;
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C expected A,B,C", true, isEqual);
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "B");
input.addLast(4, "A");
input.addLast(5, "C");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,B,A,C expected A,B,C", true, isEqual);
assertEquals("A,A,B,A,C expected final length 3", 3, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "B");
input.addLast(4, "A");
input.addLast(5, "C");
input.addLast(6, "C");
input.addLast(7, "C");
input.addLast(8, "D");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
output.addLast(4, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,B,A,C,C,C,D expected A,B,C,D", true, isEqual);
assertEquals("A,A,B,A,C,C,C,D expected final length 4", 4, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "A");
input.addLast(4, "A");
input.addLast(5, "A");
input.addLast(6, "A");
input.addLast(7, "A");
input.addLast(8, "A");
output = new SingleLinkedListNode(1, "A");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,A,A,A,A,A,A expected A", true, isEqual);
assertEquals("A,A,A,A,A,A,A,A expected final length 1", 1, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "A");
input.addLast(7, "D");
input.addLast(8, "A");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,A,D,A expected A,D", true, isEqual);
assertEquals("A,A,A,D,A expected final length 2", 2, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
input.addLast(7, "D");
input.addLast(8, "D");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(2, "C");
output.addLast(2, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C,D,D expected A,B,C,D", true, isEqual);
assertEquals("A,B,C,D,D expected final length 4", 4, input.length());
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class RemoveKtoLastNodeJTests {
SingleLinkedListNode input, output;
boolean isEqual;
int k;
@Test
//empty
public void empty() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
k = 0;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("new list expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = -1;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("k < 0 expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = 2;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("k > length expected true", true, isEqual);
}
@Test
public void removeKtoLastNode() {
//remove last node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 0;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 0 expected A,B", true, isEqual);
assertEquals("A,B,C k = 0 expected length 2", 2, input.length());
//remove middle node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 1;
output = new SingleLinkedListNode(1, "A");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 1 expected A,C", true, isEqual);
assertEquals("A,B,C k = 1 expected length 2", 2, input.length());
//remove first node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 2;
output = new SingleLinkedListNode(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 2 expected B,C", true, isEqual);
assertEquals("A,B,C k = 2 expected length 2", 2, input.length());
//cannot remove node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 3;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 3 expected A,B,C", true, isEqual);
assertEquals("A,B,C k = 2 expected length 3", 3, input.length());
}
@Test
//empty
public void emptyPointers() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
k = 0;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
assertEquals("pointers new list expected null", null, input);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = -1;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsList(output);
assertEquals("pointers k < 0 expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = 2;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsList(output);
assertEquals("pointers k > length expected true", true, isEqual);
}
@Test
public void removeKtoLastNodePointer() {
//remove last node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 0;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 0 expected A,B", true, isEqual);
assertEquals("pointers A,B,C k = 0 expected length 2", 2, input.length());
//remove middle node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 1;
output = new SingleLinkedListNode(1, "A");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 1 expected A,C", true, isEqual);
assertEquals("pointers A,B,C k = 1 expected length 2", 2, input.length());
//remove first node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 2;
output = new SingleLinkedListNode(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 2 expected B,C", true, isEqual);
assertEquals("pointers A,B,C k = 2 expected length 2", 2, input.length());
//cannot remove node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 3;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 3 expected A,B,C", true, isEqual);
assertEquals("pointers A,B,C k = 2 expected length 3", 3, input.length());
}
}
package com.blogspot.groglogs.structures;
public class SingleLinkedListNode {
public Integer id;
public String data;
public SingleLinkedListNode next;
public SingleLinkedListNode(){
this.id = null;
this.data = null;
this.next = null;
}
public SingleLinkedListNode(Integer id){
this.id = id;
this.data = null;
this.next = null;
}
public SingleLinkedListNode(Integer id, String data){
this.id = id;
this.data = data;
this.next = null;
}
public int length(){
if(this.id == null || this.data == null) return 0;
int count = 0;
SingleLinkedListNode next = this;
while(next != null){
count++;
next = next.next;
}
return count;
}
public void addLast(Integer id, String data){
SingleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new SingleLinkedListNode(id, data);
}
public void addLast(Integer id){
SingleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new SingleLinkedListNode(id);
}
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
SingleLinkedListNode other = (SingleLinkedListNode) obj;
return this.id == other.id && this.data == other.data;
}
public boolean equalsData(SingleLinkedListNode other) {
if(other == null) return false;
return this.data == other.data;
}
public boolean equalsId(SingleLinkedListNode other) {
if(other == null) return false;
return this.id == other.id;
}
public boolean equalsList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equals(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsDataList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsData(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsIdList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsId(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public void printList(){
SingleLinkedListNode next = this;
while(next != null){
System.out.println("id: " + next.id + " - data: " + next.data);
next = next.next;
}
}
}