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