519
技術社區[雲棲]
數據結構之鏈表
數組的兩大缺點：
1。若改變數組的大小就要創建一個新的數組，並需要從原數組複製所有的數據到新的數組
2。數組元素在內存中依次順序存儲，這意味著向數組插入一項要移動數組中的其他元素
因此，我們使用鏈式結構，鏈式結構是存儲數據的結點以及指向其他節點的指針的集合。如此一來，節點可以位於內存的任意位置，而且從一個節點到另一個節點的傳遞可以通過在結構中存儲節點間引用來實現。
一。單向鏈表
1。鏈表：
如果一個節點包含指向另一個節點的數據值，那麼多個節點可以連接成一串，隻通過一個變量訪問整個節點序列，這樣的節點序列稱為鏈表（linked list）
2。單向鏈表：
如果每個節點僅包含其指向後繼節點的引用，這樣的鏈表稱為單向鏈表。
一個整型單向鏈表的實現：
package com.sohu.blog.denns_zane.list;
/** */ /** 
* @author dennis * @Description 整型單向鏈表節點
*/ public class IntSLLNode 
{ public int info; // 用戶信息 public IntSLLNode next; // 下一個節點，自引用 
/** */ /** * @param info * @param next
*/ public IntSLLNode( int info, IntSLLNode next) { this .info = info; this .next = next; } /** */ /** * @param info */ public IntSLLNode( int info) { this (info, null ); } } /** */ /** * */ package com.sohu.blog.denns_zane.list; /** */ /** * @author dennis * desc: 整型單向鏈表 */ public class IntSLList { protected IntSLLNode head, tail; public IntSLList() { head = tail = null ; } public boolean isEmpty() { return head == null ; } /** */ /** * @description 增加新節點，並設置它的next為原head * @param el */ public void addToHead( int el) { head = new IntSLLNode(el, head); if (tail == null ) tail = head; } /** */ /** * @description 增加新節點，並設置原tail的next為新節點 * @param el */ public void addToTail( int el) { if ( ! isEmpty()) { tail.next = new IntSLLNode(el); tail = tail.next; } else { head = tail = new IntSLLNode(el); } } public int deleteFromHead() { if (head == null ) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null ; else head = head.next; return el; } public int deleteFromTail() { if (head == null ) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null ; else { IntSLLNode temp; for (temp = head; temp.next != null && temp.next != tail; temp = temp.next) tail = temp; System.out.println(tail.info); tail.next = null ; } return el; } public void printAll() { for (IntSLLNode temp = head; temp != null ; temp = temp.next) System.out.print(temp.info + " " ); } public boolean isInList( int el) { for (IntSLLNode temp = head; temp != null ; temp = temp.next) { if (temp.info == el) return true ; } return false ; } /** */ /** * @param el */ public void delete( int el) { if ( ! isEmpty()) { if (head == tail && head.info == el) head = tail = null ; else if (head.info == el) head = head.next; else { IntSLLNode pred, temp; // pred為找的節點的前一節點，temp即為找到的節點 for (pred = head, temp = head.next; temp != null ; pred = pred.next, temp = temp.next) { if (temp.info == el) { pred.next = temp.next; // 前一節點的next設置為當前節點的next if (temp == tail) tail = pred; } } } } } } 二。雙向鏈表
一個整型雙向鏈表的實現：
/** *//** * */package com.sohu.blog.denns_zane.list;/** *//** * @author dennis desc:雙向鏈表節點 */public class IntDLLNode { public int info; public IntDLLNode prev, next; /** *//** * @param info * @param prev * @param next */ public IntDLLNode(int info, IntDLLNode next, IntDLLNode prev) { super(); this.info = info; this.prev = prev; this.next = next; } public IntDLLNode(int info) { this(info, null, null); }}/** *//** * */package com.sohu.blog.denns_zane.list;/** *//** * @author dennis * */public class IntDLList { private IntDLLNode head, tail; public IntDLList() { head = tail = null; } public boolean isEmpty() { return head == null; } public void addToHead(int el) { if (head == null) head = new IntDLLNode(el); else { head = new IntDLLNode(el, head, null); head.next.prev = head; } if (tail == null) tail = head; } public void addToTail(int el) { if (!isEmpty()) { tail = new IntDLLNode(el, null, tail); tail.prev.next = tail; } else head = tail = new IntDLLNode(el); } public int removeFromTail() { if (head == null) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null; else { tail = tail.prev; tail.next = null; } return el; } public int removeFromHead() { if (head == null) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null; else { head = head.next; head.prev = null; } return el; } public boolean isInList(int el) { if (head == null) return false; IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { return true; } } return false; } public void delete(int el) { if (head == null) throw new NullPointerException(); IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { if (temp == head) { head.next.prev = null; head = head.next; } else temp.prev.next = temp.next; } } } public void printAll() { IntDLLNode temp;