一、線性表、順序表和雙向鏈表的區(qū)別
線性表是具有相同數(shù)據(jù)類型的n(n>0)個數(shù)據(jù)元素的有限序列。線性表的順序存儲結(jié)構(gòu)就是順序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)就是鏈表，鏈表又包括單向鏈表、雙向鏈表、循環(huán)鏈表、靜態(tài)鏈表等。
順序表可以實現(xiàn)隨機訪問，隨機存取，占用連續(xù)的存儲空間，空間利用率較高，但是順序表的插刪，需要移動多個元素。
鏈表只能順序訪問，占用額外的存儲空間存儲元素間的關(guān)系，空間利用率更低，存儲空間不一定連續(xù)，但是鏈表的插刪不需要移動多個元素。
雙向鏈表解決了單向鏈表只能從前向后遍歷，實現(xiàn)了可以通過某結(jié)點訪問它的直接前驅(qū)、直接后繼。
線性表是一種抽象的數(shù)據(jù)類型，表中的元素的數(shù)據(jù)類型相同，首結(jié)點沒有前驅(qū)結(jié)點，只有一個后繼結(jié)點，尾結(jié)點沒有后繼結(jié)點，只有一個前驅(qū)結(jié)點，其它結(jié)點只有一個前驅(qū)和一個后繼結(jié)點。
順序表指的是線性表用順序存儲方式（一般用數(shù)組）保存。
雙向鏈表指的是線性表用雙向鏈表的方式存儲。
延伸閱讀：
二、線性表基本架構(gòu)
對于一個線性表來說。不管它的具體實現(xiàn)如何，但是它們的方法函數(shù)名和實現(xiàn)效果應(yīng)該一致(即使用方法相同、達(dá)成邏輯上效果相同，差別的是運行效率)。線性表的概念與Java的接口/抽象類有那么幾分相似。非常知名的就是List的Arraylist和LinkedList，List是一種邏輯上的結(jié)構(gòu)，表示這種結(jié)構(gòu)為線性表，而ArrayList，LinkedList更多的是一種物理結(jié)構(gòu)(數(shù)組和鏈表)。
所以基于面向?qū)ο蟮木幊趟季S，我們可以將線性表寫成一個接口，而具體實現(xiàn)的順序表和鏈表的類可以實現(xiàn)這個線性表的方法，提高程序的可讀性，還有一點比較重要的，記得初學(xué)數(shù)據(jù)結(jié)構(gòu)與算法時候?qū)崿F(xiàn)的線性表都是固定類型(int),隨著知識的進(jìn)步，我們應(yīng)當(dāng)采用泛型來實現(xiàn)更合理。至于接口的具體設(shè)計如下：
package LinerList;
public interface ListInterface
??? void Init(int initsize);//初始化表
??? int length();
??? boolean isEmpty();//是否為空
??? int ElemIndex(T t);//找到編號
??? T getElem(int index) throws Exception;//根據(jù)index獲取數(shù)據(jù)
??? void add(int index,T t) throws Exception;//根據(jù)index插入數(shù)據(jù)
??? void delete(int index) throws Exception;
??? void add(T t) throws Exception;//尾部插入
??? void set(int index,T t) throws Exception;
??? String toString();//轉(zhuǎn)成String輸出???
}
京公網(wǎng)安備 11010802030320號