①泡茶看数据结构-表ADT

前言

小朽，晚上回到寝室。烧了开水，又泡了一杯下午喝了的小毛尖。耳机听着萨克斯，总结下今天学的数据结构和算法中的表ADT。

　　　　表ADT节点：

　　　　　　 #单链表

　　　　　　 #双链表

　　　　　　 #循环链表

　　　　　　 #浅谈面试题一道

喝一口热热的茶，算法和数据结构虽然枯燥，希望我不讲的枯燥。毛尖还是淡淡的味道，非常喜欢。

回顾

①ADT：带一组操作的一些对象的集合：对象及对象的操作。

②java考虑了ADT实现，隐藏了实现的细节。

单链表

①链表中的数据是以节点来表示的，每个节点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个节点的地址数据。

　　上面是比较官方的，我的版本就像老式火车一样：火车节号→火车里面东西

　　②思考

　　　　相比表的数组实现，单链表的好处明显的两点：避免了插入和删除的开销。还有值得说的一点，改变表的起始端（表头和亚节点）。以下是我的观点：如果像一些查询较多的应用，数组和链表都行。但像有些，更新和插入，删除多的情况，比如游戏中的装备等，就应该选择考虑下链表。这就是学这些的nice point。

　　　　　　　　　　　　　　　　　　它冒着热气，像是生活，coding生活那样有味。

