Java LinkedList and Search Tree

abstract Class ListItem

点击(此处)折叠或打开

1. package abstract_exp;
   
2. 
   
3. public abstract class ListItem{
   
4.     protected ListItem rightLink;
   
5.     protected ListItem leftLink;
   
6.     protected Object value;
   
7. 
   
8.     public ListItem(Object value) {
   
9.         this.value = value;
   
10.     }
    
11. 
    
12.     abstract ListItem next();
    
13.     abstract ListItem setNext(ListItem item);
    
14.     abstract ListItem prev();
    
15.     abstract ListItem setPrev(ListItem item);
    
16.     abstract int compareTo(ListItem other);
    
17. 
    
18.     public Object getValue(){
    
19.         return value;
    
20.     }
    
21. 
    
22.     public void setValue(Object value){
    
23.         this.value = value;
    
24.     }
    
25. }

下面是interface 

点击(此处)折叠或打开

1. public interface NodeList {
   
2.     ListItem getRoot();
   
3.     boolean addItem(ListItem newItem);
   
4.     boolean removeItem(ListItem item);
   
5.     void traverse(ListItem root);
   
6. 
   
7. }

Node 

点击(此处)折叠或打开

1. public class Node extends ListItem {
   
2.     public Node(Object value) {
   
3.         super(value);
   
4.     }
   
5. 
   
6.     @Override
   
7.     ListItem next() {
   
8.         return this.rightLink;
   
9.     }
   
10. 
    
11.     @Override
    
12.     ListItem setNext(ListItem item) {
    
13.         this.rightLink = item;
    
14.         return this.rightLink;
    
15.     }
    
16. 
    
17.     @Override
    
18.     ListItem prev() {
    
19.         return leftLink;
    
20.     }
    
21. 
    
22.     @Override
    
23.     ListItem setPrev(ListItem item) {
    
24.         this.leftLink = item;
    
25.         return this.leftLink;
    
26.     }
    
27. 
    
28.     @Override
    
29.     int compareTo(ListItem other) {
    
30.         if(other != null){
    
31.             return ((String) super.getValue()).compareTo(
    
32.                     (String) other.getValue());
    
33.         }else{
    
34.             return -1;
    
35.         }
    
36.     }
    
37. }

MyLinkedList

点击(此处)折叠或打开

1. public class MyLinkList implements NodeList {
   
2.     private ListItem root = null;
   
3. 
   
4.     public MyLinkList(ListItem root) {
   
5.         this.root = root;
   
6.     }
   
7. 
   
8.     @Override
   
9.     public ListItem getRoot() {
   
10.         return this.root;
    
11.     }
    
12. 
    
13.     @Override
    
14.     public boolean addItem(ListItem newItem) {
    
15.         if (this.root == null) {
    
16.             //The list was empty,
    
17.             this.root = newItem;
    
18.             return true;
    
19.         }
    
20.         ListItem currentItem = this.root;
    
21.         while (currentItem != null) {
    
22.             int comparison = (currentItem.compareTo(newItem));
    
23.             if (comparison < 0) {
    
24.                 //new item is greater, move right if possible
    
25.                 if (currentItem.next() != null) {
    
26.                     currentItem = currentItem.next();
    
27.                 } else {
    
28.                     //There is no next, so insert at end of list
    
29.                     currentItem.setNext(newItem);
    
30.                     newItem.setPrev(currentItem);
    
31.                     return true;
    
32.                 }
    
33.             } else if (comparison > 0) {
    
34.                 //new Item is less, insert before
    
35.                 if (currentItem.prev() != null) {
    
36.                     currentItem.prev().setNext(newItem);
    
37.                     newItem.setPrev(currentItem.prev());
    
38.                     newItem.setNext(currentItem);
    
39.                     currentItem.setPrev(newItem);
    
40.                 } else {
    
41.                     //the node with a prev is the root
    
42.                     newItem.setNext(this.root);
    
43.                     this.root.setPrev(newItem);
    
44.                     this.root = newItem;
    
45.                 }
    
46.                 return true;
    
47.             } else {
    
48.                 //equal
    
49.                 System.out.println(newItem.getValue() + " is already present at the list");
    
50.                 return false;
    
51.             }
    
52.         }
    
53.         return false;
    
54.     }
    
55. 
    
56.     @Override
    
57.     public boolean removeItem(ListItem item) {
    
58.         if(item != null){
    
59.             System.out.println("Deleting item "+item.getValue());
    
60.         }
    
61.         ListItem currentItem = this.root;
    
62.         while(currentItem != null){
    
63.             int comparison = currentItem.compareTo(item);
    
64.             if(comparison == 0) {
    
65.                 //found the item to delete
    
66.                 if(currentItem == this.root){
    
67.                     this.root = currentItem.next();
    
68.                 }else{
    
69.                     currentItem.prev().setNext(currentItem.next());
    
70.                     if(currentItem.next() != null){
    
71.                         currentItem.next().setPrev(currentItem.prev());
    
72.                     }
    
73.                 }
    
74.                 return true;
    
75.             }else if(comparison < 0){
    
76.                 currentItem = currentItem.next();
    
77.             }else{
    
78.                 //comparison > 0
    
79.                 //we are at an item greater than the one to be deleted
    
80.                 //so the item is not in the list
    
81.                 return false;
    
82.             }
    
83.         }
    
84.         //we have reached the end of the list
    
85.         //without finding the item to delete
    
86.         return false;
    
87.     }
    
88. 
    
89.     @Override
    
90.     public void traverse(ListItem root) {
    
91.         if (root == null) {
    
92.             System.out.println("The list is empty");
    
93.         } else {
    
94.             while (root != null) {
    
95.                 System.out.println(root.getValue());
    
96.                 root = root.next();
    
97.             }
    
98.         }
    
99.     }
    
100. }

