1.1 single-linked list. it's a node and a list
package linkedList;
public class LList {
public LList next;
String data;
public LList(String data) {
this.data = data;
}
public void insertFront(String data) {
LList newNode = new LList(this.data);
newNode.next = this.next;
this.data = data;
this.next = newNode;
}
public LList find(String data) {
LList nextNode;
nextNode = this;
while (nextNode != null) {
if (nextNode.data != null && nextNode.data.equals(data))
return nextNode;
nextNode = nextNode.next;
}
return null;
}
public void delete(String data) {
if (data == null)
return;
LList cursor = this;
LList previous = null;
// first element need to be removed. this can not be removed so ship all
// element and remove last one
if (this.data != null && this.data.equals(data)) {
while (cursor.next != null) {
cursor.data = cursor.next.data;
previous = cursor;
cursor = cursor.next;
}
if (previous != null)
previous.next = null;
return;
}
previous = this;
cursor = this.next;
while (cursor != null) {
if (cursor.data != null && cursor.data.equals(data)) {
previous.next = cursor.next;
cursor = cursor.next;
} else {
previous = cursor;
cursor = cursor.next;
}
}
return;
}
public void insertAfter(String afterData, String data) {
LList afterNode = this.find(afterData);
if (afterData == null)
return;
LList newNode = new LList(data);
newNode.next = afterNode.next;
afterNode.next = newNode;
}
public String toString() {
StringBuffer sb = new StringBuffer();
LList curNode;
curNode = this;
while (curNode != null) {
sb.append(curNode.data);
curNode = curNode.next;
}
return sb.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
// insertFron test
LList aList = new LList("z");
aList.insertFront("y");
aList.insertFront("x");
aList.insertFront("w");
aList.insertFront("v");
aList.insertFront("u");
System.out.println(aList);
// find test
LList startNode;
startNode = aList.find("y");
System.out.println(startNode);
System.out.println(aList);
// delete test
aList.delete("w");
System.out.println(aList);
// boundary test
aList.delete("u");
System.out.println(aList);
aList.delete("z");
System.out.println(aList);
// insertfter test
aList.insertAfter("v", "w");
System.out.println(aList);
}
}
1.2 Separate node and list. Node can be reused for implementing queue and stack
package linkedList;
public class ListNode {
public ListNode next;
String data;
public ListNode(String data) {
this.data = data;
this.next = null;
}
public String toString(){
return data;
}
}
package linkedList;
public class LList {
ListNode head;
//this constructor will create the first node in list
public LList(String data) {
this.head = new ListNode(data);
}
//this is much simpler than the node as list solution
public void insertFront(String data) {
ListNode newNode = new ListNode (data);
newNode.next = head;
head = newNode;
}
public ListNode find(String data) {
ListNode nextNode;
nextNode = head;
while (nextNode != null) {
if (nextNode.data != null && nextNode.data.equals(data))
return nextNode;
nextNode = nextNode.next;
}
return null;
}
//delete first node is much easier since it's now head instead of "this". you can not assign new value to "this"
public void delete(String data) {
if (data == null)
return;
ListNode curr = head;
ListNode prev = null;
//head matches,adjust head
while(head!=null && head.data != null && head.data.equals(data)) {
head = head.next;
}
////situation like aaaaaaa
if (head == null || (head!=null && head.next==null))
return;
//for any other matchings,point previous node's next to matching node's next node
prev = head;
curr = head.next;
while (curr != null) {
if (curr.data != null && curr.data.equals(data)) {
prev.next = curr.next;
curr = curr.next;
} else {
prev = curr;
curr = curr.next;
}
}
return;
}
public void insertAfter(String afterData, String data) {
ListNode afterNode = this.find(afterData);
if (afterData == null)
return;
ListNode newNode = new ListNode(data);
newNode.next = afterNode.next;
afterNode.next = newNode;
}
public String toString() {
StringBuffer sb = new StringBuffer();
ListNode curNode;
curNode = head;
while (curNode != null) {
sb.append(curNode.data);
curNode = curNode.next;
}
return sb.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
// insertFron test
LList aList = new LList("z");
aList.insertFront("y");
aList.insertFront("x");
aList.insertFront("w");
aList.insertFront("v");
aList.insertFront("u");
System.out.println(aList);
// find test
ListNode startNode;
startNode = aList.find("y");
System.out.println(startNode);
System.out.println(aList);
// delete test
aList.delete("w");
System.out.println(aList);
// boundary test
aList.delete("u");
System.out.println(aList);
aList.delete("z");
System.out.println(aList);
// insertfter test
aList.insertAfter("v", "w");
System.out.println(aList);
}
}
--the following example exercise recursion and iteration to merge two sorted linked list
package linkedList;
public class ListUtil {
/**
* @param args
*/
public static void main(String[] args) {
ListNode aList = new ListNode("u");
aList.next= new ListNode("v");
aList.next.next = new ListNode("w");
aList.next.next.next = new ListNode("x");
aList.next.next.next.next = new ListNode("y");
aList.next.next.next.next.next = new ListNode("z");
ListNode bList = new ListNode("a");
bList.next= new ListNode("b");
bList.next.next = new ListNode("c");
bList.next.next.next = new ListNode("f");
bList.next.next.next.next = new ListNode("o");
bList.next.next.next.next.next = new ListNode("p");
//ListNode merged = mergeSortedList(aList,bList);
ListNode merged2 = mergeSortedListiteration(aList,bList);
System.out.println("done");
}
//recursive
//this returns new conceptual head of the two list
public static ListNode mergeSortedList(ListNode l1, ListNode l2){
ListNode head = null;//this is the head of merged
if (l1==null )
return l2;
else if(l2 ==null)
return l1;
//l1 <= l2, l1 is the new head, and l1 needs to move further to use its next node to continue the comparison
//new head's next will be the smaller new head from next operation
if(l1.data.compareTo(l2.data)<=0){
head = l1;
head.next = mergeSortedList(l1.next,l2);
}
//it does same logic to another list
else if(l1.data.compareTo(l2.data)>0){
head = l2;
head.next = mergeSortedList(l1,l2.next);
}
return head;
}
//iteration method
public static ListNode mergeSortedListiteration(ListNode l1,ListNode l2){
//still head
ListNode fakeHead = new ListNode("fake");
//moving head,
ListNode p = fakeHead;
while(l1 != null && l2 != null){
if(l1.data.compareTo(l2.data) <= 0){
p.next = l1;
l1 = l1.next;
}else{
p.next = l2;
l2 = l2.next;
}
//making new head
p = p.next;
}
if(l1 != null)
p.next = l1;
if(l2 != null)
p.next = l2;
return fakeHead.next;
}
}
to be continued...
No comments:
Post a Comment