　　③例子来一枚-java

  1 package LinkedList;   
  2   
  3 /**  
  4  * <p><strong>我的Java单链表练习</strong></p>  
  5  * <p>单链表提供了在列表头的高效插入和删除操作，不过在单链表的末尾的插入操作效率很低.</p>  
  6  * <p>单链表指针域保存着下一节点的引用，尾结点的指针域等于null</p>  
  7  * @author baby69yy2000  
  8  */  
  9 public class SingleLinkedList<T> {   
 10        
 11     /**  
 12      * 结点类  
 13      */  
 14     private static class Node<T> {   
 15         T nodeValue; // 数据域   
 16         Node<T> next; // 指针域保存着下一节点的引用   
 17            
 18         Node(T nodeValue, Node<T> next) {   
 19             this.nodeValue = nodeValue;   
 20             this.next = next;   
 21         }   
 22            
 23         Node(T nodeValue) {   
 24             this(nodeValue, null);   
 25         }   
 26     }   
 27   
 28     // 下面是SingleLinkedList类的数据成员和方法   
 29     private Node<T> head, tail;   
 30        
 31     public SingleLinkedList() {   
 32         head = tail = null;   
 33     }   
 34        
 35     /**  
 36      * 判断链表是否为空  
 37      */  
 38     public boolean isEmpty() {   
 39         return head == null;   
 40     }   
 41        
 42     /**  
 43      * 创建头指针，该方法只用一次！  
 44      */  
 45     public void addToHead(T item) {   
 46         head = new Node<T>(item);   
 47         if(tail == null) tail = head;   
 48     }   
 49        
 50     /**  
 51      * 添加尾指针，该方法使用多次  
 52      */  
 53     public void addToTail(T item) {   
 54         if (!isEmpty()) { // 若链表非空那么将尾指针的next初使化为一个新的元素   
 55             tail.next = new Node<T>(item); // 然后将尾指针指向现在它自己的下一个元素   
 56             tail = tail.next;   
 57         } else { // 如果为空则创建一个新的！并将头尾同时指向它   
 58             head = tail = new Node<T>(item);         
 59         }   
 60     }   
 61        
 62     /**  
 63      * 打印列表  
 64      */  
 65     public void printList() {   
 66         if (isEmpty()) {   
 67             System.out.println("null");   
 68         } else {   
 69             for(Node<T> p = head; p != null; p = p.next)   
 70                 System.out.println(p.nodeValue);   
 71         }   
 72     }   
 73        
 74     /**  
 75      * 在表头插入结点，效率非常高  
 76      */  
 77     public void addFirst(T item) {   
 78         Node<T> newNode = new Node<T>(item);   
 79         newNode.next = head;   
 80         head = newNode;   
 81     }   
 82        
 83     /**  
 84      * 在表尾插入结点，效率很低  
 85      */  
 86     public void addLast(T item) {   
 87         Node<T> newNode = new Node<T>(item);   
 88         Node<T> p = head;   
 89         while (p.next != null) p = p.next;   
 90         p.next = newNode;   
 91         newNode.next = null;   
 92     }   
 93        
 94     /**  
 95      * 在表头删除结点，效率非常高  
 96      */  
 97     public void removeFirst() {   
 98         if (!isEmpty()) head = head.next;   
 99         else System.out.println("The list have been emptied!");   
100     }   
101        
102     /**  
103      * 在表尾删除结点，效率很低  
104      */  
105     public void removeLast() {   
106         Node<T> prev = null, curr = head;   
107         while(curr.next != null) {   
108             prev = curr;   
109             curr = curr.next;   
110             if(curr.next == null) prev.next = null;   
111         }   
112     }   
113        
114     /**  
115      * <p>插入一个新结点</p>  
116      * <ul>插入操作可能有四种情况:  
117      * <li>①表为空, 返回false</li>  
118      * <li>②表非空,指定的数据不存在</li>  
119      * <li>③指定的数据是表的第一个元素</li>  
120      * <li>④指定的数据在表的中间</li></ul>  
121      * @param appointedItem 指定的nodeValue  
122      * @param item 要插入的结点  
123      * @return 成功插入返回true;  
124      */  
125     public boolean insert(T appointedItem, T item) {   
126         Node<T>  prev = head, curr = head.next, newNode;   
127         newNode = new Node<T>(item);   
128         if(!isEmpty()) {   
129             while((curr != null) && (!appointedItem.equals(curr.nodeValue))) { //两个判断条件不能换   
130                 prev = curr;   
131                 curr = curr.next;   
132             }   
133             newNode.next = curr; //②③④   
134             prev.next = newNode;   
135             return true;    
136         }   
137         return false; //①   
138     }   
139        
140     /**  
141      * <p>移除此列表中首次出现的指定元素</p>  
142      * <ul>删除操作可能出现的情况:  
143      * <li>①prev为空，这意味着curr为head. head = curr.next; --> removeFirst();</li>  
144      * <li>②匹配出现在列表中的某个中间位置，此时执行的操作是 --> prev.next = curr.next;,</li></ul>  
145      * <p>在列表中定位某个结点需要两个引用:一个对前一结点(prev左)的引用以及一个对当前结点(curr右)的引用.</p>  
146      * prev = curr;  
147      * curr = curr.next;  
148      */  
149     public void remove(T item) {   
150         Node<T> curr = head, prev = null;   
151         boolean found = false;   
152         while (curr != null && !found) {   
153             if (item.equals(curr.nodeValue)) {   
154                 if(prev == null) removeFirst();   
155                 else prev.next = curr.next;   
156                 found = true;   
157             } else {   
158                 prev = curr;   
159                 curr = curr.next;   
160             }   
161         }   
162     }   
163        
164     /**  
165      * 返回此列表中首次出现的指定元素的索引，如果列表中不包含此元素，则返回 -1.  
166      */  
167     public int indexOf(T item) {   
168         int index = 0;   
169         Node<T> p;   
170         for(p = head; p != null; p = p.next) {   
171             if(item.equals(p.nodeValue))   
172                 return index;   
173             index++;   
174                    
175         }   
176         return -1;   
177     }   
178        
179     /**  
180      * 如果此列表包含指定元素，则返回 true。  
181      */  
182      public boolean contains(T item) {   
183          return indexOf(item) != -1;   
184      }   
185        
186     public static void main(String[] args) {   
187         SingleLinkedList<String> t = new SingleLinkedList<String>();   
188         t.addToHead("A");   
189         //t.addFirst("addFirst");   
190         t.addToTail("B");   
191         t.addToTail("C");   
192         System.out.println(t.indexOf("C")); // 2   
193         System.out.println(t.contains("A")); // true   
194         //t.addLast("addLast");   
195         //t.removeLast();   
196         //t.insert("B", "insert");   
197         //t.removeFirst();   
198         //t.remove("B"); // A C   
199         t.printList(); // A B C   
200            
201     }   
202   
203 }