SearchTree

点击(此处)折叠或打开

1. public class SearchTree implements NodeList {
   
2.     private ListItem root = null;
   
3. 
   
4.     //constructor
   
5.     public SearchTree(ListItem root){
   
6.         this.root = root;
   
7.     }
   
8. 
   
9.     @Override
   
10.     public ListItem getRoot() {
    
11.         return this.root;
    
12.     }
    
13. 
    
14.     @Override
    
15.     public boolean addItem(ListItem newItem) {
    
16.         if(this.root == null){
    
17.             //the tree was empty, so our item becomes the
    
18.             //head of the tree
    
19.             this.root = newItem;
    
20.             return true;
    
21.         }
    
22.         //other waise, starting comparing from the head of the tree
    
23.         ListItem currentItem = this.root;
    
24.         while(currentItem != null){
    
25.             int comparison = (currentItem.compareTo(newItem));
    
26.             if(comparison < 0){
    
27.                 //newItem is greater ,move right if possible
    
28.                 if(currentItem.next() != null){
    
29.                     currentItem=currentItem.next();
    
30.                 }else{
    
31.                     //there is no node to the right, so add at this point
    
32.                     currentItem.setNext(newItem);
    
33.                     return true;
    
34.                 }
    
35.             }else if(comparison > 0){
    
36.                 //newItem is less, move left is possible
    
37.                 if(currentItem.prev() != null){
    
38.                     currentItem = currentItem.prev();
    
39.                 }else{
    
40.                     //there is no node to the left, so add at this point
    
41.                     currentItem.setPrev(newItem);
    
42.                     return true;
    
43.                 }
    
44.             }else{
    
45.                 //equal, so do not add
    
46.                 System.out.println(newItem.getValue() +" is already existed in ");
    
47.                 return false;
    
48. 
    
49.             }
    
50.         }
    
51.         //we can not actually get here, but java complains if there's no return
    
52.         return false;
    
53.     }
    
54. 
    
55.     @Override
    
56.     public boolean removeItem(ListItem item) {
    
57.         if(item !=null){
    
58.             System.out.println("Deleting item "+item.getValue());
    
59.         }
    
60. 
    
61.         ListItem currentItem = this.root;
    
62.         ListItem parentItem = currentItem;
    
63. 
    
64.         while(currentItem != null){
    
65.             int comparison = (currentItem.compareTo(item));
    
66.             if(comparison < 0){
    
67.                 parentItem = currentItem;
    
68.                 currentItem = currentItem.next();
    
69.             }else if(comparison > 0){
    
70.                 parentItem = currentItem;
    
71.                 currentItem = currentItem.prev();
    
72.             }else{
    
73.                 //equal, we've found the item so remove it
    
74.                 performRemove(currentItem, parentItem);
    
75.                 return true;
    
76.             }
    
77.         }
    
78.         return false;
    
79.     }
    
80. 
    
81.     private void performRemove(ListItem item, ListItem parent){
    
82.         //remove item from the tree
    
83.         if(item.next() == null){
    
84.             //no right tree, so make parent point to left ree(which may be null)
    
85.             if(parent.next() == item){
    
86.                 //item is rigt child of its parent
    
87.                 parent.setNext(item.prev());
    
88.             }else if(parent.prev() == item){
    
89.                 //item is left child of its parent
    
90.                 parent.setPrev(item.prev());
    
91.             }else{
    
92.                 //parent must be item, which means we were looking at the root of the tree
    
93.                 this.root = item.prev();
    
94.             }
    
95.         }else if(item.prev()== null){
    
96.             //no left tree, so make parent point to right tree(which may be null)
    
97.             if(parent.next()==item){
    
98.                 //item is right child of its parent
    
99.                 parent.setNext(item.next());
    
100.             }else if(parent.prev() == item){
     
101.                 //item is left child of its parent
     
102.                 parent.setPrev(item.next());
     
103.             }else{
     
104.                 //again, we are deleting the root
     
105.                 this.root = item.next();
     
106.             }
     
107.         }else{
     
108.             //neither left nor right are null, deletion is now a lot
     
109.             //trickier , From the right sub-tree, find the smallest value
     
110.             //ie: the leftmost
     
111.             ListItem current=item.next();
     
112.             ListItem leftMostParent = item;
     
113.             while(current.prev() != null){
     
114.                 leftMostParent = current;
     
115.                 current = current.prev();
     
116.             }
     
117. 
     
118.             //now put the smallest value into our node to be deleted
     
119.             item.setValue(current.getValue());
     
120.             //and delete the smallest
     
121.             if(leftMostParent == item){
     
122.                 //there was no left most node, so current points to the smallest
     
123.                 //node (the one that must now be delete)
     
124.                 item.setNext(current.next());
     
125.             }else{
     
126.                 //set the smallest node's parent to point to
     
127.                 //the smallest node's right child (which may be null)
     
128.                 leftMostParent.setPrev(current.next());
     
129.             }
     
130.         }
     
131.     }
     
132. 
     
133.     @Override
     
134.     public void traverse(ListItem root) {
     
135.         if( null){
     
136.             traverse(root.prev());
     
137.             System.out.println(root.getValue());
     
138.             traverse(root.next());
     
139.         }
     
140.     }
     
141. }