雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
java模擬雙鏈表結構.實現增刪改查等方法.
/** * 雙鏈表 */public class MyDoubleLink<T> implements Iterable<T>{ /** *節點的封裝類 */ PRivate class Node{ Node prev;//上一個節點 T data;//數據 Node next;//下一個節點 } private Node head;//頭節點 private Node rear;//尾節點 /** * 添加數據 * @param data */ public void add(T data){ //1.創建新的節點 Node node = new Node(); //2.把數據放入節點中 node.data = data; //3.把節點鏈接到鏈表中 //從鏈表的尾部添加數據 if (rear == null) { //說明鏈表是空,當前節點就成為頭節點 rear = node; head = node; }else { //有頭節點 rear.next = node; node.prev = rear; rear = node; } } /** * 重寫toString方法 */ public String toString(){ StringBuffer sb = new StringBuffer("["); //遍歷鏈表中的所有數據 Node node = head;//從頭節點開始遍歷數據 while (node != null) { //有數據 //拼接數據 //判斷是否是尾節點 if (node != rear) { sb.append(node.data+", "); }else { sb.append(node.data); } //條件的改變 node = node.next; } sb.append("]"); return sb.toString(); } /** * 刪除數據 * 1.只有一個數據 * 2.刪除頭節點 * 3.刪除數據 * 4.刪除尾節點 * @param data */ public void remove(T data){ //1.查找數據是否存在,查找數據所在的節點 Node node = findData(data); //2.判斷node是否存在 if (node != null) { //存在 remove(node); } } /** * 刪除節點 * @param node */ public void remove(Node node){ if (node == head && node == rear) { //1.只有一個數據 head = null; rear = null; }else if (node == head) { //2.刪除頭節點,后面肯定有節點 head = head.next; head.prev = null; }else if (node == rear) { //3.刪除尾節點,前面肯定有節點 rear = rear.prev; rear.next = null; }else { //4.刪除數據,前后肯定有節點 node.prev.next = node.next; node.next.prev = node.prev; } } /** * 查找數據所在節點 * @param data * @return */ private Node findData(T data) { Node node = head; while (node != null) { if (node.data.equals(data) && node.data.hashCode() == data.hashCode()) { //找到數據 break; }else { //繼續下一個 node = node.next; } } return node; } /** * 修改數據 * @param oldData * @param newData */ public void updata(T oldData,T newData){ Node node = findData(oldData); if (node != null) { node.data = newData; } } /** * 修改數據(在對象的hash值相同的情況下修改對象屬性值) * @param data */ public void updata(T data){ Node node = findData(data); if (node != null) { node.data = data; } } /** * 是否包含數據 * @param data * @return */ public boolean contains(T data){ return findData(data) != null; } /** * 重寫迭代器方法,可以用增強for */ @Override public Iterator iterator() { class MyIte implements Iterator{ private Node node = head;//從頭節點遍歷 @Override public boolean hasNext() { return node != null; } @Override public Object next() { Object data = node.data;//獲取數據 node = node.next;//設置下一個數據 return data; } @Override public void remove() { //刪除next方法返回的數據 MyDoubleLink.this.remove(node.prev); } } return new MyIte(); } /** * 從頭部添加數據 * @param data */ public void addFirst(T data){ //1.創建新的節點 Node node = new Node(); //2.把數據放入節點中 node.data = data; //3.把節點鏈接到鏈表中 //從鏈表的尾部添加數據 if (rear == null) { //說明鏈表是空,當前節點就成為頭節點 rear = node; head = node; }else { //有頭節點 head.prev = node; node.next = head; head = node; } } /** * 排序添加數據,添加數據時自動排序 * @param data */ public void addSort(T data){ addSortBlock(data,null); } /** * 查找比data大的第一個節點 * @param data * @return */ private Node findNext(T data){ //從頭節點開始找 Node node = head; while (node != null) { //比較 if (compare(node.data, data)>0) { break; }else { //繼續找下一個 node = node.next; } } return node; } /** * 查找比data大的第一個節點(使用比較器) * @param data * @param comp 比較器 * @return */ private Node findNext(T data,Comparator<T> comp){ //從頭節點開始找 Node node = head; while (node != null) { //比較 if (comp.compare(node.data, data)>0) { break; }else { //繼續找下一個 node = node.next; } } return node; } /** * 比較兩個數據的大小 * @param obj1 * @param obj2 * @return * 0 相等 * 大于0 obj1 > obj2 * 小于0 obj1 < obj2 */ public int compare(T obj1,T obj2){ Comparable c1; Comparable c2; if (obj1 instanceof Comparable) { //數據實現比較器 c1 = (Comparable)obj1; c2 = (Comparable)obj2; }else { //沒有實現比較器 c1 = obj1.toString(); c2 = obj2.toString(); } return c1.compareTo(c2); } /** * 添加數據并進行排序(使用比較器) * @param data * @param comparable 比較器 */ public void addSort(T data,Comparator<T> comparable){ addSortBlock(data,comparable); } /** * 添加數據并進行排序(私有方法) * @param data 傳入數據 * @param comp 比較器 */ private void addSortBlock(T data,Comparator<T> comp){ //1.創建新的節點 Node node = new Node(); //2.把數據放入節點中 node.data = data; Node next = null; //2.找位置(從小到大)添加數據 if (comp != null) { next= findNext(data,comp); }else { next = findNext(data); } if (next != null) { //找到下一個節點,把data放到next節點前 if (next == head) { addFirst(data); }else { next.prev.next = node; node.next = next; node.prev = next.prev; next.prev = node; } }else { //沒找到下一個節點,data最大 add(data); } }}新聞熱點
疑難解答
