線性表的鏈式存儲與實現
實現線性表的另一種方法是鏈式存儲，即用指針將存儲線性表中數據元素的那些單元依次串聯在一起。這種方法避免了在數組中用連續的單元存儲元素的缺點，因而在執行插入或 刪除運算時，不再需要移動元素來騰出空間或填補空缺。然而我們為此付出的代價是，需要在每個單元中設置指針來表示表中元素之間的邏輯關系，因而增加了額外的存儲空間的開銷.
單鏈表
鏈表是一系列的存儲數據元素的單元通過指針串接起來形成的，因此每個單元至少有兩個域，一個域用于數據元素的存儲，另一個域是指向其他單元的指針。這里具有一個數據域和多個指針域的存儲單元通常稱為結點（node）.
結點接口
package com.wjy.Data_Structure.linearlist.common;public interface Node { /** * 獲取結點數據域 * * @return */ public Object getData(); /** * 設置結點數據域 * * @param obj */ public void setData(Object obj);}單鏈表結點定義
package com.wjy.Data_Structure.linearlist.common;//單鏈表結點定義public class SLNode implements Node { private Object element; private SLNode next; public SLNode() { } public SLNode(Object ele, SLNode next) { this.element = ele; this.next = next; } public SLNode getNext() { return next; } public void setNext(SLNode next) { this.next = next; } /******** Methods of Node Interface **********/ @Override public Object getData() { return element; } @Override public void setData(Object obj) { element = obj; }}線性表的單鏈表實現
在使用單鏈表實現線性表的時候，為了使程序更加簡潔，我們通常在單鏈表的前面添 加一個啞元結點，也稱為頭結點。在頭結點中不存儲任何實質的數據對象，其 next 域指向 線性表中 0 號元素所在的結點，頭結點的引入可以使線性表運算中的一些邊界條件更容易處理。
package com.wjy.Data_Structure.linearlist.listslinkimpl;import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;import com.wjy.Data_Structure.linearlist.common.List;import com.wjy.Data_Structure.linearlist.common.SLNode;import com.wjy.Data_Structure.linearlist.common.Strategy;import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;//線性表的單鏈表實現public class ListSLinked implements List { private Strategy strategy; // 數據元素比較策略 private SLNode head; // 單鏈表首結點引用 private int size;// 線性表中數據元素的個數 public ListSLinked() { this(new DefaultStrategy()); } public ListSLinked(Strategy strategy) { this.strategy = strategy; head = new SLNode(); size = 0; } /** * 輔助方法： 獲取數據元素 e 所在結點的前驅結點 * * @param e * @return */ private SLNode getPreNode(Object e) { SLNode p = head; while (p.getNext() != null) if (strategy.equal(p.getNext().getData(), e)) return p; else p = p.getNext(); return null; } /** * 輔助方法： 獲取序號為 0<=i<size 的元素所在結點的前驅結點 * * @param i * @return */ private SLNode getPreNode(int i) { SLNode p = head; for (; i > 0; i--) p = p.getNext(); return p; } /** * 輔助方法： 獲取序號為 0<=i<size 的元素所在結點 * * @param i * @return */ private SLNode getNode(int i) { SLNode p = head.getNext(); for (; i > 0; i--) p = p.getNext(); return p; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { return indexOf(e) != -1; } @Override public int indexOf(Object e) { SLNode p = head.getNext(); int index = 0; while (p != null) if (strategy.equal(p.getData(), e)) { return index; } else { index++; p = p.getNext(); } return -1; } @Override public void insert(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i > size) throw new OutOfBoundaryException("錯誤，指定的插入序號越界"); SLNode p = getPreNode(i); SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return; } @Override public boolean insertBefore(Object obj, Object e) { SLNode p = getPreNode(obj); if (p != null) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } return false; } @Override public boolean insertAfter(Object obj, Object e) { SLNode p = head.getNext(); while (p != null) if (strategy.equal(p.getData(), obj)) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } else { p = p.getNext(); } return false; } @Override public Object remove(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的刪除序號越界。"); SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; return obj; } @Override public boolean remove(Object e) { SLNode p = getPreNode(e); if (p != null) { p.setNext(p.getNext().getNext()); size--; return true; } return false; } @Override public Object replace(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的序號越界。"); SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj; } @Override public Object get(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的序號越界。"); SLNode p = getNode(i); return p.getData(); }}簡單的測試用例
package com.wjy.Data_Structure.linearlist.listslinkimpl;import org.junit.Test;import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;public class ListSLinkedTest { @Test public void testInsert() { ListSLinked list = new ListSLinked(); for (int i = 0; i < 10; i++) { list.insert(i, i + 1); } System.out.println("刪除：" + list.remove(0)); System.out.println(list.contains(1)); list.insertBefore(2, 100); list.insertAfter(2, 101); list.replace(list.getSize() - 1, 1000); for (int i = 0; i < list.getSize(); i++) { System.out.println(list.get(i)); } }}數據結構學習代碼倉庫：
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持武林網！
新聞熱點
疑難解答
