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