定义抽象节点类Node：

1 package cn.wzbrilliant.datastructure; 2  3 /** 4  * 节点 5  * @author ice 6  * 7  */ 8 public abstract class Node { 9     private Node next;10     11     public Node(){12         next=null;13     }14     15     public void setNext(Node nextNode){16         next=nextNode;17     }18     19     public Node getNext(){20         return next;21     }22 }

 

链表类，实现了插入首尾节点、指定位置节点，删除节点、指定位置节点，链表的逆序以及判空操作：

1 package cn.wzbrilliant.datastructure;  2   3 /**  4  * 链表  5  * @author ice  6  *  7  */  8 public class Link {  9      10     protected Node head; 11     protected Node tail; 12     protected int size; 13  14     public Link() { 15         this.head = null; 16         this.tail = null; 17         this.size = 0; 18     } 19      20     public void addAtFirst(Node node){ 21         node.setNext(head); 22         head=node; 23         if(size==0) 24             tail=node; 25         size++; 26     } 27      28     public void addAtLast(Node node){ 29         if(size==0){ 30             head=tail=node; 31         }else{ 32             tail.setNext(node); 33             tail=node; 34         } 35         node.setNext(null); 36         size++; 37     } 38      39     public void removeFirst(){ 40         if(size==0) 41             throw new RuntimeException("link size is 0..."); 42         head=head.getNext(); 43         if(size==1){ 44             tail.setNext(null); 45         } 46         size--; 47     } 48      49     public void removeLast(){ 50         if(size==0) 51             throw new RuntimeException("link size is 0..."); 52          53         if(size==1){ 54             head=tail=null; 55             size--; 56             return ; 57         } 58          59         Node node=head; 60         while(node.getNext()!=tail){ 61             node=node.getNext(); 62         } 63         node.setNext(null); 64         tail=node; 65         size--; 66     } 67  68     /** 69      * 队列逆序 70      */ 71     public void reverse() { 72         Node preNode, node, tempNode; 73         if (size == 0) 74             return; 75         preNode = head; 76         node = preNode.getNext(); 77         preNode.setNext(null); 78         tail = preNode; 79         while (node != null) { 80             tempNode = node.getNext(); 81             node.setNext(preNode); 82             preNode = node; 83             node = tempNode; 84         } 85         head = preNode; 86     } 87  88     /** 89      * 在第index个节点后插入newNode 90      *  91      * @param newNode 92      * @param index 93      */ 94     public void insert(Node newNode, int index) { 95         if (index < 0 || index > size) 96             throw new RuntimeException("索引错误"); 97  98         if (index == 0) { 99             newNode.setNext(head);100             head = newNode;101             size++;102             return;103         }104 105         if (index == size) {106             newNode.setNext(null);107             tail.setNext(newNode);108             tail = newNode;109             size++;110             return;111         }112 113         Node node = head;114         for (int i = 1; node != null; i++, node = node.getNext()) {115             if (i == index) {116                 newNode.setNext(node.getNext());117                 node.setNext(newNode);118                 size++;119                 return;120             }121         }122 123     }124 125     /**126      * 移除Node节点    Node节点需重写equals()方法127      * 128      * @param node129      */130     public void remove(Node node) {131         if (node == null || size == 0)132             throw new RuntimeException("remove error...");133         for (Node temp = head; temp != null; temp = temp.getNext()) {134             if (temp == head) {135                 if (temp.equals(node)) {136                     head = head.getNext();137                     size--;138                     continue;139                 }140             }141             if (temp.getNext().equals(node)) {142                 temp.setNext(temp.getNext().getNext());143                 size--;144             }145 146         }147     }148 149     public Node getFirst() {150         if (size == 0)151             return null;152         return head;153     }154 155     public Node getLast() {156         if (size == 0)157             return null;158         return tail;159     }160 161     public int size() {162         return size;163     }164 165     public boolean isEmpty() {166         if (size == 0)167             return true;168         return false;169     }170 }

 

栈类，实现了入栈、出战、获取栈顶元素以及判空的操作：

1 package cn.wzbrilliant.datastructure; 2  3 /** 4  * 栈 5  * @author ice 6  * 7  */ 8 public class Stack { 9     private int size;10     private Node top;11 12     public Stack() {13         size = 0;14         top = null;15     }16 17     public void push(Node node) {18         node.setNext(top);19         top = node;20         size++;21     }22 23     public Node pop() {24         if (top == null)25             return null;26         Node node = top;27         top = top.getNext();28         size--;29         return node;30     }31 32     public Node top() {33         return top;34     }35 36     public int size() {37         return size;38     }39 40     public boolean isEmpty() {41         if (size == 0)42             return true;43         return false;44     }45 }

 

队列类，实现了入队、出队、判空的操作：

1 package cn.wzbrilliant.datastructure; 2  3 /** 4  * 队列 5  * @author ice 6  * 7  */ 8 public class Queue { 9 10     private Node head;11     private Node tail;12     private int size;13 14     public Queue() {15         this.head = null;16         this.tail = null;17         this.size = 0;18     }19 20     public void enQueue(Node node) {21         tail.setNext(node);22         tail = node;23         size++;24     }25 26     public Node deQueue() {27         if (size == 0)28             return null;29         Node node = head;30         head = head.getNext();31         size--;32         return node;33     }34 35     public int size() {36         return size;37     }38 39     public boolean isEmpty() {40         if (size == 0)41             return true;42         return false;43     }44 45 }